그럴듯한 선택과 보장된 선택
현재 가장 이득이 큰 선택을 하면 계산이 간단해질 수 있다. 하지만 그 선택 때문에 나중의 조합이 나빠질 수도 있다. 탐욕법이 맞으려면 그 문제에서 선택을 확정해도 최적해를 놓치지 않는 근거가 필요하다. 알고리즘의 이름이 아니라 선택 규칙과 문제의 성질이 정확성을 결정한다.
가상의 교환 단위
단위가 1, 3, 4일 때 합계 6을 최소 개수로 만드는 문제를 생각하자. 큰 단위부터 고르면 4와 1과 1로 세 개가 되지만 3과 3은 두 개다. 이 반례는 그 단위 구성에서 큰 것부터 선택하는 규칙이 항상 최적은 아님을 보여 준다. 다른 단위 체계에서 성공한 직관을 그대로 옮기지 않아야 한다.
부분 문제를 정의하기
동적 계획법에서는 남은 합계나 처리한 항목 수 같은 상태를 정하고 가능한 전이의 결과를 비교할 수 있다. 같은 상태가 반복되면 계산한 답을 다시 사용한다. 다만 상태가 미래의 선택에 필요한 정보를 빠뜨리면 잘못된 부분 문제를 합치게 된다. 저장 공간을 쓰는 것 자체보다 상태의 의미와 전이의 완전성이 중요하다.
최적 부분 구조의 역할
전체 최적해와 부분 문제의 최적해가 어떻게 연결되는지 확인한다. 여러 선택을 비교하는 동적 계획법과 한 선택을 확정하는 탐욕법 모두 문제 구조를 이용하지만 확정할 수 있는 범위가 다르다. 탐욕 선택을 교환해도 손해가 없다는 식의 논증이나 상태별 최적값을 유지한다는 논증이 필요하다.
비용과 검증
동적 계획법도 상태 수가 너무 많으면 실용적이지 않을 수 있다. 탐욕법이 성립하는 문제라면 더 간결한 풀이를 얻을 수 있다. 작은 입력에서는 가능한 답을 모두 확인하는 방법과 비교해 반례를 찾는 것이 유용하다. 테스트는 근거를 보완하지만 모든 입력에 대한 정확성 증명을 자동으로 대신하지는 않는다.
관련 문서
동적 계획법 / 알고리즘 / 성능 비교 실험 설계