탐욕법이란?

결정의 순간마다 당장의 최선이 되는 선택을 하여 해답에 도달하는 방법

절차적으로 본다면 다음을 단계적으로 수행한다.

1. 선택절차 : 현재 상태에서 최적의 해답 선택
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정 반복

예시 중 하나로는
최소비용 신장트리(Minimum Spanning Trees)를 Kruskal 알고리즘을 통해 구현 하는 것이 있다.

주의사항

그러나 탐욕법은 항상 최적의 결과를 보장하지 못한다.

탐욕 알고리즘을 사용하려면 문제가 다음의 2가지 조건을 성립하여야 한다. 즉, 이 조건을 만족하는 '특정한 상황'에서만 작동한다는 뜻이다.

1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.