규칙 문장화
매 단계 무엇을 우선 고르는지 한 문장으로 고정한다.
그리디 규칙은 통과, 보류, 폐기로 나누어 채택한다
짧은 코드를 쓰기 전에 선택 규칙이 최적해를 보존하는지 작은 반례와 교환 논증으로 확인합니다.
최적해 교환
임의 최적해를 규칙 형태로 바꿔도 손해가 없는지 본다.
반례 압박
동점, 역정렬, 최소 입력으로 후보 규칙을 흔든다.
정렬 키 확정
통과한 규칙만 코드의 비교 함수로 옮긴다.
통과
가장 빨리 끝나는 회의
회의실 배정의 기본 규칙
교환 논증
첫 선택을 더 빨리 끝나는 회의로 바꿔도 이후 선택 가능 구간은 줄지 않는다.
반례 압박
같은 종료 시간은 시작 시간으로 묶고, 인접 구간은 포함한다.
폐기
가장 짧은 회의
직관은 좋지만 최적 보장 없음
깨지는 입력
짧은 회의 하나가 양쪽의 여러 회의를 막으면 전체 개수가 줄어든다.
교정
길이가 아니라 남은 시간을 최대화하는 종료 시각 기준으로 바꾼다.
조건부
가장 큰 동전부터 사용
동전 체계가 핵심 전제
반례
동전 [1, 3, 4]와 금액 6에서는 4+1+1보다 3+3이 더 적다.
대안
임의 동전 집합이면 최소 개수 DP를 기준 구현으로 둔다.