Greedy는 영어로 탐욕스러운, 욕심 많은이라는 뜻을 가지고 있다. 그러니까 Greedy Algorithm은 탐욕스러운 알고리즘…? 뭐 이런 뜻이란 소린데, 뭔가 이상하게 들리겠지만, 사실이다. DP의 Dynamic은 DP의 특성과 전혀 연관성이 없지만, Greedy Algorithm의 Greedy는 진짜로 Greedy한 방식으로 알고리즘을 설계하는 방식이다.
그렇다면, Greedy한 방식이란 무엇일까? 결론부터 이야기하자면, Greedy Algorithm은 프로그래밍의 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 간단한 방법처럼 보이지만, 여기에는 몇 가지 대가(?)가 존재한다.
이 시점부터 설명의 편의를 위해 별도의 설명이 없는 이상 Greedy는 Greedy Algorithm을 지칭하는 것으로 하겠다.
Greedy는 사용되는 경우가 좀 제한된다. 크게 다음의 두 가지 경우가 있다.
(i) Greedy를 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우. 이 경우 DP보다 수행 시간이 훨씬 빠르기 때문에 사용할 가치가 충분하다.
(ii) 시간이나 공간적 제한으로 인해 DP를 비롯한 방법으로 최적해를 찾기 어려운 경우. 이 경우는 최적해 대신 적당히 괜찮은 답을 찾는 것으로 타협하고 Greedy를 사용하면 어느 정도 근사한 정답을 도출할 수 있다.
보통 Greedy를 사용하는 경우는 (i)인 경우가 많다.
활동 선택 문제(Activity Selection Problem)은 Greedy가 유용하게 사용되는 문제이다.
회사에 회의실이 하나밖에 없는데, $n$개의 팀이 회의하고 싶은 시간을 다음과 같이 제출했다고 하자. 두 팀이 회의실을 같이 쓸 수는 없기 때문에, 이 중 서로 겹치지 않는 회의들만을 골라서 진행해야 한다. 우리는 최대 몇 개나 선택할 수 있을까?
점선으로 구분된 눈금 한 칸이 1개의 시간 단위를 나타낸다고 가정하자.
물론 이러한 유형의 문제는 여러 개의 답을 가질 수 있다. 어쨌든, 진행하는 회의가 겹치지만 않게 만들면 되니까. 우리는 그중에서 가장 짧은 시간을 가지는 회의들의 조합을 고르면 된다.
그렇다고 이 문제를 브루트포스로 풀었다가는 $n$개의 회의에 대해 $2^n$개의 경우의 수를 다 따져야 한다. 그럴 바엔 회의실을 더 만드는 게 더 빠를지도…