Algorithm Flashcards
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 알고리즘 : 동적계획 기반 고차원 기법
