[알고리즘 패러다임 - 3] Greedy

Greedy (탐욕적 알고리즘)

그리디는 경우의 수를 완성시킬 때, 지금 상황에서 가장 좋은 조각을 선택해 경우의 수 상태의 일부로 만들면서 경우의 수를 완성시키는 방식이다. 즉 탐욕적 선택으로 답을 완성시킨다. 성능이 뛰어나지만 최적해를 구한다고 보장할 수 없다.

동작 방식

1. 경우의 수를 완성시키기 위해 조각 하나를 선택해 상태의 일부로 설정, 이때 가장 좋은 조각을 선택한다. 이때 아래 두 가지 속성을 증명한다.
2. 나머지 상태도 1번과 같은 방식으로 구한다.

A) 탐욕적 선택 속성 : 우리가 선택한 가장 좋은 조각이 정답에 무조건 포함됨을 보인다. 귀류법으로 쉽게 증명할 수 있다.

B) 최적 부분 구조 : 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지를 증명한다. 대개의 경우 이 속성이 성립하는지는 자명하게 알 수 있다.