B트리와 B+트리에 관련하여 다음을 설명하시오.
가. B트리, B+트리 삽입 알고리즘
나. B트리, B+트리 삭제 알고리즘
다. 26, 57, 5, 33, 72, 45를 순서대로 삽입하고, 72, 33, 45를 순서대로 삭제하는 B트리, B+트리를 그리시오. (단, 차수는 3)
- 균형을 유지하는 m-way 탐색 트리, B트리와 B+트리의 개요
- B 트리 : Root 노드는 최소 2개 이상 자식 노드와 최소 1개 이상 key값을 가지며, Root 노드와 Leaf 노드를 제외한 모든 노드는 최소 m/2개, 최대 m개 서브 트리로 구성된 자료구조
- B+ 트리 : 순차 탐색 성능 향상을 위해 인덱스 집합(Index Set)과 순차 집합(Sequence Set)으로 구성된 트리, Leaf노드는 Linked List를 이용하여 순차적 접근이 용이하게 구성된 자료구조
- B크리, B+트리 삽입 알고리즘
가. B트리 삽입 알고리즘
1) 여유공간 있을 경우
* 삽입할 Key 값은 항상 Leaf 노드에 삽입
2) 여유공간 없을 경우
- 해당 Leaf 노드에 새로운 key 값을 삽입 했을 경우 가정
- 중간 key 값을 중심으로 2개 노드로 분할(Split)
- 중간 key 값은 분할된 노드에 대한 부모 노드에 삽입
- 이 때, 부모 노드에서 Overflow 발생할 경우 분할 작업 반복
- Leaf 노드는 key를 최대 m-1 개 까지 가질 수 있고, m개 이상인 경우 Overflow 발생에 따른 2개 노드로 분할
나. B+ 트리 삽입 알고리즘
1) 여유공간 있을 경우
- B 트리와 거의 동일
- 단순히 순서에 맞게 삽입
- 신규 노드는 Linked List로 구성된 Leaf 노드에도 삽입
2) 여유공간 없을 경우
- 노드 분할이 발생하면 중간 key 값이 부모 노드로 이동, 새로 분열된 노드에도 포함함
- 신규 노드는 Linked List로 구성된 Leaf 노드에도 삽입
- B트리, B+트리 삭제 알고리즘
가. B트리 삭제 알고리즘
1) 삭제 key 값이 Leaf 노드 인경우
- 삭제는 항상 Leaf 노드에서 이루어짐
- 최소 key 개수가 m/2-1 보다 작은 경우 Underflow 발생
- Underflow 발생 시, 재분배 또는 합병 수행
2) 삭제 key 값이 Leaf 노드가 아닌 경우
- 후행 key 값과 자리를 바꾸어 Leaf 노드로 이동시킨 후 삭제
- 최소 key 개수가 m/2-1 보다 작은 경우 Underflow 발생
- Underflow 발생 시, 재분배 또는 합병 수행
- 재분배(Redistribution) : 트리 구조가 유지되는 Underflow 대응 기법
- 최소 key 개수 보다 많은 key를 가진 형제 노드에서 차출
- 부모 노드에 있던 key 값은 Underflow 발생 노드로 이동
- 차출된 형제 노드 key 값은 부모 노드로 이동
- 합병(Merge) : 트리 구조가 변경되는 Underflow 대응 기법
- 재분배 불가능한 경우 적용
- 형제 노드를 결합하는 방법으로, 합병 결과 빈 노드는 제거
나. B+ 트리 삭제 알고리즘
1) 재배치와 합병 수행하지 않는 경우
- 삭제는 항상 Leaf 노드에서 이루어짐
- Index 부분은 다른 Key 값 검색 시 사용될 수 있기 때문에 Leaf 노드 값이 삭제 되어도 삭제하지 않음
2) 재배치 할 경우
* Index 부분 노드 key 값은 변하지만 Tree 구조는 변하지 않음
3) 합병 할 경우
* Index 부분에서도 key 값을 삭제
4. B 트리, B+ 트리 삽입/삭제 과정
내부정렬
▣ 내부정렬
- 교환 : 버블 정렬, 퀵 정렬
- 삽입 : 삽입 정렬, 셀 정렬
- 병합 : 2-way 병합, n-way 병합
- 분배 : 기수 정렬
- 선택 : 선택 정렬, 히프 정렬
선택 정렬
include
▣ 선택 정렬
- 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식
void printArray(int value[], int count);
void selectionSort(int value[], int count)
{
int i = 0, j = 0;
int min = 0, temp = 0;
// 11 Line : 전체 자료 개수보다 1 적은 횟수(count - 1) 만큼 루프를 돈다.
// 정렬의 마지막에 남은 자료는 최대 자료이기 때문에 추가적인 정렬이 필요 없다.
for(i = 0; i < count-1; i++) {
//12 Line : (정렬되지 않은 자료 중) 최솟값이 위치(min)를 초기화 시킨다.
min = i;
//13~17 Line : 정렬되지 않은 자료들 (j의 값이 i+1 부터 시작된다)을 대상으로 가장 작은 키 값을 찾는다.
for(j = i + 1; j < count; j++) {
if(value[j] < value[min]) {
min = j;
}
}
//18~20 Line : 정렬되지 않은 자료들 중 가장 작은 키 값을 가지는 자료(위치 min)와 정렬 대상이 되는 자료(위치 i)의 위치를 교환한다.
temp = value[i];
value[i] = value[min];
value[min] = temp;
printf(“Step-%d,”, i+1);
printArray(value, count);
}
}
버블 정렬
▣ 정의
- 정렬되지 않은 전체 자료들을 대상으로 인접한 두 개 자료의 키 값을 비교하여 위치를 교환하는 정렬 방식
▣ 원리
1) 인접한 두 개의 값을 비교
2) 앞의 값이 뒤의 값보다 크면 교환
3) 비교할 대상 없을 때까지 반복
▣ 특징
- 효율성 : 최선, 평균, 최악 O(n^2)
- n^2 으로 느린 알고리즘
▣ 소스코드
void printArray(int value[], int count);
void bubbleSort(int value[], int count)
{
int i = 0, j = 0;
int temp = 0;
//Line 12 : 전체 자료 개수보다 1적은 횟수(count-1) 만큼 루프를 돈다.
//정렬의 마지막에 남은 자료는 최대 자료이기 때문에 추가 정렬이 필요 없다.
for(i = count - 1; i >=0; i–) {
if(value[j-1] > value[j]) {
//Line 13 ~ 19 : 정렬되지 않은 자료들을 대상으로 이웃한 두 자료 사이의 위치를 교환한다.
temp = value[j-1];
value[j-1] = value[j];
value[j] = temp;
}
}
printf(“Step-%d,”, count - i);
printArray(value, count);
}
퀵 정렬
▣ 퀵 정렬
- 중심 값(Pivot)을 기준으로 두 자료의 키 값을 비교하여 위치를 교환하는 정렬 방식
- Left : 왼쪽 끝에서 오른쪽으로 움직이면서 피봇보다 큰 자료 찾음
- Right : 오른쪽 끝에서 왼쪽으로 움직이며 피봇보다 작은 자료 찾음
- Left는 Right까지 이동할 수 없고, 반대로 Right는 Left보다 더 왼쪽으로 이동할 수 없다
삽입 정렬
▣ 삽입 정렬
- 기존에 정렬된 부분 집합에 정렬할 자료의 위치를 찾아 삽입하는 정렬 방식
병합 정렬
▣ 정의
- 같은 개수의 원소를 가지는 부분 집합으로 기존 자료를 분할(Divide)하고 분할된 각 부분 집합을 병합(Merge)하면서 정렬 작업을 완성(Conquer)하는 분할 정복(Divide and Conquer) 기법에 의한 정렬 방식
- 2개의 부분 집합의 원소들을 하나의 집합으로 합치는 가운데 정렬이 이루어지는 것이며, 이는 2개의 부분 집합의 원소를 차례로 비교하면서 이루어진다.
▣ 정렬 원리
1) 분할 : 정렬할 데이터 집합을 반으로 나누기
2) 반복 : 나누어진 하위 데이터 집합의 크기가 2 이상이면, 하위 데이터 집합에 대해 “절차 1(분할)을 반복
3) 정렬 및 병합 : 원래 같은 집합의 나뉘어진 하위 데이터 집합 들을 병합 (병합 할 때 데이터 집합의 원소는 순서에 맞추어 정렬)
4) 반복 : 데이터 집합이 다시 하나가 될 때까지 “절차 3(정렬 및 병합)” 반복
▣ 정렬 및 병합 단계 상세 설명
1) 병합을 위한 빈 배열 생성
2) 병합하려는 2개의 부분집합의 첫 원소 비교
3) 키 값이 작은 원소 선택하여 정렬 위해 생성한 배열에 삽입
4) 2~3 과정 반복하여 정렬 완료
▣ 소스코드
void mergeSort(int value[], int buffer[], int start, int end) {
int middle = 0;
//원소의 개수가 1개가 될 때까지 순환적으로 병합 정렬을 실행한다.
if(start < end) {
//2개의 부분 집합으로 나누기 위해 중간 위치 middle을 구한다.
middle = (start+end) / 2;
//왼쪽 부분 집합(start, middle)과 오른쪽 부분집합(middle+1, end)에 대해
//순환적으로 병합 정렬을 실행한다.
mergeSort(value, buffer, start, middle);
mergeSort(value, buffer, middle+1, end);
//병합 정렬이 완료된 두 개의 부분 집합에 대해 병합을 실시한다.
//단, 이 때 병합을 위해 배열의 개수만큼의 추가적인 메모리 공간이 필요하며,
//이를 위해 버퍼(buffer)를 전달한다.
//이 버퍼는 외부에서 전달 받은 것으로, 함수 mergeSort()를 사용하기 위해서는
//이러한 버퍼를 입력 파라미터로 전달해야 한다.
mergeSortInternal(value, buffer, start, middle, end);
}
}
void mergeSortInternal(int value[], int buffer[], int start, int middle, int end) {
//변수들을 초기화 시킨다
int i = 0, j = 0, k = 0, t = 0;
//변수 i : 첫 번째 부분 집합의 원소를 가리키는 인덱스
//변수 j : 두 번째 부분 힙합의 원소를 가리키는 인덱스
//변수 k : 결과 버퍼의 현재 위치를 가리키는 인덱스
i = start;
j = middle + 1;
k = start;
//두 개 부분 집합(start, middle) 및 (middle+1, end)을 대상으로 루프를 돌면서
//각 부분 집합 원소의 키 값을 비교한다.
//만약 키 값이 작다면 해당 원소의 키 값을 복사하고 다음 원소를 가리키도록 이동시킨다.
while(i <= middle && j <= end) {
if(value[i] <= value[j]) {
buffer[k] = value[i];
i++;
} else {
buffer[k] = value[j];
j++;
}
k++;
}
//위 루프를 빠져 나온 것은 두 개의 부분 집합 중 한 개 부분 집합이 모두 복사되었다는 의미이므로,
//원소가 남은 다른 부분 집합의 자료들을 복사해 주어야 한다.
//따라서, 아래 조건에서 어느 부분 집합의 원소가 남았는지 판단한 다음,
//해당 부분 집합의 남은 원소들을 결과 버퍼에 복사한다.
if(i > middle) {
for(t = j; t <= end; t++, k++) {
buffer[k] = value[t];
}
} else {
for(t = i; t <= middle; t++, k++) {
buffer[k] = value[t];
}
}
//정렬 결과가 저장된 버퍼의 내용을 최종적으로 복사한다.
for(t = start; t <= end; t++) {
value[t] = buffer[t];
}
printf (“start-%d,middle-%d,”, start, middle, end);
for(t = start; t <= end; t++) {
printf(“%d “, value[t]);
}
printf(“\n”);
}
히프 정렬
▣ 정의
- 루트 노드 삭제 연산으로 정렬된 데이터 집합을 만들어 내는 정렬 기법
▣ 유형
- Min Heap
- Max Heap
▣ 특징
- 히프는 완전 이진 트리이면서 동시에 최대 트리 혹은 최소 트리를 말하는 것으로, 최대 히프는 루트 노드의 키가 트리 전체 중 항상 최댓값을 지니고, 최소 히프의 루트 노드는 트리 전체 중 항상 최솟값을 가지는 특성이 있다.
- 오름차순 정렬 : 최소 히프에 정렬하고 싶은 자료를 모두 삽입한 다음, 최소 히프에서 자료의 개수 만큼 루트 노드를 삭제하면 키 값이 가장 작은 자료에서 큰 순서대로 자료가 반환된다.
- 내름차순 정렬 : 최대 히프에 자료를 추가한 다음, 루트 노드를 반환하면 키 값이 가장 큰 자료에서 작은 순서대로 자료를 반환하게 된다.
▣ 수행 단계
1) 삽입 : 정렬하고자 하는 Data를 Heap에 삽입
2) 정렬 : Heap 정렬 수행
3) 삭제 : Root 노드의 값을 추출
4) 재정렬 : Heap 재정렬 수행
5) 반복 : 추출할 Data 없을 때까지 1~4 반복
분할 정복 알고리즘
▣ 정의
- 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘
▣ 원리
1) 문제를 더 작은 문제(부문제)로 분할
2) 분할된 문제 해결
3) 해결된 문제 통합
▣ 분할과 정복의 원리 소스코드
function F(x);
if F(x)의 문제가 간단 then;
return F(x)을 직접 계산한 값;
else
x 를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로 부터 F(x)를 구한 값
▣ 종류
1) 병합 정렬 (Merge Sort)
2) 퀵 정렬 (Quick Sort)
3) 선택 문제 (Selection)
4) 최근접 점의 쌍 찾기 (Closet Pair)
그래프
▣ 그래프의 종류
1) 간선의 방향성
- 무방향 그래프 : 간선에 방향이 없는 그래프
- 방향 그래프 : 간선에 방향이 있는 그래프
2) 간선의 가중치
- 가중 그래프 : 간선에 가중치가 할당된 그래프
3) 구조적 특징
- 완전 그래프 : 연결 가능한 최대 간선 수를 가진 그래프
- 부분 그래프 : 원래의 그래프에서 일부의 노드나 간선을 제외하여 만든 그래프
- 다중 그래프 : 중복된 간선을 포함하는 그래프
▣ 그래프의 구현
1) 인접 행렬(Adjacency Matrix)
2) 인접 리스트(Adjcency List)
▣ 그래프 탐색
1) 깊이- 우선 탐색 : 아직 탐색 되지 않은 노드 먼저 탐색 (스택)
2) 넓이-우선 탐색 : 이전 노드에 연결된 모든 노드 탐색 (큐)
▣ 깊이-우선 탐색 알고리즘
traversal_DFS (node v) {
스택 S;
v <- 방문;
push(S, v);
while(not is_empty(S)) {
u <- pop(S);
for(all w ∈ (u의 인접 노드들)) {
if(w != 방문) {
w <- 방문;
push(S, w);
}
}
}
}
▣ 넓이-우선 탐색 알고리즘
traversal_BFS (node v) {
큐 Q;
v <- 방문;
enqueue(Q, v);
while(not is_empty(Q)) {
u <- dequeue(Q);
for(all w ∈ (u의 인접 노드들)) {
if(w != 방문) {
w <- 방문;
enqueue(Q, w);
}
}
}
}
최소 비용 신장 트리
▣ 신장 트리 정의
- 신장(Spanning) : 모든 노드를 포함한다는 의미
- 신장트리(Spanning Tree) : 기존 그래프가 가진 모든 노드를 순환 없이 서로 연결시킨 트리
▣ 최소 비용 신장 트리
- 정의 : 가중 그래프의 신장 트리 중에서 가중치의 합이 최소인 신장 트리
▣ 최소 비용 신장 트리 알고리즘 종류
- 프림 (Prim)
- 크루스칼 (kruskal)
- 솔린 (sollin)
크루스칼(Kruskal)
▣ 정의
- 그래프의 모든 간선을 비용 순으로 정렬한 다음, 낮은 비용을 가지는 간선을 차례대로 선택하여 신장트리
▣ 알고리즘
1) 초기화
- 그래프 G의 최소 비용 신장 트리 H를 다음과 같이 초기화한다.
H= (V(G), E(H)))
단, E(H) = ∅
- 그래프 G의 모든 간선을 가중치 값에 따라 오름차순으로 정렬한다.
2) 루프
Step-1) 정렬된 간선들 중에서 1) 가중치가 작으면서 2) 순환을 발생시키지 않는 간선 e를 추출.
Sep-2) 그래프 G의 모든 노드가 V(T)에 연결 될때까지 Step-1을 반복
프림(Prim)
▣ 정의
- 트리를 확장시켜 최소 비용 신장 트리를 만드는 방법
▣ 특징
- 임의의 시작 노드 1개만 추가하여 알고리즘 시작
- 현재 신장 트리와 연결된(부속된) 간선 중에서 가장 적은 비용을 가지는 간선을 선택(선택된 노드는 제외)
▣ 알고리즘
1) 초기화
- 그래프 G에서 임의의 시작 노드 r을 선택하여, 신장 트리 T를 초기화
V(T) = { r }
E(T) = ∅ (아직 선택된 간선은 없다)
2) 루프
Step-1) V(T)와 부속된(연결된) 모든 간선들 중에서 (1) 가장 가중치가 작으면서 (2) 순환을 발생시키지 않는 간선을 선택하여 신장 트리 T를 확장
E(T) = E(T) ∪ { e }, e: 추가되는 최소 가중치 간선
V(T) = V(T) ∪ { w }, w: e와 부속된 노드로, V(T)에 포함되지 않던 노드
Step-2) 그래프 G의 모든 노드가 V(T)에 포함될 때까지 Step-1을 반복
솔린(Sollin)
▣ 정의
- 각 단계에서 여러 개의 간선을 선택하여, 최소비용 신장트리를 구축하는 알고리즘
▣ 알고리즘
1) 그래프의 각 정점 하나만을 포함하는 n개의 트리로 구성된 신장 포레스트(Forest)에서부터 시작
2) 매번 포레스트에 있는 각 트리마다 하나의 간선을 선택
3) 선정된 간선들은 각각 두개의 트리를 하나로 결합시켜 신장트리로 확장
4) 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선
5) 선택된 간선은 구축중인 신장트리에 추가
6) n - 1 개의 간선으로 된 하나의 트리가 만들어지거나, 더 이상 선정할 간선이 없을 때 종료
▣ 슈도 코드
void sollin() {
/*집합 E 의 초기 상태는 주어진 그래프의 간선 집합*/
/*집합 F 의 초기 상태는 그래프의 모든 정점들로 구성된 간선이 없는 숲*/
T = ;
while (T 는 완전한 하나의 트리가 아니고 E 는 공집합이 아님) {
for (F 내의 각각의 트리 t 에 대하여) {
T 와 또 다른 트리를 연결하는 E 의 간선 중 최소비용 간선(u, v)를 선택;
T = T (u, v) ;
E 에서 간선 (u, v)를 제거;
}
T 에 새로 추가된 간선을 포함하여 F 를 수정;
}
}
최단경로 알고리즘
▣ 정의
- 방향 그래프 G(V,E)에서 n개의 정점이 존재하고 연결선에 가중치가 주어졌을 때 시작 정점 Vi에서 종착 Vj에 도달하는 여러 경로 중에서 가장 짧은 경로. 즉, 가중치의 합이 최소인 경로를 찾는 알고리즘
▣ 유형
- Dijkstra 알고리즘 : 최소비용 경로 설정
- A* 알고리즘 : 휴리스틱 순서 탐색
- Bellman-Ford 알고리즘 : 음의 가중치 허용한 경로
- Floyd-Warshall 알고리즘 : 동적계획 기반 고차원 기법
다익스트라 (Dijkstra)
▣ 개념
- 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
▣ 탐색원리
1) 시작정점과 최초 연결한 근접 정점을 집합 S로 규정
2) 집합 S에 포함되지 않은 정점 중에서 시작 정점으로부터 가장 가까운 정점을 탐색(집합 S에 이웃한 정점 중 하나)
3) 결정된 정점을 집합 S로 포함
4) 새로운 정점이 없어질 때까지 반복
5) 모든 정점이 집합 S에 포함되었다면 종료
▣ 조건
- 시작점이 있으면 모든 정점의 최단거리 구함
- 가중치가 주어진 유향 그래프
- 음의 가중치가 있는 경우 사용 불가
▣ 알고리즘
Step-1) 초기화
1) 집합 S 초기화 : S = V(G)
2) 시작 노드 r에서 다른 노드 w 사이의 거리(yw) 초기화, 노드 r과 연결되지 않는 노드들의 거리는 모두 ∞(무한대)로 설정한다.
Step-2)
1) 집합 S 중에서 최단 거리를 가진 노드 yv를 찾아서 이를 S에서 제거
2) 노드 v에 인접한 노드 w에 대해서 다음 조건 검사를 실시
yw = yv + cvw, if yv + cvw < yw (단, 노드 w는 S에 포함된 노드)
Step-3)
집합 S에 모든 노드가 제거될 때까지 Step 1을 반복
에이 스타 (A*)
▣ 개념
- 그래프의 시작점에서 도착점에 이르는 최단 경로를 찾는 알고리즘으로 최적 우선 탐색 기법을 이용하는 알고리즘
▣ 탐색원리
1) 시작 정점으로부터 목표정점 방향의 가장 근사한 정점을 선택(휴리스틱 함수 사용)
2) 이미 조사된 정점을 닫힌 목록으로, 조사 대상의 정점을 열린목록으로 규정
3) 열린목록에서 가장 유망한 정점을 취하며 조사된 정점은 닫힌목록으로 소속
4) 목표정점에 도달할때까지 열린목록을 조사하여 닫힘목록으로 변환시키는 작업을 반복
▣ 조건
- 최초 시작 정점이 주어짐
- 최단경로 보장 (단, h*(n) <= h(n) 일 경우)
- 알고리즘 평가함수 사용
▣ 특징
- 휴리스틱 함수를 활용
- 모든 정점이 아닌 목표정점까지의 최단거리 탐색
- 최적경로 탐색을 위한 평가함수 사용
- 시스템의 자원을 가장 적게 사용
벨만-포드(Bellman-Ford)
▣ 정의
- 가중 유방향 그래프에서 간서니 음수인 경우 최단 경로 문제를 결정하는 알고리즘
▣ 특징
- 경로의 음의 가중치 허용
- 다익스트라 알고리즘 보다는 수행 속도가 효율적이지는 못함
- 음의 가중치를 가져 다익스트라 알고리즘을 사용하기 힘든 경우 사용
플로이드(Floyd)
▣ 개념
- 그래프 상의 모든 노드에서 다른 모든 노드 사이의 최단 경로를 구하는 알고리즘
▣ 특징
- Dijkstra 알고리즘과 동일한 접근 방법 사용 (최단 경로를 수정하는 전략이 동일함)
- 시작 노드가 1개가 아니라 여러 개
백트래킹 알고리즘
▣ 정의
- 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘
▣ 특징
- Non-Promising : 전혀 해답이 나올 가능성이 없는 마디
- Promising : 해가 나올만한 유망한 마디
- 모든 해
- 후보 해
▣ 방식
- 깊이우선탐색(Depth First Search : DFS)
- 너비우선탐색(Breadth First Search : BFS)
- 최선우선탐색(Best First Search/Heuristic Search)
▣ 목적
- 해가 될 조건을 만족시키는 “진짜 해”를 효율적으로 찾는 것
▣ 절차
1) 상태공간트리의 깊이 우선검색실시
2) 각 마디가 유망한지 점검
3) 만일 유망하지 않으면 그 마디의 부모마디로 돌아가서 검색을 계속
▣ 알고리즘
void checknode(node v)
{
for (each child u of v)
if (promising(u))
if(there is a solution at u)
write the solution;
else
checknode(u);
}
그리디(Greedy, 욕심쟁이) 알고리즘
▣ 정의
- 선택 시 마다 그 순간 최적의 해를 선택하여 최종적인 해를 도출하는 알고리즘
▣ 특징
- 최적성의 원리 : 주어진 선택 시점마다 최상의 해를 선택
- 최적해 미보장 : 결론적인 해가 최적의 해라는 보장은 불가능
- 효율성 개선 : 동적 계획법 대비 효율성(수행시간) 개선
▣ 수행절차
1) 해 선택 : 부분 해 집합에 더해질 다음 항목 선택
2) 적합성 검증 : 제약조건 위반여부 검사
3) 해 검증 : 주어진 문제의 해인지를 검사
▣ 알고리즘
int coin[4] = {500, 100, 50, 10}; //동전 종류 정의
int count[4];
int main() {
int m = 770, i = 0, f = 0; //m=목표 거스름돈
while(i < 4) {
if(coin[i] > m)
i++;
else if(coin[i] < m) {
m -= coin[i]; //코인 값 차감
count[i]++;
} else {
f = 1;
count[i]++;
break;
}
if(f)
print(“%d 원 %d 개, %d 원 %d개, %d 원 %d개, %d 원 %d개 입니다.\n”, coin[0], count[0], coin[1], count[1], coin[2], count[2], coin[3], count[3]);
else
printf(“해를 구하지 못하였습니다. \n”);
return 0;
}
베이즈 정리
▣ 개념
- 새로운 정보 B에 의해 이를 근거로 어떤 사건 A가 발생할 조건부 확률, P(A|B)를 계산하는 이론
▣ 절차
- 사전확률 P(A) -> 추가정보 B -> 사후확률 P(A|B)
▣ 전확률의 정리
- 임의의 사건 B에 대하여 아래의 관계가 성립
- P(B) = P(A1)P(B|A1) + P(A2)P(B|A2) + ….. + P(An)P(B|An)
- P(A) = P(B1)P(A|B1) + P(B2)P(A|B2) + P(B3)P(A|B3) + P(B4)P(A|B4)
▣ 조건부 확률
- 사건 B 하에서 사건 A가 일어날 확률
- P(B1|A) = P(A∩Bi) / P(A)
딥뷰
▣ 인공지능의 특이점의 정의
- 인공지능 기술이 발전을 거듭하여 어느 순간 기술적 진보가 폭발적으로 빨라지는 순간으로, 즉, 인공지능의 연구 또한 인공지능이 스스로 하게 되는 기술 변화의 무한 가속 지점
▣ 특이점이 이루어지는 방향
- 인공지능 기술의 진보 : 인간의 지능 선회
- 인공지능의 확장 : 뇌를 인공신경망으로 대체
- 데이터베이스의 이용 : 데이터 기반 인공지능 결합
- 유전자 기술 : 인공 DNA 번역
▣ 액소브레인(Exobrain) 소프트웨어 개념
- 내 몸 바깥에 있는 인공두뇌로써 기계가 자연어를 이해하고 지식을 학습해 생산하는 인간과 기계와의 의사소통을 뛰어넘어 지식 소통이 가능한 인공지능 소프트웨어
▣ 액소브레인 소프트웨어의 기술요소
- 자연어 이해 및 질의 응답 기술
- 자가학습 및 추론 기술
- 인간모사형 학습 지능 원천
- 자율 협업 지능 기술
▣ 딥뷰의 개념
- 대규모 이미지 동영상을 분석하여 내용 이해 및 상황 예측을 실시간으로 수행, 대규모 시각 빅데이터의 분석 및 예측 가능한 시각지능 기반 시각 인공지능 소프트웨어
▣ 딥뷰의 기술요소
- 수집관리 기술 : 시각 데이터 뱅크 (대용량 시각 데이터 저장)
- 대규모 처리 기술 : 시각 데이터 처리 파이프 라인 SW (분산처리, CPU-GPU)
- 내용 분석 기술 : 다차원 시각 데이터 내용 분석 및 이해 SW (시각 텍사노미, 시각 데이터 처리, 시각 데이터 이해, 시공계열 공간 이해)
전문가 시스템(Experts System)
▣ 정의
- 전문가가 지니고 있는 지식이나 노하우 등을 컴퓨터에 집어넣어 전문가와 같은 판단이나 추론을 컴퓨터가 행하게 하는 시스템
▣ 특징
- 전문가 작업 자동화
- 고신뢰성 및 비용절감
▣ 활용 분야
- 의료, 화학, 국방
▣ 구성요소
- 사용자 I/F : 의사소통
- 추론엔진 : 지식 처리기
- 설명기관 : 도출과정, 규칙 제공
- 지식베이스 : 사실 저장
▣ 전문가 시스템의 추론방법
- 연역법 : 일반적 사실 -> 특수한 사실 이나 원리 추리 (삼단논법)
- 귀납법 : 개별적 특수한 사실 전제 -> 일반적 사실이나 원리 결론 (인과관계)
▣ 전문가 시스템의 추론방향
- 전방향 추론
- 후방향 추론
