탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms)

Photo by Kelly Sikkema on Unsplash

탐욕 알고리즘(greedy algorithm)은 매번 현재로써 최선인 선택을 "탐욕스럽게" 취하는 알고리즘 기법으로, 문제 해결 및 다양한 분야에서 활용되고 있습니다. 알고리즘의 동작이 매우 단순하기 때문에 상대적으로 간단히 구현할 수 있으며 매우 빠른 시간에 수행된다는 장점이 있죠. 하지만 반대로 탐욕 알고리즘이 최적해를 출력한다는 것을 보이는 것은 매우 어려운데요. 직관적으로는 매우 그럴 것 같지만 막상 그것을 증명하려고 하면 까다롭기 때문입니다.

 

이번 시간에는 분석하기 어려운 탐욕 알고리즘을 분석하는 일반적인 기법들을 몇 가지 소개해 보도록 하겠습니다. 구체적으로

• Greedy stays ahead
• Certificate argument
• Exchange argument

를 다룰 예정입니다. 각 기법에 대한 간단한 설명과 더불어 실제 백준 온라인 저지의 문제들을 통해 각 기법이 어떻게 적용되는지 살펴볼 것입니다.

 

개인적으로 포스팅할 때 영어로 된 명칭은 최대한 번역해보려고 노력합니다만, 이번에는 그게 너무 힘들어서 그냥 원래 이름을 그대로 사용하였습니다. 모쪼록 양해를 바랍니다.

Greedy Stays Ahead : 탐욕스러운 것이 항상 좋을 지니...

Photo by Raquel Martínez on Unsplash

첫 번째 기법은 'greedy stays ahead'입니다. 직역하자면, "탐욕 알고리즘이 항상 앞선다." 정도가 되겠습니다. 이 기법은 탐욕 알고리즘을 증명하는 다른 기법들에 비해 상대적으로 쉽고 간단합니다. 이것이 의미하는 바를 좀더 잘 이해하기 위해서는 다음과 같은 상황을 생각해 보면 좋습니다. 먼저 최적해를 출력하는 가상의 알고리즘을 하나 가지고 오도록 하겠습니다. 그러고는 최적 알고리즘이 매번 선택을 할 때 탐욕 알고리즘이 어떤 선택을 하는지 살펴보겠습니다. 만약 탐욕 알고리즘의 선택이 최적 알고리즘의 선택보다 항상 (어떤 기준에 따라) 좋다면, 전체적으로 봤을 때도 탐욕 알고리즘의 출력이 최적 알고리즘의 그것보다 좋다고 보일 수 있습니다. 그러니 탐욕 알고리즘이 내놓은 답이 최적해가 되는 것이죠.

 

구체적인 예시로 다음 문제를 생각해 봅시다. 우리는 여러 작업들을 처리해야 하며, 이를 위해 기계가 달랑 하나 주어졌습니다. 각 작업은 시작 시각과 끝 시각을 가지며, 만약 한 작업을 기계에 넣어 처리하려고 한다면, 해당 시작 시각부터 끝 시각까지는 다른 작업을 처리할 수 없습니다. 대신 한 작업이 끝나는 시각에 시작하는 작업은 곧바로 기계에 할당할 수 있습니다. 우리의 목표는 최대한 많은 수의 작업을 처리하는 것입니다. 아실 분들은 아실 테지만, 이 문제는 유명한 인터벌 스케줄링(interval scheduling)이며 백준 온라인 저지에도 이에 해당하는 [BOJ 1931] 회의실배정 문제가 있습니다.

 

이 문제를 해결하는 잘 알려진 알고리즘은 다음과 같습니다.

모든 작업을 끝나는 시각의 오름차순으로 정렬한 후, 각 작업을 순서대로 고려하면서 기계에 할당할 수 있으면 넣고 그렇지 않으면 버린다.

이 알고리즘을 시각화하면 다음 그림과 같이 됩니다.

그림 1. 첫 번째 알고리즘 동작 예시. 각 화살표의 왼쪽 끝이 작업이 시작하는 시각, 오른쪽 끝이 끝나는 시각을 의미한다.

