알고리즘(15) - 그리디 알고리즘 greedy algorithm

그리디 알고리즘

---

눈앞의 이익만 우선 추구하는 알고리즘을 총칭한다. 최적해를 찾을 수 있으면 찾지만, 없다면 그런대로 괜찮은 해를 찾아내는 것이 목표다. 이 때문에 대부분 최적해를 보장하지 못하지만 드물게 최적해를 보장하는 경우도 있다.

 

그리디 알고리즘으로 최적해가 보장되는 않는 예는 다음과 같다.

1. 이진트리 최적합 경로 찾기
2. 동전 바꾸기
3. 배낭 문제

최적해가 보장되는 예는 다음과 같다.

1. 최소 신장 트리 : prim, kruskal
2. 최단 경로 : 다익스트라
3. 회의실 배정 문제

 

여기서 몇가지를 뽑아서 설명하겠다.

 

동전 바꾸기

---

동전을 모아서 특정 액수를 만들되 동전의 개수를 최소로 하는 문제다.

다만 이 문제는 모든 동전의 액면이 일반적인 화폐의 유통과 같았을 때, 즉 500원, 100원, 50원, 10원일 때 그리디 알고리즘으로 인한 최적해가 보장된다.

하지만 그렇지 않은 경우엔, 그리디 알고리즘으로 최적해가 보장되지 않는다.

 

 

배낭 문제

---

넣을 수 있는 무게에 상한이 있는 배낭에 가치가 제각각인 물건들을 넣고 배낭에 넣은 물건의 총 가치가 최대가 되도록 하는 문제다. 그리디 알고리즘에서는 무게 당 가치가 가장 큰 물건부터 넣는다. 다만 이렇게만 하면 최적해가 보장되지 않고 물건을 잘라서 넣는다는 가정 하에 최적해를 보장할 수 있다.

 

 

 

최소 신장 트리

---

프림과 크루스칼 알고리즘으로, 최적해를 보장한다.

Prim(G,r){ //정점 r에서 시작, 최소신장트리를 구함
	S<-Q; //정점 집합
    T<-R; //간선 집합
	while(S != V){
    	S에서 V-S를 연결하는 간선들 중 최소 길이인 x,y를 찾는다. //그리디한 부분이다.
        간선 (x,y)를 T에 포함시킴;
        정점 y를 집합 S에 포함시킴;
       }
}