[1. 개요]
완전 탐색, 동적 계획법과 같이 전체 문제를 여러 개의 부분 문제로 나누고,
각 부분 문제를 해결하는 것 까지는 같으나,
각 단계마다 지금 당장 좋은 방법만을 선택한다는 것에서 다르다.
즉, 현재 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.
탐욕법을 사용하는 경우
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
=> 이때는 완전 탐색, 동적 계획법 등으로 풀 수 없는 경우라고 볼 수 있다.
=> 보통 완전탐색, 동적 계획법으로 구현 시 제한 시간 이내로 풀 수 없는 경우.
=> 약간의 직관력이 필요하다.
탐욕 알고리즘에 대한 증명은 보통 일정한 패턴을 갖는다.
- 탐욕적 선택 속성
=> 탐욕적 선택을 해서 손해 볼 일은 없다.
=> 귀류법을 사용하여 증명 - 최적 부분 구조
=> 부분 문제의 최적해로부터 전체 문제의 최적해를 만들 수 있다.
탐욕적인 선택이 틀려서, 전체 답이 틀릴 수 있다.
=> 탐욕적인 선택을 완전히 다른 관점에서 생각 해 볼 필요가 있다.
=> 회의실 배정 같은 문제..
보통 특정 조건으로 객체들을 정렬해두면 탐욕법 구현이 쉬워지는 경우가 있다.
[2. 예제]
