그리디 알고리즘

4.2 최소 신장 트리 (MST)

최소 신장 트리 (MInimum Spanning Tree) 란 주어진 가중치 크래프에서 사이클 없이 모든 점들을 연결시킨 드리들 중 간선들의 가중치 합이 최소인 트리이다. 이를 찾기 위해서는 사이클이 없도록 모든 점을 연결시키면 된다. 최소 신장 트리를 찾는 그리디 알고리즘으로는 크루스컬 (Kruskal) 과 프림 (Prim) 알고리즘이 있다. 

 

📍Kruskal 알고리즘

1. 그래프가 주어졌을 때 가중치 순으로 간선을 정렬한다. 그리고, parent 배열을 준비한다. 

2. find() 를 통해 각 노드의 parent 를 찾는다. 처음에는 b 와 c의 parent 가 각각 b와 c로써 서로 다르다. parent 가 서로 다르다면 뒤의 것의 parent 를 앞의 것의 parent 로 업데이트한다. 

 

 

 

3. 같은 방식으로 진행을 해준다. 

 

4. b-f의 parent 를 살펴보면 b와 b 로 동일하다. 이는 사이클이 발생하였다는 의미이므로 해당 간선은 버린다. 

 

5. 같은 방식으로 또 진행한다. 

 

6. b-d 간선을 보면, 둘의 parent 가 다르기 때문에 union 과정을 거친다. d의 parent 가 이미 a 로 업데이트 되었지만, 또 다시 b 로 업데이트 해주면 된다. 

 

 

 

7. 노드가 6개인데 간선 5개가 추가가 되었으므로 알고리즘은 종료된다. 

 

 

📍Prim 알고리즘

1. 임의의 점 (c) 을 선택하고 Tree 배열에 해당 점을 넣는다. (노란색으로 표시) T={c}. 

또한, 0으로 초기화된 Distance 배열을 준비한다.

 

 

2. 시작점 c 와 연결된 각 점들의 가중치를 D 배열에 적는다. 나머지 점들에 대해서는 ∞ 으로 초기화한다. 

3. c에서 가장 가까운 점인 b 를 T 배열에 추가한다. T={c,b}. 그리고, b 에 연결된 각 점들의 가중치를 계산하여 D 배열을 업데이트 한다. 

4. T에 가장 가까운 점인 f를 T배열에 추가한다. T={c,b,f}. 그리고, f 에 연결된 각 점들의 가중치를 계산하여 D 배열을 업데이트 한다. 

5. T에 가장 가까운 점인 a를 T배열에 추가한다. T={c,b,f,a}. 그리고, a 에 연결된 각 점들의 가중치를 계산하여 D 배열을 업데이트 한다. 

6. T에 가장 가까운 점인 d를 T배열에 추가한다. T={c,b,f,a,d}. 그리고, a 에 연결된 각 점들의 가중치를 계산하여 D 배열을 업데이트 한다.

7. 마지막 점인 e를 T배열에 추가한다. T={c,b,f,a,d,e}. 

 

프림 알고리즘은 항상 T 밖에 있는 점을 추가하기 때문에 사이클이 만들어지지 않는다. 

 

4.3 최단 경로 찾기

📍다익스트라 알고리즘

1. 서울을 시작점으로 선택한다.

 

2. 연결된 노드까지의 거리를 업데이트하고, 그 중에서 최소값을 선택한다. 

3. 다익스트라 알고리즘은 출발점으로부터의 거리를 계산하는 것이기 때문에 (서울~천안) 거리를 더해서 논산, 대전 의 값을 계산한다. 원주 (15), 논산(16), 대전(22) 중에 원주가 최소값이므로 원주를 확정한다. 

 

4. 원주와 연결되어 있는 강릉과 대구의 값을 계산하고, 이 중에서 최솟값인 논산을 확정한다. 

5. 논산과 연결되어 있는 값들을 살펴보자. 논산에서 대전으로 가면 '논산 16+3=19' 이므로 기존 값인 22보다 작다. 값을 업데이트 해준다.  이후에, 최소값인 대전을 확정한다. 

 

