후보 규칙
가장 빨리 끝나는 회의, 가장 작은 간선처럼 선택 규칙을 한 문장으로 고정합니다.
Greedy Proof
그리디 정당성 증명
그리디는 "지금 고른 선택"이 어떤 최적해에도 포함될 수 있음을 보여야 합니다. 반례 탐색, 교환 논증, invariant가 결정적 증거입니다.
탐욕 선택을 증명하는 순서
exchange proof반례 탐색
동전 1, 3, 4에서 큰 동전 우선이 6원을 4+1+1로 만드는 식의 반례를 먼저 찾습니다.
교환 논증
임의의 최적해 첫 선택을 그리디 선택으로 바꿔도 비용이 나빠지지 않음을 보입니다.
부분 문제
첫 선택 뒤 남은 문제가 같은 형태의 최적 부분 구조를 유지하고, invariant가 다음 단계에서도 보존되는지 확인합니다.
그리디 규칙counterexampleexchangeinvariantvalid
그리디가 안 되면 대개 "지금 최선"이 미래 선택지를 망칩니다. 반례가 있으면 DP나 탐색으로 바꾸고, 없더라도 교환 논증으로 닫아야 합니다.