처음 보시는 분들이라면 "이게 정말 되는 거 맞아?"라고 생각하실 수 있겠습니다. 매우 좋은 반응입니다. 알고리즘을 공부하실 때는 비판적인 시각을 견지하는 것이 매우 중요합니다. 그리고 놀랍게도, 이 알고리즘은 실지로 최적해를 출력하는 알고리즘입니다. 그에 대해 직관적인 설명을 먼저 해 보겠습니다. 모든 작업을 끝나는 시각으로 정렬하고 그 순서대로 고려한다는 것은 먼저 끝나는 작업부터 기계에 할당하겠다는 의미입니다. 그러면 작업이 끝난 후 다른 작업을 처리할 수 있는 시간이 더 길어지기 때문에 좋을 것으로 예상됩니다.

 

하지만 증명하기 전까지는 그 생각이 올바른지 아무도 모릅니다. 그러니 증명해 보도록 하죠. 증명을 편히 하기 위해서 몇 가지 기호들을 정의하고 넘어가겠습니다. 먼저 어떤 작업 $p$에 대해, 이 작업이 시작하는 시각을 $s(p)$, 끝나는 시각을 $f(p)$라고 하겠습니다. 다음, 위 알고리즘이 기계에 할당한 작업의 집합을 $S:=\{p_1,\cdots ,p_k\}$라고 하겠습니다. 이때, $p_1,\cdots ,p_k$는 기계에서 처리되는 순서입니다. 다시 말해, $$s(p_1)\le f(p_1)\le s(p_2)\le \cdots \le f(p_{k-1})\le s(p_k)\le f(p_k)$$를 만족합니다. 비교를 위해 최적해 $O:=\{q_1,\cdots ,q_{\ell }\}$를 하나 가져오겠습니다. 여기서도 $q_1,\cdots ,q_{\ell }$은 기계에서 처리되는 순서로 $$s(q_1)\le f(q_1)\le s(q_2)\le \cdots \le f(q_{\ell -1})\le s(q_{\ell })\le f(q_{\ell })$$을 만족합니다.

 

우리가 보이고 싶은 것은 $k\ge \ell$입니다. 이를 다음 정리를 통해 증명하겠습니다.

정리 1. Correctness by greedy-stays-ahead

---

모든 $i=1,\cdots ,\ell$에 대해, $p_i\in S$이며 $f(p_i)\le f(q_i)$를 만족한다.

이것이 말하는 바를 먼저 설명 드리자면, 최적해의 각 $q_i\in O$를 $p_i\in S$에 짝지어줄 수 있고, 그러면서 항상 $p_i$가 $q_i$보다는 늦지 않게 끝난다는 것입니다. 다시 말해, $O$를 출력하는 가상의 최적 알고리즘이 있다고 했을 때, 매번 이 알고리즘이 선택하는 작업보다 탐욕 알고리즘이 그때 선택하는 작업이 더 먼저 끝난다는 것을 알 수 있습니다. 게다가 $O$의 모든 작업을 $S$에 하나씩 짝지어 주었으니 $S$가 최소 $O$의 개수 만큼은 기계에 할당했다는 사실도 알 수 있습니다.

 

[정리 1 증명] $i$에 대한 수학적 귀납법으로 보이겠습니다. 만약 $i=1$이라면 탐욕 알고리즘은 주어진 작업들 중 가장 일찍 끝나는 작업을 할당할 것이므로 분명 $p_1$이 존재하고 $f(p_1)\le f(q_1)$도 만족할 겁니다.

 

이제 $i=j-1$에 대해 정리가 성립한다고 가정했을 때(단, $j>1$), $p_j$가 $S$에 존재하고 $f(p_j)\le f(q_j)$를 만족한다는 것을 보이도록 하겠습니다. 만약 그러한 $p_j$가 존재하지 않았다면, 탐욕 알고리즘이 $p_{j-1}$을 선택한 후 다음으로 할당할 작업이 더 이상 존재하지 않았을 겁니다. 하지만 $q_j\in O$를 잘 생각해 보면, 이것이 모순이라는 점을 알 수 있습니다. $O$의 작업들도 분명히 서로 겹치지 않았어야 하므로 $f(q_{j-1})\le s(q_j)$를 만족할 겁니다. 그런데 여기서 가정에 의해 $f(p_{j-1})\le f(q_{j-1})$가 되어 $f(p_{j-1})\le s(q_j)$를 이끌어낼 수 있게 됩니다. 이는 탐욕 알고리즘이 $p_{j-1}$를 선택한 후에 $q_j$를 선택할 수 있었다는 뜻이므로 모순입니다. (그림 2)

