Greedy Algorithm

Greedy Algorithm (그리디 알고리즘, 탐욕 알고리즘) 은 문제를 작은 문제들로 나눈 후, 각 순간순간의 문제마다 최적의 결정을 택하는 알고리즘이다. 작은 문제들로 나누어 풀기 때문에, 일종의 DP (동적계획법) 문제의 예라고 생각할 수 있다.

작은 문제들에서 항상 최적의 결정을 한다고 해서, 결론적으로 그것이 최적의 결정이 된다는 것은 결코 보장할 수 없다. 따라서 개인적으로, 그리디 알고리즘을 이용하여 문제를 풀 때는 그 아이디어를 잘 정하는 것이 키 포인트라고 생각한다. 작은 문제들에서 항상 최적의 결정만을 택했을 때, 결론적으로도 그것이 최적의 결정이 되도록 풀이를 구상해야 한다.

그리디 알고리즘을 이용하는, 쉬운 문제와 어려운 문제를 하나씩 다루어 보려 한다. 가장 유명하면서 쉬운 문제는 ‘동전 문제’이다(Baekjoon 11407, 동전 0 문제). 주어진 단위의 동전들과 만들어야 하는 금액이 주어졌을 때, 필요한 동전 개수의 최솟값을 구하는 문제이다.
1원, 10원, 100원의 세 종류의 동전이 있고, 347원을 만들어야 한다고 생각하자. 해답이 100원 동전 3개, 10원 동전 4개, 1원 동전 7개를 사용한 14개라는 것은 분명하다. 이를 다음과 같이 생각한다. 347원에서, 최대한 100원짜리 동전을 사용한다. 최대 3개가 사용 가능하다. 이를 제외하면, 남은 47원에서는 10원짜리 동전을 최대한으로 사용한다. …
위와 같은 알고리즘을 적용한다. 이러한 알고리즘은 “동전의 단위가 서로 배수 관계에 있기 때문”에 사용 가능하다. ( 10 = 1 10, 100 = 10 10 ) 배수의 관계에 있지 않다면 위와 같이 그리디 알고리즘을 사용할 수 없다. 예를 들어 3원과 5원 동전이 주어진다면, 5원짜리 동전을 무작정 사용하다 원하는 금액을 아예 만들지도 못할 수 있기 때문이다.

이번에는 조금 어려운 예시를 생각해 보자. 꽤 널리 알려진 ‘회의실 배정 문제’이다(Baekjoon 1931, 회의실배정 문제). 시작하는 시간과 끝나는 시간이 정해진 회의들이 주어진다. 한 회의실에서 회의를 진행할 때, 겹치지 않도록 회의를 고를 때 회의의 최대 개수를 구해야 한다.
그리디 알고리즘을 이용한 간단한 아이디어로, 매 순간마다 가장 빠르게 시작하는 수업을 택하는 방법을 생각해 볼 수 있다. 그러나 그 경우에는 다음과 같을 때를 해결할 수 없다: 세 회의 (1, 10), (2, 8), (9,11)가 주어졌을 때, (2,8)과 (9,11)을 택하는 경우가 최댓값이지만 위 알고리즘에 따르면 (1,10)을 택하게 된다.
본 문제를 해결한 필자의 아이디어는 “회의가 끝난 시점마다 종료 시간이 가장 이른 회의를 선택” 하는 것이었다. 위와 같이 구상하여 그리디 알고리즘을 사용하면, 모든 경우에서 해답을 찾아낼 수 있다. (증명도 귀류법으로 가능하다.) 이와 같이 그리디 알고리즘을 사용하여 문제를 해결할 때는, 그 아이디어를 구상하는 것이 중요하다.

---

Baekjoon 11407, 동전 0 문제
Baekjoon 1931, 회의실배정 문제
Baekjoon 1931, 회의실배정 필자의 코드