선택을 쌓는 방식
가능한 후보 가운데 정한 기준에 가장 좋은 것을 고르고 남은 문제를 진행한다. 큰 값을 먼저 택하는 규칙도, 작은 비용을 먼저 택하는 규칙도 가능하다. 탐욕적이라는 말만으로 선택 기준이 하나로 정해지는 것은 아니다.
동전 문제의 반례
동전 값이 1, 5, 7이고 각 동전을 충분히 쓸 수 있다고 하자. 합계 10을 가장 큰 동전부터 만들면 7+1+1+1로 네 개다. 하지만 5+5는 두 개다. 큰 동전 우선 규칙은 이 체계에서 최소 개수를 보장하지 않는다.
정확성을 보이는 일
올바른 탐욕 선택을 하면 나머지 문제에서도 최적해를 완성할 수 있음을 보여야 한다. 최적해의 일부를 탐욕 선택으로 바꾸어도 나빠지지 않는다는 교환 논증 등이 사용된다. 몇 입력에서 성공한 실험만으로 모든 입력의 최적성을 증명할 수는 없다.
다른 전략과 비교
동적 계획법은 여러 부분 문제의 결과를 저장하며 선택지들을 비교할 수 있다. 탐욕 알고리즘은 더 적은 선택만 검토해 효율적일 수 있지만 그만큼 선택 규칙의 근거가 중요하다. 빠르게 답을 만드는 것과 최적해를 보장하는 것은 별도 성질이다.
관련 문서
알고리즘 / 동적 계획법 / 최소 신장 트리 / 프림 알고리즘 / 크루스칼 알고리즘 / 다익스트라 알고리즘 / 반례 / 최적화