그림 2. $p_j\notin S$인 경우. 이때는 $q_j$가 $S$에 선택되었어야 한다.

남은 것은 $f(p_j)\le f(q_j)$가 만족하는지입니다. 이는 위 논의를 따라가면 쉽게 보일 수 있습니다. 위에서 탐욕 알고리즘이 $p_{j-1}$을 선택한 후 $q_j$를 고를 수 있었다고 하였습니다. 그런데 만약 $f(p_j)>f(q_j)$라면, 사실 알고리즘은 $p_j$가 아닌 $q_j$를 골랐어야 합니다. 따라서 모순이 됩니다. (그림 3)□

그림 3. $f(p_j)>f(q_j)t$인 경우. 이때는 $q_j$가 $p_j$보다 먼저 $S$에 선택되었어야 한다.

Certificate Argument : 이것이 내 답이 정답이라는 증거일세!

Photo by Shane Aldendorff on Unsplash

다음 기법으로 넘어 가도록 하겠습니다. 이번에 공부할 기법은 'certificate argument'입니다. 직역하자면 '증거 논의' 쯤 되겠는데요. 이 기법은 알고리즘이 답과 함께 그 답이 최적해라는 증거를 함께 출력하도록 만드는 방법입니다. 증거를 함께 제출했으니 무엇을 더 바랄까요?

 

바로 예시를 들어 보겠습니다. 이번 문제는 앞에서 본 문제의 변형입니다. 똑같이 우리에게 여러 작업들이 주어지며 우리는 이 작업들을 기계에 돌려 처리해야 합니다. 이번에는 기계를 여러 대 구매할 수 있습니다만 대신 모든 작업을 처리해야 합니다. 과연 모든 작업을 처리하기 위해서는 최소 몇 대의 기계가 필요하고, 작업들을 기계에 어떻게 할당해야 할까요? 이 문제는 백준 온라인 저지의 [BOJ 11000] 강의실 배정을 다르게 표현한 것입니다.

 

기호를 사용하여 문제를 좀더 간략히 표현해 보겠습니다. 우리에게는 작업의 집합 $P$가 주어집니다. 각 작업 $p\in P$는 $s(p)$에 시작하고 $f(p)$에 끝납니다. 한 기계에는 수행 시간이 겹치는 작업 두 개를 동시에 할당할 수 없습니다. 단, 한 작업이 끝날 때 다음 작업을 바로 수행시킬 수는 있습니다. 모든 작업의 수행 시간을 $[s(p),f(p))$로 표현하면 이를 일관되게 나타낼 수 있습니다. 우리의 목표는 다음을 만족하는 $\mathcal{S}=\{S_1,\cdots ,S_k\}$ 중 그 크기 $k$가 가장 작은 것을 찾는 것입니다.

• 각 $S_j\in \mathcal{S}$는 서로 겹치는 작업이 없는 $P$의 부분집합이다. 즉, 임의의 서로 다른 두 작업 $p,p^{\prime }\in S_j$에 대해, $[s(p),f(p))\cap [s(p^{\prime }),f(p^{\prime }))=\mathrm{\varnothing }$이다.

 

알고리즘을 소개하기에 앞서 한 가지 생각해 봅시다. 과연 우리는 최소한 몇 대의 기계가 필요할까요? 네, 모든 작업을 수행해야 하므로 어떤 시각에 동시에 수행되는 작업의 개수보다는 적지 않아야 합니다. 다시 말해, 어떤 시각 $t$에 수행되는 작업의 집합을 $P_t:=\{p\in P:t\in [s(p),f(p))\}$라고 하겠습니다. 그러면 분명 다음의 정리를 만족해야 합니다.

정리 2. Certificate

---

