알고리즘 문제 해결 8장 그리디(Greedy)

현재의 상태에서 특정한 값을 기준으로 가장 좋은 것을 선택해 나가는 방법

그리디 알고리즘으로 문제를 해결하기 위해서는 어떠한 반례도 없이 항상 최적의 결과를 얻을 수 있음이 입증되어야 함

1. 현재의 상태에서 가장 좋은 것을 선택하는 것이므로 그 선택의 기준이 되는 것을 정해야 한다.

   따라서 여러 가지 선택 기준 중에서 반례가 없는 기준을 찾아야 함

2. 어떤 값을 기준으로 했을 때 반례가 없다는 것이 입증이 되면 그 기준값을 기준으로 정렬하는 것이 필수임

3. 정렬이 되었다면 처음부터 차례대로 선택이 가능한 것을 모두 선택해 나가면 됨