1주자 Greedy Algorithm

1. Greedy Algorithm이란?

선택을 해야될 때 마다 그 순간에 최선의 선택을 하면서 문제를 해결하는 방법
순간마다 하는 선택이 최적이지만 그 선택을 해나가면서 해결한 최종 답이 최적이라는 보장은 없다. 
하지만 이 알고리즘을 적용하는 문제들은 지역적으로(순간마다) 최적이면서 전역적으로(최종 답) 최적인 문제들이다.

 

 

2. Kruskal Algorithm이란?

Greedy한 방법으로 undirected connected weighted 그래프에서 모든 정점을 최소 비용으로 연결하는 최적의 답을 찾는 방법 = Minimum Cost Spanning Tree를 찾는 방법

 

*Spanning Tree : Component가 1개인 그래프. (모든 vertex가 edge들로 이어져 있다.)

*Minimum Cost Spanning Tree : Spanning Tree 중 edge의 weight의 합이 가장 작은 tree
                                           이 트리는 여러 개 있을 수 있다. = unique하지 않다.

                                           이 트리의 edge의 수는 (vertex의 수 -1)이다.

 

1. 그래프의 edge와 edge의 weight을 쌍으로 우선순위 큐에 넣는다. 

-> 아무렇게나 집어넣어도 나올 때는 sort되어서 나온다. 가장 작은 것부터

2. 우선순위 큐에서 하나를 빼서 Spanning Tree의 edge의 Set T에다 집어넣는데 만약 T에 넣었을 때 사이클을 형성한다면 T에 집어넣지 않고 사이클을 형성하지 않는다면 T에 집어넣는다.

3. 2의 과정을 반복하는데 T의 크기가 그래프의 vertex의 수 - 1이면 멈춘다.

 

-> Set T의 원소들은 MCST의 edge들!

 

3. Greedy Algorithm으로 shortest path 구하기

Dijkstra's Algorithm : Greedy한 방법으로 directed connected weighted 그래프에서 모든 정점을 최소 비용으로 연결하는 최적의 답을 찾는 방법

 

 

1. 시작 vertex를 정해서 current vertex로 설정하고 시작 vertex를 Set T에 넣는다.

2. current vertex에서 Set T의 원소들로 각각의 vertex로 가는 최단 경로의 값을 구한다. 

3. 그 값들 중 가장 작은 값을 가진 vertex를 Set T에 추가한다.

4. 2, 3의 과정을 반복하는데 Set T의 크기가 그래프의 vertex의 수 - 1이면 멈춘다.