알고리즘 정의
그리디(탐욕) 알고리즘은 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 최적이지만, 그 선택들을 계속 수집하여 최종 답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역(Local)적으로 최적이면서 전역(Global)적으로 최적인 문제들이다.
아래 두 가지 조건이 만족하는 경우 탐욕 알고리즘이 잘 작동한다고 정의한다.
-
탐욕스런 선택 조건 (greedy choice property)
-> 앞의 선택이 이후의 선택에 영향을 주지 않는다. -
최적 부분 구조 조건 (optimal substructure)
-> 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해
대표적인 문제
그리디 알고리즘의 대표적이 문제는 아래와 같은 거스름돈 문제입니다.
Q. 음식점의 계산을 도와주는 점원이 500원, 100원, 50원, 10원의 4가지 종류의 동전을 가지고 손님에게 N원을 거슬러 줘야 하는 경우 거슬러 주어야 하는 동전의 최소 개수를 구하시오
위의 문제가 그리디 알고리즘의 두 가지 조건이 만족하는지 생각해보자. 만약, 610원을 거슬러 줘야 한다고 가정하면 아래와 같은 방법으로 선택하게 됩니다.
| 단계 | 남은금액 | 선택 | 누적 |
|---|---|---|---|
| 1 | 610원 | 500원 | 500원 x 1 |
| 2 | 110원 | 100원 | 500원 x 1, 100원 x 1 |
| 3 | 10원 | 10원 | 500원 x 1, 100원 x 1, 10원 x 1 |
각 단계의 선택이 이후 선택에 영향을 주지 않고 (탐욕스런 선택 조건), 각 단계의 최적해가 전체 문제의 최적해와 일치합니다. (최적 부분 구분 조건)
주의점
그리디 알고리즘의 최적해는 그 해답이 궁극적으로 최적이라는 보장은 없다. 그러므로 항상 최적해를 주는지를 반드시 검증해야 한다.
위 예시를 보았을때, 첫 번째 단계에서 50원을 선택하게 된다면, 이후 단계에서 100원 단위를 맞추기 위해 50원을 하나 더 집거나 10원을 5개 집어야 하므로 최적해가 도출될 수 없음을 증명할 수 있다.
레퍼런스
