탐욕 알고리즘 (Greedy algorithm)

탐욕 알고리즘은 주어진 순간에 가장 최적의 경우를 선택하는 알고리즘이다.

다시 말해, 현재 단계 관점에서 최선의 결정을 선택하는 것이다.

따라서 지역적으로 최적을 선택하는 것이기 때문에, 문제에 따라, 최선의 접근법이 아닐 수도 있다. 

 

만약 탐욕 알고리즘은 최선의 해를 내놓는다면, 보통 동적 프로그래밍(dynamic programming)이나 완전 탐색보다 빠르다.

반대로, 최선의 해를 내놓지 못한다면, 동적 프로그래밍이나 완전 탐색이 최적의 접근법이 될 수 있다.

 

예시) 동전 교환문제

주어진 동전을 가지고, 주어진 금액을 지불할 수 있는 최소 동전 개수를 찾는 문제.

동전: [1, 2, 5]

지불 금액: 6

결과: 동전(1) 1개, 동전(5) 1개

 

이 문제는 동전이 어떻게 주어지냐에 따라, 그리디 알고리즘이 최적해를 내놓을 수도 있고, 안내놓을 수도 있다.

위에서 최적해를 내놓는 예시를 보았으니, 이번에는 최적해를 내놓지 못하는 예시를 보자.

 

동전: [1, 3, 4]

지불 금액: 6

최적해: 동전(3) 2개

그리디 알고리즘: 동전(4) 1개, 동전(1) 2개

 

그리디 알고리즘이 최적해를 내놓는지 판단하는 것은 매우 어려운 일이다.

첫째로, 탐욕 선택 속성(Greedy Choice Property) 증명이 필요하다.

탐욕 선택 속성이란? 지역적인 최적의 선택이 전체적으로도 최적해의 일부가 될 수 있음을 증명하는 것이다.

 

위의 예시로 얘기하자면, 동전[1, 2, 5] 중 동전(5)가 최적해에도 포함되는가?를 생각해 보는 것이다.

동전[1, 3, 4]도 마찬가지다. 동전(4)가 최적해에 포함되는가?를 생각해보면, 그리디 알고리즘을 쓸 수 있는지 없는지 판단할 수 있다.