[문제 해결 알고리즘] 그리디 알고리즘 ①

1. 그리디 알고리즘

 (1) 그리디 알고리즘 : 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 = 최적화 문제 해결에 사용

  * 최적화 문제 : 가능한 해들 중에서 가장 좋은 (최대 혹은 최소) 해를 구하는 문제

  * 근시안적인 선택 : 데이터 간의 관계를 고려하지 않고 수행과정에서 욕심내어 최소값 또는 최대값을 가진 데이터를 선택

   > 부분적 최적해를 찾고 이를 모아서 문제의 최적해를 얻음

  * 일반 선택하면 절대로 번복하지 않음

  * 제한적인 문제들만 그리디 알고리즘으로 해결 가능함

 (2) 예시 ⓐ : 동전 거스름돈 문제

  > 거스름돈이 주어졌을 때, 동전의 개수가 최소가 되도록 거스름돈을 주는 방법

  * 남은 액수를 초과하지 않는 조건 하에 가장 큰 액면의 동전을 취하는 것

  > 거스름돈 660원에 대해 그리디 알고리즘 적용

  * 500/100/50/10원 종류가 있을 경우, 500 1개, 100 1개, 50 1개, 10 1개가 최적

  * 500/120/100/50/10원 종류가 있을 경우, 500 1개, 120 1개, 10 4개

  == 항상 최적의 답이 아님

  == 최적이라고 생각했던 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 최적이라는 보장이 없음 

  == 반드시 검증이 필요함

2. 크루스칼 알고리즘

  (1) 크루스칼 알고리즘 : 최소 신장 트리(Minimum Spanning Tree) 

   - 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리

   - 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결시키면 됨

   - 그래프의 점의 수가 n이면 신장트리에는 정확히 n-1개의 선분이 있음

   * 트리에 선분을 하나 추가시키면 사이클이 만들어짐

   - 최소 신장 트리를 찾는 대표적인 그리디 알고리즘

   ⓐ 크루스칼 알고리즘 : 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 그 선분을 추가시켜 최소 신장트리를 구성함

   ⓑ 프림 알고리즘 : 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, 선분을 하나씩 추가시켜 트리를 만듦

   >> 두 알고리즘 모두 최소비용으로 전화선로, 송유관로, 배수로 등을 설치하는데에 활용

  (2) KruskalMST(G) 함수의 이해

   - 입력 : 가중치 그래프 G = (V, E), |V| = n, |E|=m

   - 출력 : 최소신장트리 T

   ⓐ 가중치의 오름차순으로 선분들을 정렬하고, 정렬된 선분 리스트를 L이라고 함

   ⓑ T = []

   ⓒ while(len(T) < n-1) {

   ⓓ L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거

   ⓔ if(선분 e가 T에 추가되어 사이클을 만들지 않으면)

   ⓕ e를 T에 추가 }

   ⓖ else { e를 버림 }

   ⓗ return 트리 T

 (3) 시간 복잡도 계산

  - Line 정렬 O(n)

  - T 초기화 O(1)

  - 최악의 경우 while이 m번 수행 : L로부터 가져온 선분 e가 사이클을 만드는지 검사하는데 O(logm) 시간 소요

  = O(mlogm) + O(mlog*m) = O(mlogm)

3. 프림 알고리즘

 (1) 주어진 가중치 그래프에서 임의의 점 하나를 선택한 후 선분을 하나씩 추가시켜 트리를 만듦

  - 추가 되는 선분 : 현재까지 만들어진 트리에 연결시킬 때 항상 최소의 가중치로 연결되는 선분

  - 배열(최저 길이만 저장) D[p] = 0, 점 v와 T의 속한 점들을 연결하는 선분들 중에서 최소 가중치를 가진 선분의 가중치를 저장함 

 (2) PrimMSG(G)의 이해

  - 입력 : 가중치 그래프 G = (V, E), |V| = n |E| = m

  - 출력 : 최소 신장 트리 T

  ⓐ 그래프 G에서 임의의 점 p를 시작점으로 선택하고 D[p]=0으로 놓음

   // 배열 D[v]는 T에 있는 점 v와 u를 연결하는 선분의 최소 가중치를 저장함

  ⓑ for(점 p가 아닌 각 점 v에 대하여)

  ⓒ if(선분 (p,v)가 그래프에 있으면)

  ⓓ D[v] = 선분(p,v)의 가중치

  ⓔ else { D[v] = 무한대 }

  ⓕ T = {p}

  ⓖ while(T에 있는 점의 수 <n)

  ⓗ T에 속하지 않은 각 점 v에 대하여 D[v]가 최소인 점 vmin과 연결된 선분(u, vmin)을 T에 추가함

      단, u는 T에 속한 점이고, 점 vmin도 T에 추가함

  ⓘ for(T에 속하지 않은 각 점 w에 대하여){

  ⓙ if(선분 vmin, w)의 가중치 < D[w])

  ⓚ D[w] = 선분(vmin, w)의 가중치 }}

  ⓛ return T

 (3) PrimMST 알고리즘의 최종적으로 리턴하는 T에는 왜 사이클이 없을까?

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

 (4) Prim 시간 복잡도

  - while 루프가 n-1번 반복되고, 1회 반복 시 T에 속하지 않은 각 점 v에 대하여 최소인 점을 찾는데 O(n) 시간 걸림

  = (n-1)O(n) = O(n^2)

4. 크루스칼 알고리즘 vs 프림 알고리즘

 - 연결된 그래프에서 간선의 개수 m은 다음 범위를 가짐 > n -1 <= m <= n(n-2)/2

	Sparse Graph	Dense Graph
프림	O(n^2)	O(n^2)
프루스칼	O(nlogn)	O(n^2logn)

4. 다익스트라 알고리즘

 (1) 최단 경로 찾기 문제 : 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지 최단 경로를 찾는 무제

 (2) ShortestPath(G, s)

  - 입력 : 가중치 그래프 G = (V, E) |V| = n |E| = m

  - 출력 : 출발점 s로부터 n-1개의 점까지 각각 최단 거리를 저장한 배열

  ⓐ 배열 D를 모두 무한대로 초기화 시킴

      배열 D[s] = 0으로 초기화

  ⓑ while(s로부터 최단거리가 확정되지 않은 점이 있다면) {

  ⓒ 현재까지 s로부터 최단거리가 확정되지 않은 각 점 c에 대해서

      최소의 D[v]를 가진 점 vmin을 선택하고 출발점 s로부터 vmin까지의 최단 거리 D[vmin]을 확정시킴

  ⓓ s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신함

  ⓔ return D

 (3) 시간 복잡도 : while루프가 n-1번 반복, 1회 반복 시 최소의 D[v]를 가진점 vmin을 찾는데 O(n) 소요

   - vmin에 연결된 점의 수가 최대 n-1개 이므로 각 D[w]를 갱신하는데 걸리는 시간은 O(n) 시간임

   = n-1 * {O(n)+O(n)} = O(n^2)