$P$가 어떻게 주어지든 간에 모든 작업을 할당하기 위해서는 임의의 시각 $t$에 대해 $|P_t|$ 이상의 기계가 필요하다. 다시 말해, $\mathcal{S}$가 올바른 답(feasible solution)이라면 반드시 $|\mathcal{S}|\ge \underset{t}{max}|P_t|$를 만족한다.

이 정리가 흥미로운 이유는 다음 정리를 이끌어낼 수 있기 때문인데요.

정리 3. Optimality through certificate

---

만약 알고리즘이 올바른 답 $\mathcal{S}$와 함께 $|\mathcal{S}|=|P_{t^{\star }}|$인 어떤 시각 $t^{\star }$를 찾는다면, $\mathcal{S}$는 최적해이다.

[증명] 문제의 최적해를 $\mathcal{O}$라고 하겠습니다. 이 답도 올바른 답이므로 정리 2에 의해 $$|\mathcal{O}|\ge \underset{t}{max}|P_t|\ge |P_{t^{\star }}|=|\mathcal{S}|$$가 됩니다. $\mathcal{O}$는 최적해라고 했는데 $\mathcal{S}$가 그것보다 크기가 더 작거나 같으므로 $\mathcal{S}$도 최적해입니다. □

 

다시 말해, 알고리즘이 $\mathcal{S}$와 함께 정리 3을 만족하는 $t^{\star }$를 "증거"로 제출하면 알고리즘이 최적의 답을 출력한다는 것을 보일 수 있습니다. 이를 염두에 두고 다음 알고리즘을 살펴봅시다.

시간의 흐름에 따라 다음을 고려한다. 매 시각 $t$에 시작하는 작업이 있을 때 지금까지 구매한 기계에 할당할 수 있으면 그것들 중 아무 것에 할당한다. 현재까지 구매한 기계만으로는 불가능하다면, 기계를 하나 더 구매하고 거기에 할당한 다음 $t^{\star }\leftarrow t$를 기억한다.

이를 시각화하면 다음 그림과 같습니다.

그림 4. 두 번째 알고리즘 동작 예시. 가로줄은 모두 작업을 나타내며, 하늘색 세로줄은 고려 중인 시각 $t$, 빨간색 세로줄은 기억 중인 $t^{\star }$를 나타낸다.

매 시각마다 $t^{\star }$는 $|\mathcal{S}|=|P_{t^{\star }}|$를 만족한다는 것을 확인하시기 바랍니다. 이로써 알고리즘이 원하는 대로 동작한다는 것을 증명할 수 있습니다.

Exchange Argument : 봐봐, 이렇게 저렇게 바꾸면 내 답이랑 똑같지?

Photo by Haupes Co. on Unsplash

마지막으로 살펴볼 증명 기법은 'exchange argument'입니다. 직역하자면 '교환 논의' 정도가 되겠는데요. 이 방법은 먼저 가상의 최적해를 하나 고정하고, 이 최적해를 약간씩 수정하여 알고리즘의 답과 동일하도록 만드는 것입니다. 여기서 매번 최적해를 수정할 때 답이 나빠지지 않는다는 것을 보인다면 최종적으로 알고리즘의 답이 최적해보다 나쁘지 않다는 것을 보이게 되어, 그 답 역시 최적해라는 것을 증명하게 되는 것이죠.

 

이번 예시는 [BOJ 14464] 소가 길을 건너간 이유 4입니다. 대신 일관되도록 표현하기 위해 기계와 작업으로 바꿔 설명하겠습니다. 여전히 우리에게는 처리해야 할 작업들이 주어집니다. 이번 작업들에는 생성 시각과 마감 시각이 주어집니다. 즉, 생성되기 전에는 작업을 처리할 수 없으며, 작업이 생성된 후 마감 시각이 되기 전까지 작업을 기계에 할당하지 못하면 작업은 처리되지 못합니다.

 

이번에는 기계를 구매하여 작업을 처리하지 않고 외부의 공용 기계를 사용하려고 합니다. 그런데 이 공용 기계가 동작하는 방식이 약간 특이한데, 특정한 시각에 최대 하나의 작업을 처리할 수 있다고 우리에게 신호를 주게 됩니다.

 

