- MIT 6.006 Introduction to Algorithms (Spring 2020) 15강 정리
- 강의: Erik Demaine, Jason Ku, Justin Solomon
- MIT OpenCourseWare, CC BY-NC-SA
- ▶ 강의 영상
- Recitation 15 notes (PDF)
알고리즘 문제를 푸는 두 가지 길
알고리즘 문제를 푸는 첫 번째 방법은 이미 아는 문제로 환원(reduce)하는 것이다. 지금까지 배운 도구는 다음과 같다.
| 탐색 자료구조 | 정렬 알고리즘 | 그래프 알고리즘 |
|---|---|---|
| 배열(array) | 삽입 정렬(insertion sort) | BFS |
| 연결 리스트(linked list) | 선택 정렬(selection sort) | DAG 완화(DFS + 위상 정렬) |
| 동적 배열(dynamic array) | 병합 정렬(merge sort) | Dijkstra |
| 정렬된 배열(sorted array) | 계수 정렬(counting sort) | Bellman-Ford |
| 직접 접근 배열(direct-access array) | 기수 정렬(radix sort) | Johnson |
| 해시 테이블(hash table) | AVL 정렬 | |
| AVL 트리 | 힙 정렬(heap sort) | |
| 이진 힙(binary heap) |
강의 노트에 정리된 지금까지의 도구 상자. 탐색 자료구조, 정렬 알고리즘, 그래프 알고리즘의 세 열로 나뉜다. 출처: MIT 6.006 Lecture 15 notes (CC BY-NC-SA 4.0).
세 열은 수업의 앞부분 세 단원에 대응한다. 첫 열은 집합과 순서열 인터페이스를 구현하는 자료구조, 둘째 열은 정렬 알고리즘, 셋째 열은 그래프 탐색과 최단 경로 알고리즘이다. 새 문제를 만나면 먼저 이 목록 가운데 하나로 바꿔 풀 수 있는지 확인한다. 예를 들어 “가장 저렴한 환승 경로”는 그래프를 만들어 Dijkstra로, “중복 원소 찾기”는 해시 테이블로 바로 풀린다. 이 목록으로 해결되지 않을 때 비로소 재귀 알고리즘을 직접 설계하는 두 번째 길로 넘어간다.
두 번째 방법은 자신만의 재귀 알고리즘(recursive algorithm)을 설계하는 것이다. 알고리즘은 상수 크기의 프로그램으로 임의 크기의 입력을 풀어야 하므로 반복이나 재귀가 필요하고, 정확성은 귀납법으로 분석한다.
재귀 호출 하나하나를 그래프의 정점으로 보고, B가 A를 호출하면 A → B 방향의 간선을 둔다. 재귀가 종료하려면 이 의존 그래프(dependency graph)는 비순환(acyclic)이어야 한다. 재귀 알고리즘은 이 그래프의 모양으로 분류할 수 있다.
| 분류 | 그래프 모양 |
|---|---|
| 무차별 대입(brute force) | 별(star) |
| 감소 정복(decrease & conquer) | 사슬(chain) |
| 분할 정복(divide & conquer) | 트리(tree) |
| 동적 계획법(dynamic programming) | DAG |
| 탐욕/점진(greedy/incremental) | 부분 그래프(subgraph) |
재귀 알고리즘의 분류와 그 호출 의존 그래프의 모양. 마지막 행은 가로선으로 분리되어 있다. 출처: MIT 6.006 Lecture 15 notes (CC BY-NC-SA 4.0).
위의 네 행은 그래프가 점점 일반적인 모양이 되는 순서다. 무차별 대입은 원래 문제 하나가 모든 후보를 한 번씩 호출하므로 중심에서 뻗어 나가는 별 모양이다. 감소 정복은 크기 \(n\)인 문제가 크기 \(n-1\)인 문제 하나만 부르므로 사슬, 분할 정복은 여러 개의 서로 겹치지 않는 부분 문제를 부르므로 트리가 된다. 동적 계획법은 서로 다른 호출이 같은 부분 문제를 공유할 수 있어서 트리가 아닌 DAG가 된다. 트리와 DAG의 차이, 곧 “진입 차수가 1보다 큰 정점이 있는가”가 메모이제이션이 효과를 내는지를 결정한다.
맨 아래 행이 선으로 분리된 것은 탐욕 알고리즘이 성격이 다르기 때문이다. 탐욕 알고리즘은 동적 계획법의 부분 문제 DAG에서 각 단계마다 가장 좋아 보이는 하나의 간선만 따라가므로, 그 DAG의 부분 그래프만 탐색한다.
어려운 부분은 귀납적으로 생각해서 부분 문제(subproblem)에 대한 점화식을 세우는 일이다. 이를 체계적으로 하기 위한 틀이 SRTBOT이다.
- Subproblem: 부분 문제 정의
- Relate: 부분 문제의 해를 재귀적으로 연결
- Topological order: 부분 문제 사이의 위상 순서(부분 문제 DAG임을 보임)
- Base cases: 관계식의 기저 사례
- Original problem: 부분 문제의 해로 원래 문제의 해를 구함
- Time analysis: 시간 분석
SRTBOT으로 본 병합 정렬
이미 아는 병합 정렬도 SRTBOT으로 표현할 수 있다. 길이 \(n\)인 배열 \(A\)를 정렬한다.
- 부분 문제: \(S(i, j)\) = \(A[i:j]\)의 원소를 정렬한 배열, \(0 \le i \le j \le n\).
- 관계: \(m = \lfloor (i+j)/2 \rfloor\)에 대해 \(S(i, j) = \text{merge}(S(i, m), S(m, j))\).
- 위상 순서: \(j - i\)가 증가하는 순서.
- 기저 사례: \(S(i, i+1) = [A[i]]\).
- 원래 문제: \(S(0, n)\).
- 시간: \(T(n) = 2T(n/2) + O(n) = O(n \lg n)\).
이 경우 부분 문제 DAG는 트리이므로 분할 정복이다.
피보나치 수
이 절에서는 \(n\)번째 피보나치 수 \(F_n\)을 구한다.
- 부분 문제: \(F(i)\) = \(i\)번째 피보나치 수 \(F_i\), \(i \in \{0, 1, \ldots, n\}\).
- 관계: \(F(i) = F(i-1) + F(i-2)\) (정의 그대로).
- 위상 순서: \(i\)가 증가하는 순서.
- 기저 사례: \(F(0) = 0\), \(F(1) = 1\).
- 원래 문제: \(F(n)\).
이를 그대로 코드로 옮기면 다음과 같다.
def fib(n):
if n < 2: return n # base case
return fib(n - 1) + fib(n - 2) # recurrence
이 코드의 호출 구조는 트리이고, 수행 시간은 다음과 같이 지수적이다.
\[T(n) = T(n-1) + T(n-2) + O(1) > 2T(n-2) \quad\Rightarrow\quad T(n) = \Omega(2^{n/2})\]원인은 같은 부분 문제 \(F(k)\)가 여러 번(정확히는 \(F_{n-k}\)번) 계산된다는 데 있다.
부분 문제 해의 재사용
부분 문제 사이의 의존 관계를 DAG로 그리고, 다음 두 방식 중 하나로 푼다.
- 하향식(top down): 부분 문제의 해를 메모(memo)에 기록하고 재사용한다. 즉 재귀 + 메모이제이션(memoization)이다.
- 상향식(bottom up): 부분 문제를 위상 정렬 순서대로 푼다. 보통 반복문으로 구현한다.
피보나치에서는 부분 문제(정점)가 \(n+1\)개, 의존 관계(간선)가 \(2n\)개 미만이므로 덧셈 \(O(n)\)번이면 계산이 끝난다.
# recursive solution (top down)
def fib(n):
memo = {}
def F(i):
if i < 2: return i # base cases
if i not in memo: # check memo
memo[i] = F(i - 1) + F(i - 2) # relation
return memo[i]
return F(n) # original
# iterative solution (bottom up)
def fib(n):
F = {}
F[0], F[1] = 0, 1 # base cases
for i in range(2, n + 1): # topological order
F[i] = F[i - 1] + F[i - 2] # relation
return F[n] # original
미묘한 점이 하나 있다. 피보나치 수는 \(\Theta(n)\) 비트 길이까지 커지므로 워드 크기 \(w\)보다 훨씬 클 수 있다. 덧셈 한 번에 \(O(\lceil n/w \rceil)\) 시간이 들고, 전체 비용은 \(O(n \lceil n/w \rceil) = O(n + n^2/w)\)이다.
동적 계획법
동적 계획법(dynamic programming)이라는 이상한 이름은 Richard Bellman이 붙였다. 정부 연구비를 받으려고 수학을 한다는 사실을 감추는 멋진 이름이 필요했다고 한다. 계획(program)을 갱신한다(dynamic)는 뜻이다.
- 재귀적 해가 존재한다는 것은 문제를 부분 문제로 분해할 수 있다는 뜻이다. 이 성질을 흔히 최적 부분 구조(optimal substructure)라 부르지만, 동적 계획법만이 아니라 재귀 일반의 성질이다.
- 재귀 알고리즘은 계산 그래프를 만든다. 부분 문제 의존이 겹치면(DAG에서 진입 차수가 1보다 크면) 동적 계획법이다.
- 하향식 관점으로는 “재귀하되 재사용하라(recurse but re-use)”, 상향식 관점으로는 “신중한 무차별 대입(careful brute force)”이다.
- 세기(counting) 문제나 최적화(optimization) 문제에 특히 유용하며, 점화식의 정확성이 거의 자명한 경우가 많다.
SRTBOT 자세히
- 부분 문제 정의: 부분 문제 \(x \in X\)의 의미를 매개변수로 말로 설명한다. 입력의 부분집합, 특히 접두사(prefix), 접미사(suffix), 연속 부분 문자열(substring)을 쓰는 경우가 많다. 보조 변수를 늘려 부분적인 상태(partial state)를 기록하기도 한다.
- 관계: 하나 이상의 \(j < i\)에 대해 \(x(i) = f(x(j), \ldots)\) 꼴로 쓴다.
- 위상 순서: 관계가 비순환이고 부분 문제가 DAG를 이룸을 보인다.
- 기저 사례: 관계가 성립하지 않는 (도달 가능한) 독립 부분 문제의 해를 모두 명시한다.
- 원래 문제: 부분 문제의 해로 원래 문제의 해를 계산하는 방법을 보인다. 목적 함수 값뿐 아니라 실제 해가 필요하면 부모 포인터(parent pointer)를 저장한다.
- 시간 분석: 전체 시간은 다음과 같다.
여기서 \(\text{work}(x)\)는 관계식의 비재귀적 작업량이며, 재귀 호출은 \(O(1)\)로 취급한다(메모이제이션 덕분).
DAG 최단 경로
DAG \(G\)와 정점 \(s\)가 주어질 때 모든 \(v \in V\)에 대해 \(\delta(s, v)\)를 구하는 DAG SSSP 문제를 다시 보자.
- 부분 문제: 모든 \(v \in V\)에 대한 \(\delta(s, v)\).
- 관계: \(\delta(s, v) = \min(\{\delta(s, u) + w(u, v) \mid u \in \text{Adj}^-(v)\} \cup \{\infty\})\).
- 위상 순서: \(G\)의 위상 순서.
- 기저 사례: \(\delta(s, s) = 0\).
- 원래 문제: 모든 부분 문제.
- 시간: \(\sum_{v \in V} O(1 + \lvert \text{Adj}^-(v) \rvert) = O(\lvert V \rvert + \lvert E \rvert)\).
DAG 완화(DAG relaxation)는 이 동적 계획법과 같은 최솟값을 계산한다. 다만 (1) 새 값이 현재 최솟값보다 작으면 간선 완화로 갱신하는 식으로 한 단계씩 계산하고, (2) \(v\)와 \(\text{Adj}^-(v)\)의 관점 대신 \(u\)와 \(\text{Adj}^+(u)\)의 관점에서 계산한다는 차이만 있다.
볼링
핀 \(n\)개가 \(0, 1, \ldots, n-1\)로 번호 붙어 있고, 핀 \(i\)의 값은 \(v_i\)다. 핀과 비슷한 크기의 공은 다음 중 하나를 맞힌다.
- 핀 하나 \(i\): \(v_i\)점을 얻는다.
- 인접한 두 핀 \(i\)와 \(i+1\): \(v_i \cdot v_{i+1}\)점을 얻는다.
한 번 맞힌 핀은 제거되어 다시 맞힐 수 없다. 공을 0번 이상 던져 총점을 최대화하는 것이 목표다. 예: \([-1, 1, 1, 1, 9, 9, 3, -3, -5, 2, 2]\). 값이 음수일 수 있으므로 핀을 건너뛰는 선택도 의미가 있다. 예를 들어 \(9 \cdot 9\)나 \((-3)\cdot(-5)\)처럼 묶는 것이 이득이다.
볼링 예제의 최적해. 상자 하나가 공 하나이며, 상자에 든 핀이 한 개면 그 값을, 두 개면 두 값의 곱을 얻는다. 출처: MIT 6.006 Lecture 15 notes (CC BY-NC-SA 4.0).
그림을 왼쪽부터 읽으면 각 핀에 대한 선택이 보인다. 첫 핀 \(-1\)은 상자 밖에 있으므로 건너뛴다. 이어지는 세 개의 1은 각각 따로 맞힌다. 1끼리 묶으면 \(1 \cdot 1 = 1\)점이라 따로 맞혀 2점을 얻는 것보다 손해다. \(9, 9\)는 묶어서 81점, 3은 따로 3점, \(-3, -5\)는 묶으면 음수끼리의 곱이 양수가 되어 15점, 마지막 \(2, 2\)는 묶으면 4점으로 따로 맞힐 때와 같다. 합은 \(1 + 1 + 1 + 81 + 3 + 15 + 4 = 106\)이다.
이 예는 탐욕적인 규칙이 잘 통하지 않는다는 점도 보여 준다. \(-3\)이나 \(-5\)만 보면 건너뛰는 것이 맞아 보이지만 둘을 함께 보면 묶는 것이 최선이고, 1과 1은 묶는 것보다 따로 맞히는 것이 낫다. 어떤 핀을 어떻게 처리할지는 이웃 핀과의 관계에 달려 있으므로, 가능한 처리 방법을 모두 시도하는 국소적 무차별 대입이 필요하다.
분할 정복 풀이
익숙한 분할 정복부터 시작한다.
- 부분 문제: \(B(i, j)\) = 핀 \(i, i+1, \ldots, j-1\)만 있을 때의 최대 점수, \(0 \le i \le j \le n\).
- 관계: \(m = \lfloor (i+j)/2 \rfloor\)으로 두고, \(m\)과 \(m+1\)을 함께 맞히거나 그렇지 않거나 둘 중 하나다.
- 위상 순서: \(j - i\) 증가 순.
- 기저 사례: \(B(i, i) = 0\), \(B(i, i+1) = \max\{v_i, 0\}\).
- 원래 문제: \(B(0, n)\).
- 시간: \(T(n) = 4T(n/2) + O(1) = O(n^2)\).
동작은 하지만 빠르지 않고, 핀 세 개를 한꺼번에 맞히는 큰 공처럼 문제를 바꾸면 일반화하기도 어렵다.
접미사를 쓰는 동적 계획법
- 부분 문제: \(B(i)\) = 핀 \(i, i+1, \ldots, n-1\)만 있을 때의 최대 점수, \(0 \le i \le n\).
- 관계: 첫 번째 핀(원래 핀 \(i\))에 무슨 일이 일어날지를 국소적으로 무차별 대입한다. 건너뛰기, 하나만 맞히기, 둘을 함께 맞히기. 그 뒤 더 작은 접미사 \(B(i+1)\)이나 \(B(i+2)\)로 재귀한다.
- 위상 순서: \(i\) 감소 순(\(i = n, n-1, \ldots, 0\)).
- 기저 사례: \(B(n) = B(n+1) = 0\).
- 원래 문제: \(B(0)\).
- 시간: 메모이제이션을 가정하면 부분 문제 \(\Theta(n)\)개, 각각 \(\Theta(1)\) 작업이므로 \(\Theta(n)\).
빠르고 일반화도 쉽다. 이 풀이는 부분 문제 DAG \(B_0 \to B_1 \to \cdots \to B_n\)에서의 최대 가중치 경로와 같다. \(B_i \to B_{i+1}\) 간선의 가중치는 \(\max\{v_i, 0\}\), \(B_i \to B_{i+2}\) 간선의 가중치는 \(v_i \cdot v_{i+1}\)이다.
볼링의 부분 문제 DAG. 위쪽 간선은 핀 하나를 처리하고 다음 접미사로, 아래쪽 곡선 간선은 핀 두 개를 함께 맞히고 두 칸 뒤의 접미사로 간다. 출처: MIT 6.006 Lecture 15 notes (CC BY-NC-SA 4.0).
그림에서 \(B_i\)는 “핀 \(i\)부터 남은 상태”다. \(B_i\)에서 나가는 간선은 두 개뿐이다. 위쪽 직선 간선 \(B_i \to B_{i+1}\)은 핀 \(i\)를 건너뛰거나 따로 맞히는 경우로, 둘 중 좋은 쪽인 \(\max\{v_i, 0\}\)이 가중치다. 아래쪽 곡선 간선 \(B_i \to B_{i+2}\)는 핀 \(i\)와 \(i+1\)을 함께 맞히는 경우로 가중치가 \(v_i \cdot v_{i+1}\)이다. 간선이 항상 오른쪽으로만 향하므로 이 그래프는 DAG이고, 위상 순서는 단순히 인덱스 순서다.
\(B_0\)에서 \(B_n\)으로 가는 경로 하나가 볼링 전략 하나에 대응한다. 앞의 예제에서 최적해는 \(B_0 \to B_1 \to B_2 \to B_3 \to B_4 \to B_6 \to B_7 \to B_9 \to B_{11}\) 경로이고, 가중치 합이 106이다. 따라서 볼링은 이 DAG에서 최대 가중치 경로를 찾는 문제이며, 가중치의 부호를 뒤집으면 지난 강의들의 DAG 최단 경로 문제와 같다. 정점이 \(n+1\)개, 간선이 \(2n\)개 미만이므로 DAG Relaxation으로 \(\Theta(n)\)에 풀린다는 것도 그림에서 바로 읽힌다.
볼링 코드
SRTBOT 명세를 코드로 옮기는 일은 거의 기계적이다. 아래에서 \(v_i \cdot v_{i+1}\) 항은 \(i+1 < n\)일 때만 고려한다.
# recursive solution (top down)
def bowl(v):
n = len(v)
memo = {}
def B(i):
if i >= n: return 0 # base cases
if i not in memo: # check memo
best = max(B(i + 1), # relation: skip pin i
v[i] + B(i + 1)) # OR bowl pin i separately
if i + 1 < n: # OR bowl pins i and i+1 together
best = max(best, v[i] * v[i + 1] + B(i + 2))
memo[i] = best
return memo[i]
return B(0) # original
# iterative solution (bottom up)
def bowl(v):
n = len(v)
B = [0] * (n + 2) # base cases B[n] = B[n+1] = 0
for i in reversed(range(n)): # topological order
B[i] = max(B[i + 1], v[i] + B[i + 1]) # skip pin i, or bowl it alone
if i + 1 < n: # bowl pins i and i+1 together
B[i] = max(B[i], v[i] * v[i + 1] + B[i + 2])
return B[0] # original
부분 문제의 해를 연결하는 법
관계식을 세우는 일반적인 방법은 다음과 같다.
- 답을 안다면 문제를 “더 작은” 부분 문제로 줄여 주는 질문을 하나 찾는다. 볼링에서는 “첫 핀 한두 개를 어떻게 처리하는가?”였다.
- 그 질문의 가능한 답을 모두 시도하는 국소적 무차별 대입(local brute force) 을 하고 가장 좋은 것을 고른다. 볼링은 최대화 문제이므로 max를 취했다.
- 답을 올바르게 추측(guess) 하고 곧장 재귀한다고 생각해도 된다. 실제로는 모든 추측을 검사하고 가장 좋은 것을 돌려준다.
효율의 핵심은 질문의 가능한 답이 적어서(다항 개) 무차별 대입 비용이 크지 않은 것이다. 관계식의 비재귀적 작업량은 시도하는 답의 개수와 같은 경우가 많다(항상은 아니다).
Recitation 예제: 단순화된 블랙잭
Recitation 15의 예제도 같은 틀로 풀린다. 순서가 알려진 카드 덱 \(D = (c_1, \ldots, c_n)\)이 있고, 각 라운드에서 딜러가 두 장, 플레이어가 두 장을 뽑은 뒤 플레이어는 한 장을 더 뽑을지(hit) 정한다. 플레이어의 합이 21 이하이면서 딜러보다 크면 이긴다. 이길 수 있는 라운드 수의 최댓값을 구한다.
- 부분 문제: \(x(i)\) = 카드 \((c_i, \ldots, c_n)\)으로 이길 수 있는 최대 라운드 수.
- 관계: hit 여부를 추측한다. \(w(d, p) = 1\) (\(d < p \le 21\)일 때), 아니면 0으로 두면, \(i \le n-4\)일 때 다음과 같다.
- 위상 순서: \(i\) 감소 순. 기저 사례: \(x(n-3) = \cdots = x(n+1) = 0\). 원래 문제: \(x(1)\). 시간: \(O(n)\).
같은 recitation의 텍스트 정렬(text justification) 예제는 \(x(i) = \min\{b(i, j) + x(j+1) \mid i \le j < n\}\)로 풀린다. 각 줄의 나쁨(badness) \(b(i, j)\)를 매번 계산하면 \(O(n^3)\)이지만, 구간 합을 다시 동적 계획법으로 미리 계산하면 \(O(n^2)\)이 된다.
정리
- 재귀 알고리즘은 호출 의존 그래프의 모양(별, 사슬, 트리, DAG)으로 분류되고, 부분 문제가 겹치는 DAG인 경우가 동적 계획법이다.
- SRTBOT(부분 문제, 관계, 위상 순서, 기저 사례, 원래 문제, 시간)은 재귀 알고리즘을 설계하고 서술하는 틀이다.
- 순진한 재귀 피보나치는 \(\Omega(2^{n/2})\)이지만, 메모이제이션(하향식)이나 위상 순서 반복(상향식)으로 덧셈 \(O(n)\)번에 줄어든다.
- 시간은 \(\sum_{x} \text{work}(x)\)이며, 재귀 호출은 \(O(1)\)로 센다.
- DAG 최단 경로는 \(\delta(s, v) = \min_{u} \{\delta(s, u) + w(u, v)\}\)인 동적 계획법이고, DAG 완화는 이를 간선 쪽에서 계산한 것이다.
- 볼링은 접미사 부분 문제와 첫 핀에 대한 국소적 무차별 대입으로 \(\Theta(n)\)에 풀린다.
- 관계식의 핵심은 답의 가짓수가 적은 질문을 찾아 모든 답을 시도하는 것이다.