Greedy Algorithm

Greedy? 사전적 의미로는 "탐욕스러운, 욕심 많은" 이라는 뜻이다.

말 그대로 탐욕 알고리즘은 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫒아 최종적인 해답에 도달하는 방법이다. 이러한 탐욕 알고리즘의 문제 해결법을 보다 단계적으로 나누어 본다면 다음과 같다.

1. 선택 절차(seletion procedure) : 현재 상태에서의 최적의 해답을 선택

2. 적절성 검사(Feasibility check) : 선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사(Solution check) : 원래 문제가 해결 되었는지 검사하고 , 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복한다.

이처럼 탐욕 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 그래프나 정렬, 유명한 다익스트라(Dijkstra) 알고리즘까지 폭넓은 영역에서 사용된다.

최소비용 신장 트리 : 그래프 내의 모든 정점을 최소 비용으로 연결하는 트리
Kruskal 알고리즘 : 최소비용 신장 트리를 만드는 알고리즘 중 탐욕 알고리즘을 이용한 풀이

탐욕 알고리즘은 문제를 해결하는 과정에서 그 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다, 하지만 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다

따라서 탐욕 알고리즘을 사용하려면 문제가 아래의 2가지 조건을 성립하여야 잘 작동합니다. 즉, 아래의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못합니다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.

항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적해에 근사한 값을 빠르게 도출할 수 있는 장점이 있기 때문에 근사 알고리즘으로 사용이 가능합니다.