탐욕법 (greedy algorithm)

* 탐욕법 (greedy algorithm)

: 현재 상황에서 "당장 눈앞에 보이는 최적의 상황" 만을 선택하는 알고리즘
최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많음

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달
그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없음

=> 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들
ex. 거스름돈 문제


* 탐욕 알고리즘 접근 방법
1. 방법 고안 : 어떤 것을 선택할지 알고리즘을 고안
2. 정당성 확인 : 항상 최적의 해를 보장하는지 확인, 증명


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


* 탐욕 알고리즘 적용 조건
1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않음
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성