정리하면, 언젠간 공용 기계가 우리에게 작업을 진행할 수 있다고 연락을 주면, 우리는 그 때 처리 가능한 작업 하나를 공용 기계에 보내는 방식으로 작업을 처리하게 됩니다. 다행히도 이번에는 외부 기계를 사용하기 때문에 작업들의 수행 시간이 겹치는 문제는 고민할 필요가 없습니다. 그건 공용 기계 쪽에서 알아서 처리할 문제죠. 우리의 목표는 최대한 많은 작업을 공용 기계에 보내 처리하는 것입니다.

 

이제 이 문제를 해결하는 알고리즘을 구상해 봅시다. 매번 공용 기계로부터 신호를 받으면 가능한 작업 중 하나를 공용 기계로 보낼 수 있습니다. 어떤 작업을 보내는 것이 좋을까요? 아무래도 곧 마감되는 작업을 보내는 것이 이득일 것입니다. 마감 시각이 이르다면 곧 마감되어 더 이상 작업을 처리하지 못하게 될 수 있는 반면, 마감이 늦으면 그만큼 다른 신호를 받아 처리할 가능성이 높다는 것을 의미하니까 말이죠. 따라서 이런 알고리즘을 만들어 보겠습니다.

매번 공용 기계로부터 신호를 받으면 처리할 수 있는 작업 중 가장 마감 시각이 이른 것을 공용 기계로 전송한다. 만약 처리할 수 있는 작업이 존재하지 않는 경우에는 아무 행동도 하지 않는다.

이를 도식화하면 다음과 같습니다.

그림 5. 세 번째 알고리즘 동작 예시. 가로줄은 작업이 처리될 수 있는 시간, 세로줄은 공용 기계로부터 신호가 들어온 것을 나타낸다. 각 신호와 그때 처리된 작업은 빨간색 마름모로 묶어서 표현하였다. 신호가 들어왔는데 아무 작업이 처리되지 않은 경우 그 신호를 회색으로 칠하였다.

아이디어는 매우 그럴듯하지만 증명되지 않은 명제는 주장일 뿐이죠. 이제부터 이 알고리즘이 항상 최적해를 출력한다는 것을 exchange argument로 증명해 보도록 하겠습니다.

 

증명을 위해 주어진 문제를 기호로 표현해 보겠습니다. 우리에게는 작업의 집합 $P$가 주어지고, 각 작업 $p\in P$에 대해서는 생성 시각 $r(p)$와 마감 시각 $d(p)$가 주어집니다. 또한 공용 기계가 신호를 주는 시각의 집합을 $T$라고 하겠습니다. 또, 신호의 개수를 $n:=|T|$로 정의하겠습니다. 어떤 작업이든 그것을 처리하려면 신호가 들어온 시각에 활성화되어야 합니다. 또한, 모든 작업은 최대 한 번만 수행되면 충분하고, 한 신호에는 최대 하나의 작업을 처리할 수 있습니다. 따라서, 이 문제의 올바른 해는 다음을 만족하는 작업-신호 쌍의 집합 $M\subseteq P\times T$가 되겠습니다.

• 임의의 작업-신호 쌍 $(p,t)\in M$은 $r(p)\le t\le d(p)$를 만족한다.
• 임의의 작업 $p\in P$나 어떤 신호 시각 $t\in T$나 $M$에는 최대 한 번만 등장한다. 예를 들어, $t_1\ne t_2$에 대해서 $(p,t_1)\in M$이면서 동시에 $(p,t_2)\in M$일 수 없으며, $p_1\ne p_2$에 대해 동시에 $(p_1,t)\in M$과 $(p_2,t)\in M$일 수 없다.

우리의 목표는 그러한 $M$ 중에서 크기가 가장 큰 것을 찾는 것이었죠.

 

위 탐욕 알고리즘이 출력한 결과를 $S$로, 어떤 고정된 최적해를 $O$라고 부르겠습니다. 이제부터 우리는 $O$에서 시작해서 이를 조금씩 바꾸어 언젠간 $S$가 되도록 만들 것입니다. 이때 조금씩 바꾸어도 여전히 그 크기가 줄지 않도록 할 것입니다. 그러면 $|O|\le |S|$가 되므로 $S$도 최적해라는 것을 증명할 수 있게 되는 것이죠.

 

