그리디 알고리즘(greedy algorithm)
그리디 알고리즘은 완전 탐색, 동적 계획법처럼 답을 구하는 과정을 여러 개의 단계로 나누어 답을 만들어가는 과정은 비슷해보인다. 하지만 각 단계에서 가능한 모든 답을 계산하여 전체적으로 가장 좋은 답을 선택하는 것이 아닌, 각 단계에서 가장 좋은 답을 선택하는 점이 완전 탐색, 동적 계획법과 다른 점이다. 예를 들어 외판원 순회 문제에서 동적 계획법은 현재 정점에서 갈 수 있는 정점 중에 전체 거리를 최소화할 수 있는 정점을 고르지만, 그리디 알고리즘은 단순히 현재 정점에서 다음 정점까지의 거리를 최소화하는 정점을 고른다.
그리디 알고리즘은 "답을 도출하는 과정 중 매 순간 최고의 선택을 해서 결과적으로 최적의 해를 도출하자"로 표현할 수 있다. 그런데 매 순간 최고의 선택이 항상 결과적으로 최적의 해를 보장할까? 답은 아니다. 그럼에도 불구하고 그리디 알고리즘을 쓰는 이유는 그리디 알고리즘이 최적해를 보장하는 문제에서 완전 탐색, 동적 계획법보다 수행 시간이 빠르기 때문이다.
언제 써야 할까?
그리디 알고리즘이 적용되는 문제는 아래 2가지 특성을 가지고 있다
- 탐욕적 선택 속성 (greedy choice property) : 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로 선택하여도 최적해를 구할 수 있음을 증명해야 한다.
- 최적 부분 구조 (optimal substructure) : 부분 문제의 최적해가 전체 문제의 최적해를 만들 수 있음을 증명해야 한다.
2가지 특성을 가진 문제는 그리디 알고리즘으로 해결할 수 있다.
그리디 알고리즘 증명 1 - Greedy stays ahead
출처 : CS161 Guid to Greedy Algorithms July 29, 2013
The greedy algorithm always is at least as far ahead as the optimal solution during each iteration of the algorithm.
과정
- Define Your Solution
우리가 생각한 알고리즘을 \(\boldsymbol {X}\), 최적해 알고리즘을 \(\boldsymbol {X^*}\)라고 하자. - Define Your Measure
문제를 여러 개로 나눈 부분 문제 \(m\)에 대하여 \(m_1(X), m_2(X),... , m_n(X)\) 와 \(m_1(X^*), m_2(X^*),..., m_l(X^*)\)이라고 하자. (\(n\)과 \(l\)은 다를 수 있음) - Prove Greedy Stays Ahead
모든 \(i\)에 대하여 \(m_i(X) ≥ m_i(X^*)\) 또는 \(m_i(X) ≤ m_i(X^*)\)을 만족하는지 증명해야 한다. 즉 우리가 고른 알고리즘이 매 순간 최적의 알고리즘보다 앞서있다는 것을 증명하는 것이다. (수학적 귀납법으로 보통) - Prove Optimality
그리디 알고리즘이 최적해 알고리즘을 리턴하는 것을 증명해야 한다.(귀류법으로 보통)
예시 - 회의실 배정
- \(X=\{x_1,\ x_2\ ,...,\ x_n\}\) : 회의가 일찍 끝나는 순서로 회의실을 최대한 배정하는 알고리즘
\(X^*=\{x^*_1,\ x^*_2\ ,...,\ x^*_l\}\) : 어떠한 최적 알고리즘 (\(n\)과 \(l\)은 다를 수 있다.)
- 회의 시작시간을 \(s\), 끝나는 시간을 \(e\)라고 했을 때 각 알고리즘의 부분집합은 서로 겹치지 않아 비교 가능하다. \(s(x_1) ≤ e(x_1) ≤... ≤ s(x_n) ≤ e(x_n)\)와 \(s(x^*_1) ≤ e(x^*_1) \le... \le\ s(x^*_l) ≤ e(x^*_l)\)을 만족한다.
- \(1 \le i \le n\)을 만족하는 모든 \(i\)에 대하여 \(e(x_i) ≤ e(x^*_i)\)을 만족함을 보여야 한다. 즉. \(i\)번째 우리가 선택한 회의의 종료시간이 최적해가 선택한 회의의 종료 시간보다 느리지 않아 항상 앞선다는 것을 증명해야 한다.
- \(i=1\)일 때 \(X\)는 가장 일찍 끝나는 회의를 선택하므로 항상 \(e(x_1) ≤ e(x^*_1)\)을 만족한다.
- \(i=k\)일 때 \(e(x_k) ≤ e(x^*_k)\)가 만족한다고 가정하자.
\(X^*\)가 \(e(x^*_k) \le s(x^*_{k+1})\)을 만족하므로 \(e(x_k) ≤ e(x^*_k) ≤ s(x^*_{k+1})\)을 만족한다. 즉 \(x^*_{k+1}\)은 모두 \(x_k, \ x^*_k\)보다 늦게 시작한다.
\(x^*_{k+1}\)도 우리의 알고리즘에 선택지에 있음에도 불구하고 우리는 \(k+1\)번째에 \(x_{k+1}\)을 선택했으므로 \(x_{k+1}\)이 \(x^*_{k+1}\)보다 느리지 않음을 알 수 있고 \(i=k+1\)일 때 \(e(x_{k+1}) ≤ e(x^*_{k+1})\)이 만족한다. - 따라서 \(1 \le i \le n\)을 만족하는 모든 \(i\)에 대하여 \(e(x_i) ≤ e(x^*_i)\)을 만족한다.
- \(X\)가 최대 개수를 리턴한다는 것을 증명하여 X가 최적해임을 보이자.
- \(n ≥ l\)임을 보이기 위해 귀류법을 사용하자.
- \(X\)가 \(n\)개를 리턴했는데 \(X^*\)가 \)n+1\)개를 리턴했다고 가정하자. 2, 3번에 의해 \(x_n\)와 \(x^*_{n+1}\)는 비교 가능하다. \(X\)는 선택 가능한 회의가 없을 때까지 회의를 선택하므로 선택지에 \(x^*_{n+1}\)이 남아있음에도 \(X\)가 종료되었다는 것은 모순이므로 \(n\)은 최대 개수가 맞다.