6. 대전과 연결되어 있는 값들을 살펴본다. 대전에서 대구까지 10이므로 19+10=29이다.기존 값인 22보다 크므로 업데이트 하지 않는다. 남은 값들 중 가장 작은 값인 대구를 확정한다. 

 

7.  대구와 연결되어 있는 값들을 업데이트 해주고, 남은 값들 중 최소값인 광주를 확정한다. 

 

8. 광주와 연결된 값들은 값이 더 커지기 때문에 업데이트가 되지 않고, 가장 작은 값인 부산이 확정된다. 

9. 부산과 연결된 포항을 업데이트 해누면 강릉과 포항의 값이 동일하다. 순서 상관없이 남은 값들을 차례로 확정하면 알고리즘이 종료된다. 

4.4 부분 배낭 문제

1. 무게 당 가치 계산한다. 

2. 내림차순으로 정렬한다. 

3. 무게 당 가치가 높은 것부터 "전부" 배낭에 담는다. 만약 무게가 초과하게 된다면, "일부분" 만 배낭에 담는다. 

 

4.5 집합 커버 문제

 

집합 커버 문제(Set Cover Problem)는 주어진 전체 집합 U를 커버할 수 있는 최소한의 부분 집합들의 조합을 찾는 문제이다. 

 

학교를 설치하여 마을 전체를 커버하고자 할 때, 어느 위치에 설치하여야 학교의 수가 최소가 되는지 알아보자. 

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} // 신도시의 마을 10개

F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} // Si는 마을 i에 학교를 배치했을 때 커버되는 마을의 집합

• S1 = {1, 2, 3, 8}
• S2 = {1, 2, 3, 4, 8}
• S3 = {1, 2, 3, 4}
• S4 = {2, 3, 4, 5, 7, 8}
• S5 = {4, 5, 6, 7}
• S6 = {5, 6, 7, 9, 10}
• S7 = {4, 5, 6, 7}
• S8 = {1, 2, 4, 8}
• S9 = {6, 9}
• S10 = {6, 10}

가장 단순한 해결 방법은 집합 F에 포함된 모든 집합들의 조합을 생성하고, 이 조합들이 전체 집합 U를 커버하는지를 일일이 확인하는 방식이다. 가령, F={S1,S2,S3}일 때 가능한 조합은 다음과 같다:

• 집합 하나만 사용하는 경우: S1, S2, S3 (총 3개)
• 집합 두 개를 사용하는 경우: S1∪S2, S1∪S3, S2∪S3 (총 3개)
• 집합 세 개를 모두 사용하는 경우: S1∪S2∪S3 (1개)

이처럼 최적해를 찾기 위해서는 최대 $2^n-1$ 번 검사를 해야 한다. n이 커지면 최적해를 찾는 것은 실질적으로 불가능하다. 따라서, 최적해를 직접 구하는 대신 최적해에 가까운 값을 제공하는 근사해 (approximation solution) 를 사용한다. 

 

4.7 허프만 압축

1. 입력된 문자들로 우선순위 큐를 생성한다. 우선순위 큐는 가장 작은 값을 가진 노드가 위로 온다.

삽입 연산은 새 원소를 큐의 끝에 추가한 뒤, 부모와 비교해 올라가며(heapify-up) 정렬한다. 그러면 T → G → C → A 순으로 정렬된다. 

 

2. 가장 작은 값을 가지고 있는 T를 제거한다. 삭제 연산은 root(최소값)를 제거한 후, 마지막 원소를 root로 옮기고 내려가며(heapify-down) 재정렬한다. 첫 단계에서는 제거를 2번 반복하여 T와 G를 삭제한다. Q에는 C와 A만 남는다. 

 

3. 제거한 두 값 T와 G를 더해 새 노드 (210) 만들고, 해당 두 값을 자식 노드로 만든다. 그리고 노드를 (210) Q에 삽입한다. 

4. 큐에서 최솟값인 C를 제거한다. 

5. 기존 값 (210) 과 C 를 더해 새로운 노드를 만든다. 그리고 새로운 노드 (480) 을 Q에 삽입한다.

5. Q에서 마지막 남은 값인 A와 480을 제거하고, A와 480을 이용해 새 부모 노드를 Q에 삽입한다.