Chap 4. Greedy Approach

- Greedy Approach 는 말 뜻 그대로, 욕심이 많다. 미래를 생각하지 않고 현재만 생각(Locally optimal)

- ex) 우리나라 동전은 Greedy Approach로 큰 화폐 단위로부터 locally optimal하게 고르면 잘 골라짐

 

- MST는 minimum Spanning Tree의 약자로, 최소 weight로 모든 node를 연결하는 트리 형성하기

(참고로 Spanning tree는 1) Sub graph, 2) Cover vertex, 3) Tree 의 조건을 만족해야함)

- MST를 만드는 대표적인 두 가지 방법 Prim 알고리즘, Kruskal 알고리즘

- Prim's Alg 는 출발 노드(1)로 부터 가장 작은 값을 고르고, 또 연결된 노드를 포함하여 연결되있는 edge중 가장 작은 값을 추가하면서 n-1개의 edge를 구성할 때 까지 반복한다

- Programming 하려면 구조체 자료형 필요(From, To, Distance), 추가적으로 똑같은 weight 변경하지 않는다(GA)

- 시간복잡도는 O(n^2), Adjacency Matrix 비용

- 이것이 최소 MST인지 증명은 공집합으로부터 시작, 귀납법으로 최소만 담으므로 끝까지 MST

 

- Kruskal은 전체 엣지를 Weight로 정렬하여 가장 작은 것만 추가하는데 이 때, Cycle이 형성되지 않도록 Disjoint set Forest를 활용하여 추가해준다(같은 root는 cycle 형성)

- Disjoint set Forest에서는 Parent 배열을 선언해주고, 높이가 최소화되는 방향으로 결합하기(Root까지 올라가서 더 큰것에 작은 것 달기)

- 시간복잡도는 O(ElogE) Edge 정렬 하는데 드는 비용

 

- DijkStra's Algorithm 은 SSSP(Single Source Shortest Path) 구하는 법(Floyd는 AFSP)

- Greedy Approach로 현재 Locally Optimal

- 핵심 아이디어는 출발지로부터 Length에 경로 길이 등록 후, 최단 경로로 선정된 near를 다음 경로 탐색에서 활용

- near를 거쳐가는게 빠른지 비교하여 Length 갱신하기, T에는 최단 경로의 부모 기록해두기(어디로부터 온것인지)

 

 

- Bellman-Ford's Alg도 마찬가지로 SSSP 해결법이나 DP을 활용한다

- K 개수 이하의 edge를 활용하여 거쳐가는 DP를 통해 해결한다

- 총 개수가 n이 넘지 않아야 Cycle이 형성 안된 것이므로 k를 n-1까지 반복

- 다음의 공식을 통해 DP 해결

 

- 두 알고리즘의 비교