그리디 알고리즘 (탐욕법, Greedy Algorithm)

알고리즘 문제 해결 전략 p. 368

[탐욕법을 사용하는 이유]

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 훨씬 수행시간이 빠르므로 유용

2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면, 적당히 괜찮은 답을 찾는 것으로 타협할 수 있음. 탐욕법은 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 쓰임

[정당성의 증명]

-문제- 회의실 예약. 

회의 시간들이 주어졌을 때 가장 많은 회의를 열 수 있도록 회의실을 스케쥴링 한다.

- 탐욕법을 이용한 해결-

S = { 주어진 회의들 } = {s1, s2, ... }

1. 목록 S중 가장 일찍 끝나는 회의 s(min)를 선택한다.

2. S 중 s(min)과 겹치는 회의를 S에서 모두 지운다.

3. S가 텅 빌 때까지 반복한다.

-정당성 증명-

위와 같은 탐욕법이 성립하려면 다음 조건이 성립해야 한다.

가장 종료 시간이 빠른 회의 s(min)을 포함하는 최적해가 반드시 존재한다.

1. S의 최적해 중에 s(min)을 포함하지 않는 답(회의목록 : 끝나는 순서대로 {s1, s2,,, sk})이 있다고 가정하자.

2. 이 목록 중에서 s1을 지우고 s(min)을 추가해서 새로운 목록을 만들자.

3. s(min)은 S에서 가장 일찍 끝나는 회의이기 때문에, 남은 목록 {s2,,, sk}와 겹치치 않는다.

// s(min)보다 늦게 끝나는 s1이랑도 안겹쳤으니깐 s(min)과는 당연히 겹치지 않음

그리고 같은 수의 회의를 열 수 있으므로 이 목록도 최적해 중 하나다.

4. 따라서 항상 s(min)을 포함하는 최적해가 존재한다.

따라서 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없다.