1. 그리디 알고리즘 정당성 증명 "매 순간 내리는 선택을 포함하는 최적해가 반드시 존재한다"를 증명하면 된다. 늘 그렇듯 기초가 가장 중요하므로, 쉬운 문제들을 예시로 삼아서 그리디 알고리즘의 정당성을 어떻게 증명하는지 한 번 살펴보도록 하자. 2. 백준 1931번 문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 종료 시간이 가장 빠른 회의를 m이라고 하자. 이때 m이 최적해에 포함되지 않는다고 가정하자. 그러면 최적해의 회의들 중 종료 시간이 가장 빠른 회의를 m으로 대체하여 또 다른 최적해를 얻을 수 있다. 따라서 m을 포함하는 최적해는 반드시 존재한다. 그러면 이제는 m을 선택했다는 가정 하에 m을 제외한 나머지..
