탐욕법

탐욕법(Greedy method)

그때 그때 가장 최적의 해를 취하여 전체의 큰 해를 만드는 방법이다.

탐욕법 사용 조건

탐욕 선택 속성(Greedy Choice Property)

각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우이다.

최적 부분 구조(Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 구조를 말한다.

설계 절차

선정 과정(selection procedure)

현재 상태에서 가장 좋으리라고 생각되는 해답을 찾아서 해답모음(solution set)에 포함한다.

적정성 점검(feasibility check)

새로 얻은 해답모음이 문제의 조건을 만족하는 지 확인한다.

해답 점검(solution check)

새로 얻은 해답모음들이 ‘최종 선택’이 ‘문제의 조건을 만족’하는지 확인한다. 이러한 해답 점검 부분이 가장 어렵다.

해답 증명법들

Greedy Stays Ahead

직역하면 탐욕적인 것이 가장 앞선다이다. 어떤 최적 알고리즘을 가정하여 해당 조건을 나열했을 때 탐욕적인 방법으로 제시한게 그보다 낫거나 같은 조건을 만족할 경우 해당하는 탐욕 알고리즘은 최적 알고리즘이 되는것이다.

Certificate argument

직역하면 증거논의이다. 알고리즘이 답과 함께 그 답이 최적해라는 증거를 함께 출력하도록 만드는 방법이다.

Exchange Argument

직역하면 교환 논의이다. 가상의 최적해를 하나 고정하고, 최적해가 나빠지지 않게끔 조금씩 조정하면서 탐욕 알고리즘의 답과 동일하게 맞추는 방법이다.

* 알림

여기에 직접 증명을 적자니 너무 길어지고 오래걸려서 추가적인 포스팅으로 해당 증명법에 대해서 예시를 들어 보일 것이다.

탐욕법을 적용하기 좋은 경우

탐욕법을 적용하면 좋은 몇가지 경우들이 있다. 대부분 동적계획법을 사용하면 풀수는 있지만 짧은 시간내에 해가 산출되는게 보장이 안되는 경우이다.

탐욕 알고리즘을 적용한 예시 문제

• 프림 알고리즘
• 크루스칼 알고리즘
• 다익스트라 알고리즘
• 플로이드 워셜
• 허프만 코드
• 거스름돈 문제

참고 자료

• Gazelle and Computer Science
• Contributor9
• Guide to Greedy Algorithms