[알고리즘] 그리디 알고리즘

---

그리디 알고리즘이란

그리디 알고리즘은 최적화 문제를 해결하는 알고리즘이다. 최적화 문제는 가능한 해들 가운데 가장 좋은(최대 또는 최소) 해를 찾는 문제이다. 

 

1. 그리디 알고리즘은 수행 과정에서 최솟값 또는 최댓값을 가진 데이터를 선택한다. 부분적인 최적해를 찾은 후, 이 부분해를 모아서 최적해를 얻는다.

2. 이 알고리즘은 선택한 데이터를 버리고 다른 것을 취하지 않는다.

 

---

동전 거스름돈 문제

 

거스름돈을 동전으로 받을 때 적은 수의 동전으로 거스름돈을 주어야 한다. 이 때 그리디 알고리즘을 활용한다면, 알고리즘은 액수를 초과하지 않는 조건 아래에 가장 큰 값의 동전을 취할 수 있다. 

 

알고리즘)

CoinChange(W)
input : 거스름돈 액수(==W)
output : 최소 동전의 개수
1. change = W   
2. x500=x100=x50=x10=0 //동전 개수를 담을 변수
3. while( change >= 500 )
	change = change - 500, 
  	x500++
4. while( change >= 100 )
	change = change -100,
    x100++
5. while( change >= 50 )
	change = change - 50,
    x50++
6. while( change >= 10 )
	change = change - 10,
    x10++
7. return (x500+x100+x50+x10)

 

---

최소 신장 트리

 

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

 

신장은 영어로 spanning이다. 신장 트리를 찾는다는 건 사이클 없이 모든 점을 연결시킨 트리를 찾는 것이다. 그래프의 점의 개수가 n이면 신장 트리에는 n-1개의 간선이 있다. 이 때 간선을 하나 추가하게 되면 사이클이 이루어 진다. 

 

최소 신장 트리를 찾는 그리디 알고리즘으로는 크리스컬과 프림 알고리즘이 있다.

 

크리스컬 알고리즘은 가중치가 가장 작은 간선이 사이클을 만들지 않을 때에만 그 간선을 추가시킨다. 

알고리즘)

KruskalMST(G)
input : G = (V,E) // V = n(점의 수) E = m (간선의 수)
output : T //최소 신장 트리 T
1. 가중치의 오름차순으로 간선들을 정렬한다. 정렬한 간선 리스트를 L이라고 한다.
2. while( T의 간선 수 < n-1 ){
	L에서 가장 작은 가중치를 가진 간선 e를 가져온다.
    e를 L에서 제거한다.
    if( 간선 e가 T에 추가되었을 때 사이클을 만들지 않으면 )
    	e를 T에 추가한다.
    else
    	e를 버린다.
        
   }
3. return T