구체적으로 설명드리기 전에 몇 가지 정의와 가정이 필요합니다. 먼저 $T=\{t_1,\cdots ,t_n\}$가 시간 순서대로 정렬되어 있다고 하겠습니다. 또한, 어떤 올바른 답 $M$이 주어졌을 때, 임의의 $i=1,\cdots ,n$에 대해, $M(t_i)$를 $M$에서 $t_i$와 짝을 이룬 작업이라고 정의하겠습니다. 만약 짝지어지지 않았다면, $M(t_i):=\mathsf{nil}$로 정의하겠습니다.

 

우리의 목표는 다음 정리를 증명하는 것입니다.

정리 4. Exchange operation

---

다음을 만족하는 $O^0,O^1,\cdots ,O^n$이 존재한다.

1. $O^0=O$이다.
2. 임의의 $i=0,1,\cdots ,n$에 대해, $t_i$까지 $O^i$와 $S$는 동일하다. 즉, 각 $t=t_1,\cdots ,t_i$에 대해, $O^i(t)=S(t)$이다.
3. $|O^0|\le |O^1|\le \cdots \le |O^n|$이다.

특히, 두 번째 조건에 의해 $O^n=S$이라는 사실을 유도할 수 있으며, 세 번째 조건에 의해 $|O|\le |S|$임을 얻을 수 있다.

[증명] $i$에 대한 수학적 귀납법으로 보이겠습니다. $i=0$일 때는 고민할 것이 없습니다. 이제, $i=j-1$일 때까지 위 조건이 모두 성립한다고 하겠습니다. 우리가 보여야 하는 것은 모든 $t=t_1,\cdots ,t_j$에 대해, $O^j(t_j)=S(t_j)$이면서 $|O^{j-1}|\le |O^j|$인 $O^j$를 만드는 것이죠. 이는 $O^{j-1}$에서 $t_j$를 고려하여 만들어 보도록 하겠습니다. 다음과 같은 경우들을 따져봅시다.

 

경우 1. $O^{j-1}(t_j)=S(t_j)$. 이때는 다른 증명이 필요 없이 $O^j:=O^{j-1}$로 두면 됩니다. 쉽게 조건 2와 3이 만족되는 것도 확인할 수 있습니다.

 

경우 2. $O^{j-1}(t_j)\ne \mathsf{nil},S(t_j)=\mathsf{nil}$. 결론부터 말씀드리면, 이 경우는 불가능합니다. $t_j$가 들어왔을 때 분명 $O^{j-1}(t_j)$가 할당 가능한 상태로 남아 있었을 것이기 때문입니다. 따라서 우리 알고리즘은 분명 어떤 작업을 할당하였을 것입니다.

 

경우 3. $O^{j-1}(t_j)=\mathsf{nil},S(t_j)\ne \mathsf{nil}$. 만약 $S(t_j)$가 $O^{j-1}$에서 할당되지 않은 상태였으면, 바로 할당해 줍시다. 즉, $$O^j:=O^{j-1}\cup \{(S(t_j),t_j)\}$$로 두면 됩니다. 그러면 두 번째 조건은 바로 만족되며, 세 번째 조건도 $|O^j|>|O^{j-1}|$이 되어 만족됩니다.

그림 6. $O^{j-1}(t_j)=\mathsf{nil},O(t_{j^{\star }})=S(t_j)$에서 $O^j$를 만드는 방법.

