- MIT 6.006 Introduction to Algorithms (Spring 2020) 16강 정리
- 강의: Erik Demaine, Jason Ku, Justin Solomon
- MIT OpenCourseWare, CC BY-NC-SA
- ▶ 강의 영상
- Recitation 16 notes (PDF)
동적 계획법 복습
동적 계획법은 부분 문제 의존이 겹쳐 DAG를 이루는 재귀다. 하향식으로는 “재귀하되 재사용”(부분 문제 해를 기록하고 조회), 상향식으로는 “신중한 무차별 대입”(부분 문제를 순서대로 해결)이다.
SRTBOT 단계를 다시 정리하면 다음과 같다.
- 부분 문제 정의: 부분 문제 \(x \in X\)의 의미를 매개변수로 설명한다. 접두사, 접미사, 연속 부분 문자열을 자주 쓰며, 여러 입력에 대해 가능한 부분집합을 곱하는 경우도 많다. 보조 변수를 늘려 부분 상태를 기록하기도 한다.
- 관계: 답을 알면 부분 문제를 더 작은 부분 문제로 줄여 주는 질문을 찾고, 가능한 모든 답을 국소적으로 무차별 대입한다.
- 위상 순서: 관계가 비순환임을 보인다.
- 기저 사례: 관계가 깨지는 (도달 가능한) 독립 부분 문제의 해를 명시한다.
- 원래 문제: 부분 문제 해로 원래 해를 계산한다. 실제 해는 부모 포인터로 복원한다.
- 시간: \(\sum_{x \in X} \text{work}(x)\), 또는 모든 작업량이 \(O(W)\)이면 \(\lvert X \rvert \cdot O(W)\).
최장 공통 부분 수열 (LCS)
두 문자열 \(A\)와 \(B\)가 주어질 때, \(A\)의 부분 수열(subsequence, 연속일 필요 없음)이면서 \(B\)의 부분 수열인 것 중 가장 긴 것을 찾는다. 이것이 최장 공통 부분 수열(longest common subsequence, LCS)이다.
예: \(A\) = hieroglyphology, \(B\) = michaelangelo. 답은 hello, heglo, iello, ieglo 등이며 모두 길이 5다. 부분 수열의 길이에 대한 최대화 문제다.
SRTBOT
1. 부분 문제. \(x(i, j)\) = 접미사 \(A[i:]\)와 \(B[j:]\)의 LCS 길이, \(0 \le i \le \lvert A \rvert\), \(0 \le j \le \lvert B \rvert\). 두 입력의 접미사를 곱한 부분 문제다.
2. 관계. 첫 문자가 같거나 다르거나 둘 중 하나다.
- 첫 문자가 같으면 어떤 LCS는 그 쌍을 사용한다. 어떤 LCS도 첫 일치 쌍을 쓰지 않는다면 그 쌍을 추가해 해를 개선할 수 있다. LCS가 \(A[i]\)를 쓰되 \(B[j]\)가 아닌 다른 문자와 짝지었다면, 그 짝을 \(B[j]\)로 바꿔도 여전히 최적이다.
- 첫 문자가 다르면 둘이 동시에 LCS에 들어갈 수는 없다. \(A[i]\)와 \(B[j]\) 중 어느 것이 LCS에 없는지 추측한다.
3. 위상 순서. \(x(i, j)\)는 \(i\)나 \(j\) 또는 둘 다 엄격히 큰 부분 문제에만 의존한다. 가장 서술하기 쉬운 순서는 \(i + j\) 감소 순이고, 상향식 코드에는 \(i\) 감소, 그 안에서 \(j\) 감소 순이 편하다. 부분 문제들은 직사각형 격자를 이루고 각 칸은 오른쪽, 아래, 오른쪽 아래 대각선 칸에 의존한다.
4. 기저 사례. \(x(i, \lvert B \rvert) = x(\lvert A \rvert, j) = 0\) (한 문자열이 비었음).
5. 원래 문제. LCS 길이는 \(x(0, 0)\)이다. 부모 포인터를 저장하면 부분 수열을 복원할 수 있다. 부모 포인터가 두 인덱스를 모두 증가시키면 그 문자를 LCS에 추가한다.
6. 시간. 부분 문제 \((\lvert A \rvert + 1)(\lvert B \rvert + 1)\)개, 각각 \(O(1)\) 작업이므로 \(O(\lvert A \rvert \cdot \lvert B \rvert)\).
def lcs(A, B):
a, b = len(A), len(B)
x = [[0] * (b + 1) for _ in range(a + 1)]
for i in reversed(range(a)):
for j in reversed(range(b)):
if A[i] == B[j]:
x[i][j] = x[i + 1][j + 1] + 1
else:
x[i][j] = max(x[i + 1][j], x[i][j + 1])
return x[0][0]
최장 증가 부분 수열 (LIS)
문자열 \(A\)가 주어질 때 (사전식으로) 엄격히 증가하는 가장 긴 부분 수열을 찾는다. 이것이 최장 증가 부분 수열(longest increasing subsequence, LIS)이다.
예: \(A\) = carbohydrate. 답은 abort이며 길이 5다.
첫 시도와 문제점
자연스러운 부분 문제는 접두사나 접미사, 예컨대 접미사 \(A[i:]\)다. 자연스러운 질문은 “\(A[i]\)가 LIS에 들어가는가?”(답 2가지)다. 그런데 \(A[i]\)를 넣기로 하면, \(A[i+1:]\)로 재귀할 때 그 결과가 \(A[i]\)보다 큰 원소로 시작한다는 보장이 없다. 증가 조건을 확인할 정보가 부족하다.
해결책은 부분 문제에 제약(constraint) 을 추가해 증가 성질을 다룰 만큼의 구조를 주는 것이다.
SRTBOT
1. 부분 문제. \(x(i)\) = 접미사 \(A[i:]\)의 증가 부분 수열 중 \(A[i]\)를 포함하는 것의 최대 길이, \(0 \le i < \lvert A \rvert\).
2. 관계. \(A[i]\)가 LIS의 첫 원소임은 주어져 있다. 다음 질문은 “두 번째 원소는 무엇인가?”다. \(j > i\)이고 \(A[j] > A[i]\)인 어떤 \(A[j]\)든 될 수 있고, \(A[i]\)가 마지막 원소일 수도 있다.
\[x(i) = \max(\{1 + x(j) \mid i < j < \lvert A \rvert,\; A[j] > A[i]\} \cup \{1\})\]3. 위상 순서. \(i\) 감소 순.
4. 기저 사례. 필요 없다. \(A[i]\)가 마지막 원소인 경우를 관계식에서 이미 고려했기 때문이다.
5. 원래 문제. LIS의 첫 원소가 무엇인지 추측한다. LIS 길이는 \(\max\{x(i) \mid 0 \le i < \lvert A \rvert\}\)이다. 부모 포인터로 부분 수열을 복원한다.
6. 시간. 부분 문제 \(\lvert A \rvert\)개, 각각 \(O(\lvert A \rvert)\) 작업이므로 \(O(\lvert A \rvert^2)\). AVL 트리 증강(augmentation)을 써서 부분 문제마다 \(O(\log \lvert A \rvert)\) 작업만 하면 \(O(\lvert A \rvert \log \lvert A \rvert)\)로 줄일 수 있다(연습 문제).
def lis(A):
a = len(A)
x = [1] * a
for i in reversed(range(a)):
for j in range(i, a):
if A[j] > A[i]:
x[i] = max(x[i], 1 + x[j])
return max(x)
Recitation 예제: 최대 부분 배열 합
Recitation 16의 최대 부분 배열 합(max subarray sum)도 LIS처럼 조건이 붙은 부분 문제를 쓴다. 정수 배열 \(A\)에서 비어 있지 않은 연속 부분 배열의 최대 합을 구한다. 예: \([-9, 1, -5, 4, 3, -6, 7, 8, -2]\)의 답은 16이다.
- 부분 문제: \(x(k)\) = \(A[k]\)에서 끝나는 부분 배열의 최대 합.
- 관계: \(k-1\)을 쓰거나 쓰지 않거나 둘 중 하나다. \(x(k) = \max\{A[k],\; A[k] + x(k-1)\}\).
- 위상 순서: \(k\) 증가 순. 기저 사례: \(x(0) = A[0]\).
- 원래 문제: \(\max_k x(k)\). 시간: \(O(n)\).
def max_subarray_sum(A):
x = [None for _ in A] # memo
x[0] = A[0] # base case
for k in range(1, len(A)): # iteration
x[k] = max(A[k], A[k] + x[k - 1]) # relation
return max(x) # original
같은 recitation의 편집 거리(edit distance)는 LCS처럼 두 문자열의 접두사 쌍 \(x(i, j)\)를 부분 문제로 두고, 마지막 문자가 같으면 \(x(i-1, j-1)\), 다르면 삭제, 삽입, 교체를 추측해 \(1 + \min\{x(i-1, j), x(i, j-1), x(i-1, j-1)\}\)로 푼다. \(O(\lvert A \rvert \lvert B \rvert)\) 시간이다.
번갈아 동전 가져가기 게임
값이 \(v_0, v_1, \ldots, v_{n-1}\)인 동전 \(n\)개가 한 줄로 놓여 있다. 두 플레이어(“나”와 “너”)가 번갈아 남은 동전 중 맨 앞이나 맨 뒤의 것을 하나 가져간다. 내가 먼저 시작하며, 내가 가져가는 동전의 총 가치를 최대화하는 것이 목표다.
첫 번째 풀이: 제로섬 성질 이용
제로섬 게임이므로 네가 가져가지 않은 동전은 모두 내 것이다.
1. 부분 문제. 게임의 상태에 대응하는 부분 문제를 고른다. 동전 \(i\)부터 \(j\)까지의 모든 연속 부분 수열(\(0 \le i \le j < n\))에 대해, \(x(i, j)\) = 동전 \(v_i, \ldots, v_j\)에서 (내 차례로) 시작할 때 내가 얻을 수 있는 최대 총 가치.
2. 관계. 나는 동전 \(i\)나 동전 \(j\)를 가져가야 한다(추측). 그다음은 너의 차례이므로 너는 각각 \(x(i+1, j)\) 또는 \(x(i, j-1)\)만큼 얻는다. 내가 얻는 값은 남은 동전 총합에서 이를 뺀 것이다.
\[x(i, j) = \max\left\{v_i + \sum_{k=i+1}^{j} v_k - x(i+1, j),\;\; v_j + \sum_{k=i}^{j-1} v_k - x(i, j-1)\right\}\]3. 위상 순서. \(j - i\) 증가 순.
4. 기저 사례. \(x(i, i) = v_i\).
5. 원래 문제. \(x(0, n-1)\). 부모 포인터로 전략을 복원한다.
6. 시간. 부분 문제 \(\Theta(n^2)\)개, 합을 계산하느라 각각 \(\Theta(n)\) 작업이므로 \(\Theta(n^3)\). 모든 구간 합 \(\sum_{k=i}^{j} v_k\)를 (역시 동적 계획법으로) \(\Theta(n^2)\) 시간에 미리 계산하면 \(\Theta(n^2)\)로 줄어든다(연습 문제).
두 번째 풀이: 부분 문제 확장
다음에 누가 둘 차례인지를 부분 문제에 추가하는 부분 문제 확장(subproblem expansion) 을 쓴다.
1. 부분 문제. 게임의 전체 상태, 즉 동전 구간 \(i..j\)와 다음에 둘 플레이어 \(p\)에 대응시킨다. \(x(i, j, p)\) = 플레이어 \(p \in \{\text{me}, \text{you}\}\)가 동전 \(v_i, \ldots, v_j\)에서 시작할 때 내가 얻을 수 있는 최대 총 가치.
2. 관계. 플레이어 \(p\)는 동전 \(i\)나 \(j\)를 고른다(추측). \(p\)가 나라면 그 값을 내가 얻고, 아니면 아무것도 얻지 못한다. 그다음은 상대 차례다. 상대는 내 몫을 최소화하려 하므로 min을 취한다.
\[\begin{aligned} x(i, j, \text{me}) &= \max\{v_i + x(i+1, j, \text{you}),\; v_j + x(i, j-1, \text{you})\} \\ x(i, j, \text{you}) &= \min\{x(i+1, j, \text{me}),\; x(i, j-1, \text{me})\} \end{aligned}\]3. 위상 순서. \(j - i\) 증가 순.
4. 기저 사례. \(x(i, i, \text{me}) = v_i\), \(x(i, i, \text{you}) = 0\).
5. 원래 문제. \(x(0, n-1, \text{me})\). 부모 포인터로 전략을 복원한다.
6. 시간. 부분 문제 \(\Theta(n^2)\)개, 각각 \(\Theta(1)\) 작업이므로 \(\Theta(n^2)\).
부분 문제 제약과 확장
이번 강의에서 부분 문제에 제약을 걸거나(LIS) 부분 문제를 확장하는(동전 게임) 두 가지 예를 보았다.
- 문제의 조건을 확인할 정보가 부족하거나, 재귀할 자연스러운 부분 문제가 없다면 부분 문제 제약/확장을 시도한다.
- 부분 문제와 제약이 많을수록 관계식이 활용할 정보가 늘어나 동적 계획법이 가능해진다.
- 보통 부분 문제의 개수와 관계식의 분기 수(복잡도) 사이에 trade-off가 있다.
정리
- 여러 입력이 있으면 각 입력의 접두사/접미사를 곱한 부분 문제를 쓴다. LCS는 \(x(i, j)\)로 \(O(\lvert A \rvert \lvert B \rvert)\)에 풀린다.
- LCS 관계식은 첫 문자가 같으면 함께 쓰고, 다르면 어느 쪽을 버릴지 추측한다.
- LIS는 “\(A[i]\)를 포함한다”는 제약을 부분 문제에 넣어 증가 조건을 확인 가능하게 만들고, \(O(\lvert A \rvert^2)\)에 풀린다. 원래 문제는 모든 \(x(i)\)의 최댓값이다.
- 동전 게임은 구간 부분 문제 \(x(i, j)\)와 제로섬 성질로 \(\Theta(n^3)\), 차례 정보를 추가한 확장 \(x(i, j, p)\)로 \(\Theta(n^2)\)에 풀린다.
- 부분 문제를 제약/확장하면 관계식에 필요한 정보가 생기며, 부분 문제 수와 분기 수 사이의 균형을 고려해야 한다.