그리디 알고리즘 : 매 순간 최적의 해를 선택한다.

 greedy는, 욕심쟁이라는 뜻입니다. 이름에 걸맞게, 매 순간 제일 매력적인 해를 택하는 방법입니다. 그런데 그게 best한 답일까요? 답은 그럴 수도 있고 아닐 수도 있다는 것입니다. 오늘은 이러한 approach로 풀 수 있는 문제 중에서 쉬운 문제만 소개해 드리도록 하겠습니다.

 

 

---

 작업 n개가 주어집니다. 이들을 끝내는 데 걸리는 시간이 있습니다. 각각 T(1), ... ,T(n)이라고 합시다. 우리는 제한시간 limit 내에 최대한 많은 작업을 끝내려고 합니다. 어떻게 하면 좋을까요? 직관적으로 생각했을 때, 선택하지 않은 작업들 중에서, 소요 시간이 제일 짧은 작업들을 매 순간마다 선택하면 될 거 같습니다.

 

 그러면 T 배열을 정렬하면 될 겁니다. 예를 들어 T = [2, 5, 1, 3, 7] 이라고 한다면 아래와 같이 될 겁니다.

 

 

 

 그 다음에 어떻게 하면 될까요? 제한 시간 limit가 12라고 해 봅시다. 그러면 앞에서부터 누적합을 시켜 가면 됩니다.

 

 

 먼저 1 하나를 선택했습니다. 그러면 선택한 작업의 총 작업 시간은 1입니다.

 

 

 다음에 2를 선택합니다. 그러면, 총 시간은 3이 됩니다. 이것은 limit인 12보다 작거나 같습니다. 계속 탐색합니다.

 

 

 쭉 search를 해 볼까요? 1, 2, 3, 5짜리를 택했습니다. 그러면 총 시간은 11입니다. 이것은 12보다 작거나 같으므로, 계속 탐색해도 됩니다.

 

 

 

 그런데 7까지 선택하면 어떤가요? 18은 limit인 12보다 큽니다. 따라서, 이 때는 안 됩니다. 제한 시간인 12 내에 할 수 있는 작업의 최대 갯수는 4개임을 알 수 있어요. 이 과정을 되짚어 봅시다.

 

 

 1만큼 걸리는 작업을 선택했습니다. 그러면 select 할 수 있는 작업들의 시간은 각각 2, 3, 5, 7입니다. 두 번째로 어떤 것을 택했나요? 2만큼 걸리는 것을 선택했습니다. 그 순간에 select 할 수 있는 것 중에서 가장 적게 걸리는 작업을 선택했습니다. 그 순간에 가장 최적인 해를 선택한 셈입니다. 그리고, 그렇게 선택하는 전략이, 최적의 해를 보장합니다.

 

 

---

 왜 그럴까요? 직관적으로 생각하면 당연한 것이지만, 증명을 해 보도록 하겠습니다. T 오름차순으로 정렬했다면, i<j라면 T(i)보다 T(j)가 같거나 크다는 것이 자명합니다.

 

 

 그런가요? 다음에 한 가지 제약 조건을 더 걸겠습니다. T(x)를 택하고, T(y)를 택했다고 했을 때, x<y여야 합니다. 예를 들어서 T(2)를 처음에 선택했다면, T(1)이나 T(0)은 선택할 수 없습니다. 0은 2보다 크지 않고, 1도 2보다 크지 않기 때문입니다. 즉, 우리는 3번을 택하고 1번을 택하고 2번을 택하는 것을, 1번을 택한 다음에 2번을 선택하고, 그 다음에 3번을 선택한 것으로 보겠다는 것입니다.

 

 그러면 처음에 T(0)을 선택하는 것이 이득일까요? 아니면 T(1)을 선택하는 게 이득일까요? 제한 시간을 limit라고 해 봅시다. 그러면, T(0)<=T(1)이기 때문에, limit-T(0)>=limit-T(1)이 됩니다. 즉 T(0)을 선택했을 때, 남은 제한 시간이 T(1)을 선택했을 때 남은 제한시간보다 같거나 큽니다.

 

 

 그럼에도 불구하고 T(1)을 선택하는 게 더 이득이라 생각이 들 수도 있어요. 하지만 그렇지 않습니다. 왜냐하면, T(1)을 선택했을 때, 선택할 수 있는 스케쥴은 {T(2), ... , T(n-1)}입니다. 이를 집합 A라 합시다. 그런데 T(0)을 선택했을 때에는 어떤가요?

 

 

 선택할 수 있는 집합이 {T(1), ... , T(n-1)}입니다. 이를 B라고 합시다. 당연하게도, T(1)을 택했을 때 선택할 수 있는 집합인 A를 집합 B가 포함하고 있는 구조입니다. T(0)을 선택했을 때, 선택할 수 있는 선택지가, T(1)을 선택했을 때 선택할 수 있는 선택지를 포함하고 있는 셈입니다. 다시 말하면, T(1)을 택했을 때 이득이 없는 상황입니다. 따라서, T(0)을 선택하는 것이 이득입니다.

 

 

 마찬가지로 생각해 봅시다. {T(0), ... , T(n-1)}의 부분 수열 {T(1), ... , T(n-1)}이 있다고 해 봅시다. 그러면 T(1)을 선택하는 게 이득일까요? T(2)를 선택하는 게 이득일까요? 일단 T(1)<=T(2)이기 때문에, T(1)을 선택한다면 남는 제한시간이 T(2)를 select 했을 때 보다는 더 클 겁니다.

 

 

 그 다음에 T(1)을 선택하면 어떤가요? 다음에 선택할 수 있는 후보해 집합이 {T(2), ... , T(n-1)}가 있습니다. 이를 집합 C라고 합시다. T(2)를 pick 하면 어떤가요? 당연하게도 그런 경우 다음에 T(1)을 뽑을 수 없습니다. 제약 조건 때문입니다.

 

 

 그러면 {T(3), ... , T(n-1)} 중에서 뽑아야 할 건데요. 이를 집합 D라 하겠습니다. D가 C에 포함이 됩니다. 이 이야기는 다시 말하면, D에서 어떻게 어떻게 잘 뽑아서 최적해를 만들었다 하더라도, 그 해가 C에 포함이 된다는 소리입니다. 즉, T(2)를 택했을 때, T(1)을 택하는 것 보다 이득이 없는 상황입니다.

 

 따라서 T(1)을 선택하는 것이 이득입니다. 마찬가지로 생각을 한다면, T(0)부터 T(1), T(2), ... 순으로 select 하는 것이 이득임을 알 수 있고, 이것이 최적해입니다. greedy 접근법이 성립합니다.

 

 

 따라서, T배열을 오름차순으로 sort 하고, T(i)>limit인 최초의 i를 찾으면 됩니다.