매 단계 무엇을 고를지 한 문장으로 고정한다. 동점 처리까지 같이 정한다.
GREEDY PROOF
그리디는 “좋아 보이는 선택”이 아니라 “증명된 선택 규칙”이다
후보 규칙을 세운 뒤 교환 논증과 반례 탐색을 통과해야 구현할 가치가 생긴다.
임의의 최적해를 현재 규칙 선택으로 바꿔도 최적성이 유지되는지 확인한다.
경계값, 역정렬, 동점 케이스에서 깨지는 입력이 있는지 일부러 만든다.
채택: 종료 시간이 빠른 회의처럼 남은 선택지를 줄이지 않는
규칙
폐기: 짧은 구간 우선처럼 직관은 강하지만 전역 최적을 보장하지
못하는 규칙