그리디 선택 기준
종료 시간이 가장 빠른 회의처럼 목적 함수와 직접 연결된 기준이어야 합니다.
그리디 선택 증명
회의실 배정처럼 맞는 규칙과 동전 문제처럼 깨지는 규칙을 같은 절차로 통과, 보류, 폐기해야 합니다.
교환해도 최적성이 유지되는가
임의의 최적해를 선택 규칙을 따르는 해로 바꿀 수 있어야 채택합니다.
작은 입력 반례 검토
동전 `{1,3,4}`, 금액 6처럼 그리디와 DP 결과가 갈리는 입력을 확인합니다.
통과
교환 논증과 반례 세트가
모두 선택 규칙을 지지합니다.
보류
샘플은 맞지만 증명 문장이 비어 있으면 DP나 탐색 대안을
비교합니다.
폐기
작은 반례 하나라도 나오면
빠른 구현보다 정확한
최적화 방법을 택합니다.