그렇지 않은 경우, $S(t_j)$가 $O^{j-1}$에서 $t_{j^{\star }}$에 할당되었다고 하겠습니다. 조건 2를 통해 우리는 $j^{\star }>j$라는 사실을 알 수 있습니다. 왜냐하면, $t=t_1,\cdots ,t_{j-1}$에 대해서는 가정에 의해 $O^{j-1}(t)=S(t)$이기 때문입니다. $O^j$에서는 $S(t_j)$를 $t_{j^{\star }}$가 아닌 $t_j$에 할당하겠습니다. 다시 말해, $$O^j:=O^{j-1}\setminus \{(S(t_j),t_{j^{\star }})\}\cup \{(S(t_j,t_j)\}$$로 두는 것이죠. 그러면 이제 $O^j(t_j)=S(t_j)$가 되어 두 번째 조건을 만족시킬 수 있게 됩니다. 그 크기도 $|O^j|=|O^{j-1}|$로 동일하므로 세 번째 조건 역시 충족됩니다.

 

경우 4. $\mathsf{nil}\ne O^{j-1}(t_j)\ne S(t_j)\ne \mathsf{nil}$. 가장 까다로운 경우입니다. 표현의 편의를 위해 $p:=S(t_j)$, $q:=O^{j-1}(t_j)$라고 부르겠습니다. 한 가지 알 수 있는 사실은, 우리 알고리즘이 $t_j$를 고려할 때, $p$와 $q$ 모두 활성화된 상태라는 점입니다. 따라서 $p$의 마감 시각이 $q$보다 늦지 않을 것입니다. 즉, $d(p)\le d(q)$를 만족합니다.

그림 7. $p$가 $O^{j-1}$에서 할당되지 않은 경우 $O^j$를 만드는 방법.

만약 $p$가 $O^{j-1}$에서 할당되지 않았다면, $q$ 대신 $p$를 $t_j$에 할당해주는 것으로 충분합니다. 즉, $$O^j:=O^{j-1}\setminus \{(q,t_j)\}\cup \{(p,t_j)\}$$로 두는 것이죠. 그러면 두 번째 조건이 쉽게 만족되며, 세 번째 조건 또한 그 크기가 같으므로 이끌어낼 수 있습니다.

그림 8. $O^{j-1}(t_{j^{\star }})=p$인 경우 $O^j$를 만드는 방법.

마지막으로 $p$가 $O^{j-1}$에서 $t_{j^{\star }}$에 할당되었다고 해보죠. 역시 위와 같은 논의로 조건 2에 의해 $j^{\star }>j$가 됩니다. 다만 $t_{j^{\star }}$에서 $p$를 할당하기 위해서는 반드시 $t_{j^{\star }}\le d(p)$가 되어야 합니다. 앞에서 우린 $d(p)\le d(q)$라는 사실을 보였으므로, $$r(q)\le t_j\le t_{j^{\star }}\le d(p)\le d(q)$$가 성립하여 $t_{j^{\star }}$ 때 $q$를 할당할 수 있다는 사실을 알 수 있습니다. 따라서 $t_j$와 $t_{j^{\star }}$ 때 할당된 것을 서로 바꿔칠 수 있죠. 다시 말해, $$O^j:=O^{j-1}\setminus \{(p,t_{j^{\star }}),(q,t_j)\}\cup \{(p,t_j),(q,t_{j^{\star }})\}$$로 만드는 것입니다. 그러면 두 번째 조건과 세 번째 조건 모두 성립하게 됩니다.

 

모든 경우에 대해서, 정리의 조건을 만족하는 $O^{j-1}$이 주어졌을 때 $O^j$를 만드는 방법에 대해서 보였으므로 정리의 증명이 완성됩니다. □

마치며

이번 포스트에서는 탐욕 알고리즘을 증명하는 세 가지 증명 기법에 대해서 알아 보았습니다. 간단히 정리하면 다음과 같습니다.

• Greedy stays ahead는 매번 탐욕 알고리즘이 선택하는 것이 가상의 최적 알고리즘이 선택하는 것보다 항상 좋다는 것을 보임으로써 증명하는 기법입니다.
• Certificate argument는 알고리즘이 답을 출력할 때, 그 답이 실제로 최적해라는 증거를 함께 제출하는 기법입니다.
• 마지막으로 exchange argument는 최적해를 조금씩 바꾸어 탐욕 알고리즘의 답과 동일하게 만들되, 매번 나빠지지 않는다는 것을 보임으로써 알고리즘의 답이 최적해라는 것을 증명하는 방법입니다.

모든 탐욕 알고리즘이 이 기법을 활용해서 증명할 수 있는 것은 아닙니다만, 많은 경우 세 가지 기법을 적용하면 알고리즘이 정확히 동작한다는 것을 증명할 수 있습니다.

 

이것으로 글을 모두 마칩니다. 궁금하신 점이 있으시거나, 글에 잘못된 내용이 적혀있는 경우에는 댓글로 알려주시기 바랍니다. 고맙습니다. :)