3 Inseok Kong Schedule

Algorithms 17: Dynamic Programming 3: APSP, Parens, Piano

부분 문제 확장을 중심으로 Bellman-Ford를 동적 계획법으로 다시 유도하고, Floyd-Warshall 전체 쌍 최단 경로, 산술식 괄호 배치, 피아노 운지 문제를 SRTBOT으로 정리한다.

복습: SRTBOT과 DAG 최단 경로

SRTBOT 단계는 부분 문제 정의, 관계, 위상 순서, 기저 사례, 원래 문제, 시간 분석이다. 부분 문제는 접두사/접미사/부분 문자열, 여러 입력의 곱, 보조 변수로 기록한 부분 상태 등으로 정한다. 관계식은 답을 알면 문제가 작아지는 질문을 찾아 모든 답을 국소적으로 무차별 대입해 세운다. 시간은 \(\sum_{x \in X} \text{work}(x)\)이다.

15강의 DAG 최단 경로는 다음과 같았다.

  • 부분 문제: 모든 \(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\)의 위상 순서.

그래프에 사이클이 있으면 이 관계식은 순환 의존을 만들어 동적 계획법이 되지 않는다.

단일 출발점 최단 경로 다시 보기

1. 부분 문제. 정보를 추가해 의존을 비순환으로 만드는 부분 문제 확장을 쓴다(이미 본 적 있는 예다). \(\delta_k(s, v)\) = \(s\)에서 \(v\)까지 간선을 최대 \(k\)개 쓰는 최단 경로의 가중치, \(v \in V\), \(0 \le k \le \lvert V \rvert\).

2. 관계. 최단 경로의 마지막 간선 \((u, v)\)를 추측한다.

\[\delta_k(s, v) = \min(\{\delta_{k-1}(s, u) + w(u, v) \mid (u, v) \in E\} \cup \{\delta_{k-1}(s, v)\})\]

3. 위상 순서. \(k\) 증가 순. 각 부분 문제는 \(k\)가 엄격히 작은 부분 문제에만 의존한다.

4. 기저 사례. \(\delta_0(s, s) = 0\), \(v \ne s\)이면 \(\delta_0(s, v) = \infty\) (간선 없음).

5. 원래 문제. 최단 경로가 유한하면 \(\delta(s, v) = \delta_{\lvert V \rvert - 1}(s, v)\)이다. 그렇지 않으면 어떤 \(v\)에 대해 \(\delta_{\lvert V \rvert}(s, v) < \delta_{\lvert V \rvert - 1}(s, v)\)이고, 그 경로는 음의 가중치 사이클을 포함한다. 관계식을 최소화한 부분 문제를 부모 포인터로 기록할 수 있다.

6. 시간. 부분 문제 \(\lvert V \rvert \times (\lvert V \rvert + 1)\)개, \(\delta_k(s, v)\)의 작업량은 \(O(\deg_{\text{in}}(v))\)이다.

\[\sum_{k=0}^{\lvert V \rvert} \sum_{v \in V} O(\deg_{\text{in}}(v)) = \sum_{k=0}^{\lvert V \rvert} O(\lvert E \rvert) = O(\lvert V \rvert \cdot \lvert E \rvert)\]

이것이 바로 Bellman-Ford다(계산 순서만 약간 다르다).

전체 쌍 최단 경로: Floyd-Warshall

Bellman-Ford처럼 \(\delta_k(u, v)\) = \(u\)에서 \(v\)까지 간선을 최대 \(k\)개 쓰는 경로의 최소 가중치로 정의할 수도 있다. 하지만 그러면 Bellman-Ford를 \(\lvert V \rvert\)번 돌리는 것과 같아 \(O(\lvert V \rvert^2 \cdot \lvert E \rvert) = O(\lvert V \rvert^4)\)이 된다.

14강의 Johnson 알고리즘은 \(O(\lvert V \rvert^2 \log \lvert V \rvert + \lvert V \rvert \cdot \lvert E \rvert) = O(\lvert V \rvert^3)\)을 달성한다. 간단한 동적 계획법인 Floyd-Warshall로도 \(\Theta(\lvert V \rvert^3)\)을 얻을 수 있어, 밀집 그래프에서 Johnson과 같은 성능을 낸다.

정점에 \(V = \{1, 2, \ldots, \lvert V \rvert\}\)로 번호를 붙인다.

1. 부분 문제. \(x(u, v, k)\) = \(\{1, 2, \ldots, k\} \cup \{u, v\}\)에 속한 정점만 사용하는 \(u\)에서 \(v\)까지 경로의 최소 가중치, \(u, v \in V\), \(0 \le k \le \lvert V \rvert\).

2. 관계. 경로가 정점 \(k\)를 지나는지 아닌지만 따지면 된다.

\[x(u, v, k) = \min\{x(u, k, k-1) + x(k, v, k-1),\; x(u, v, k-1)\}\]

분기 수가 상수다. 이전 정점이나 간선을 추측하지 않는다.

3. 위상 순서. \(k\) 증가 순. 관계식은 더 작은 \(k\)에만 의존한다.

4. 기저 사례.

  • \[x(u, u, 0) = 0\]
  • \((u, v) \in E\)이면 \(x(u, v, 0) = w(u, v)\)
  • 그 외에는 \(x(u, v, 0) = \infty\)

5. 원래 문제. 모든 \(u, v \in V\)에 대해 \(x(u, v, \lvert V \rvert)\).

6. 시간. 부분 문제 \(O(\lvert V \rvert^3)\)개, 각각 \(O(1)\) 작업이므로 \(O(\lvert V \rvert^3)\). 부분 문제마다 의존이 상수 개이므로 실행 시간의 \(O(\lvert E \rvert)\) 인수가 \(O(\lvert V \rvert)\)로 내려온다.

def floyd_warshall(V, w):           # V = [1, ..., |V|], w: dict of edge weights
    INF = float('inf')
    x = { (u, v): (0 if u == v else w.get((u, v), INF)) for u in V for v in V }
    for k in V:                     # topological order: increasing k
        for u in V:
            for v in V:             # relation (in place: only shorter or equal)
                if x[(u, k)] + x[(k, v)] < x[(u, v)]:
                    x[(u, v)] = x[(u, k)] + x[(k, v)]
    return x

위 코드는 \(k\) 차원을 덮어쓰는 흔한 구현이다. 단계 \(k\)에서 \(x(u, k)\)와 \(x(k, v)\)는 바뀌지 않으므로(음의 사이클이 없다면) 결과가 같다.

산술식 괄호 배치

입력: 산술식 \(a_0 *_1 a_1 *_2 a_2 \cdots *_{n-1} a_{n-1}\). 각 \(a_i\)는 정수이고 각 \(*_i \in \{+, \times\}\)다.

출력: 식의 값을 최대화하는 괄호 위치.

예: \(7 + 4 \times 3 + 5 \to ((7) + (4)) \times ((3) + (5)) = 88\).

음수도 허용한다. 예: \(7 + (-4) \times 3 + (-5) \to ((7) + ((-4) \times ((3) + (-5)))) = 15\).

1. 부분 문제. 각 부분 구간을 최대화하는 것만으로 충분할까? 아니다. \((-3) \times (-3) = 9 > (-2) \times (-2) = 4\)이므로, 곱셈에서는 두 피연산자를 최소화하는 편이 더 클 수 있다. 그래서 최솟값과 최댓값을 모두 기록하도록 확장한다.

부분 문제 \(x(i, j, \text{opt})\)는 \(a_i *_{i+1} \cdots *_{j-1} a_{j-1}\)에 괄호를 쳐서 얻을 수 있는 opt 값이다. 범위는 \(0 \le i < j \le n\), \(\text{opt} \in \{\min, \max\}\).

2. 관계. 가장 바깥 괄호의 위치, 즉 마지막에 계산되는 연산을 추측한다.

\[x(i, j, \text{opt}) = \underset{\substack{i < k < j \\ \text{opt}', \text{opt}'' \in \{\min, \max\}}}{\text{opt}} \; x(i, k, \text{opt}') *_k x(k, j, \text{opt}'')\]

3. 위상 순서. \(j - i\) 증가 순. \(x(i, j, \text{opt})\)는 \(j - i\)가 엄격히 작은 부분 문제에만 의존한다.

4. 기저 사례. \(x(i, i+1, \text{opt}) = a_i\). 수가 하나뿐이고 남은 연산이 없다.

5. 원래 문제. \(x(0, n, \max)\). 괄호 배치를 찾으려면 부모 포인터를 두 개 저장한다. 결과는 이진 트리를 이룬다.

6. 시간. 부분 문제는 \(n \cdot n \cdot 2 = O(n^2)\)개 미만, 부분 문제당 작업은 \(O(n) \cdot 2 \cdot 2 = O(n)\)이므로 \(O(n^3)\).

피아노 운지

오른손으로 칠 단음 \(n\)개의 수열 \(t_0, t_1, \ldots, t_{n-1}\)이 주어진다(여러 음과 양손은 뒤에서 일반화한다). 오른손가락은 \(1, 2, \ldots, F\)이다(대부분의 사람은 \(F = 5\)). 음 \(t\)를 손가락 \(f\)로 친 뒤 음 \(t'\)를 손가락 \(f'\)로 치는 전이의 난이도 \(d(t, f, t', f')\)가 주어진다. 보통 여러 페널티의 합이다.

  • \(1 < f < f'\)이고 \(t > t'\)이면 불편하다.
  • 레가토(legato, 부드러운 연주)에는 \(t \ne t'\)이어야 한다(아니면 무한대 페널티).
  • 약한 손가락 규칙: \(f' \in \{4, 5\}\)는 피하는 것이 좋다.
  • \(\{f, f'\} = \{3, 4\}\)는 거북하다.

목표는 각 음에 손가락을 배정해 총 난이도를 최소화하는 것이다.

첫 시도

1. 부분 문제. \(x(i)\) = 음 \(t_i, t_{i+1}, \ldots, t_{n-1}\)을 치는 최소 총 난이도.

2. 관계. 첫 손가락, 즉 \(t_i\)에 배정할 \(f\)를 추측한다.

\[x(i) = \min\{x(i+1) + d(t_i, f, t_{i+1}, ?) \mid 1 \le f \le F\}\]

그런데 \(?\)를 채울 정보가 없다. \(x(i+1)\)이 어느 손가락으로 시작하는지 알아야 한다. 시작 손가락에 따라 \(x(i+1)\)과 \(d(t_i, f, t_{i+1}, ?)\)가 모두 좋아지거나 나빠질 수 있으므로, 시작 손가락마다 \(x(i+1)\)의 최적해를 대응시키는 표가 필요하다. 즉 부분 문제를 시작 조건으로 확장해야 한다.

해법

1. 부분 문제. \(x(i, f)\) = 음 \(t_i\)를 손가락 \(f\)로 시작해 \(t_i, \ldots, t_{n-1}\)을 치는 최소 총 난이도, \(0 \le i < n\), \(1 \le f \le F\).

2. 관계. 다음 손가락, 즉 \(t_{i+1}\)에 배정할 \(f'\)을 추측한다.

\[x(i, f) = \min\{x(i+1, f') + d(t_i, f, t_{i+1}, f') \mid 1 \le f' \le F\}\]

3. 위상 순서. \(i\) 감소 순(\(f\) 순서는 상관없음).

4. 기저 사례. \(x(n-1, f) = 0\) (전이가 없음).

5. 원래 문제. \(\min\{x(0, f) \mid 1 \le f \le F\}\).

6. 시간. 부분 문제 \(\Theta(n \cdot F)\)개, 부분 문제당 \(\Theta(F)\) 작업이므로 \(\Theta(n \cdot F^2)\). 서로 다른 음의 개수와는 무관하다.

def piano(t, F, d):
    n = len(t)
    x = [[0] * (F + 1) for _ in range(n)]        # base case: x[n-1][f] = 0
    for i in reversed(range(n - 1)):              # decreasing i
        for f in range(1, F + 1):
            x[i][f] = min(x[i + 1][g] + d(t[i], f, t[i + 1], g)
                          for g in range(1, F + 1))
    return min(x[0][f] for f in range(1, F + 1))

기타 운지

같은 음을 칠 수 있는 방법이 최대 \(S\)가지(줄 수)라면 “손가락”을 (음을 누르는 손가락, 음을 치는 줄)의 순서쌍으로 재정의한다. 알고리즘 전체에서 \(F\)가 \(F \cdot S\)로 바뀌므로 실행 시간은 \(\Theta(n \cdot F^2 \cdot S^2)\)이다.

여러 음을 동시에

이제 \(t_i\)가 시각 \(i\)에 칠 음의 집합이라 하자. 더 큰 전이 난이도 함수 \(d(t, f, t', f')\)가 주어진다. 목표는 각 음을 어떻게 짚을지(기타라면 어느 줄인지 포함) 정하는 운지 \(f_i : t_i \to \{1, 2, \ldots, F\}\)를 골라 다음을 최소화하는 것이다.

\[\sum_{i=1}^{n-1} d(t_{i-1}, f_{i-1}, t_i, f_i)\]

한 시각에 치는 음의 최대 개수를 \(T = \max_i \lvert t_i \rvert\)라 하면 각 운지 \(f_i\)의 선택지는 최대 \(T^F\)개다. 일반적인 피아노에서는 \(T \le F = 10\)이고(예외는 있다), 기타에서는 \(T \le S\)다.

  • 부분 문제 \(\Theta(n \cdot T^F)\)개
  • 부분 문제당 \(\Theta(T^F)\) 작업
  • 전체 \(\Theta(n \cdot T^{2F})\) 시간, \(T, F \le 10\)이면 \(\Theta(n)\) 시간

비디오 게임 응용

  • Guitar Hero / Rock Band: \(F = 4\) (서로 다른 음 5개).
  • Dance Dance Revolution: \(F = 2\) (두 발), \(T = 2\) (동시에 최대 두 음). 길게 누르는 음은 “각 발이 어디에 있는지”(화살표 위인지 가운데인지)를 접미사 부분 문제의 상태로 추가해 다룰 수 있다(연습 문제).

Recitation 예제

Recitation 17의 두 예제도 이번 강의의 주제, 곧 부분 문제를 확장하거나 모양을 잘 골라 관계식에 필요한 정보를 확보하는 방법을 보여 준다.

보물선 배치 (Treasureship)

\(2 \times n\) 격자의 각 칸에 양수나 음수 값이 있고, \(2 \times 1\) 배를 가로나 세로로 겹치지 않게 원하는 만큼 놓아 덮인 칸 값의 합을 최대화한다. 가장 오른쪽 칸을 비울지, 세로 배로 덮을지, 가로 배로 덮을지 추측하면, 남은 판은 직사각형이 아닐 수 있다.

Possible right-edge shapes of the remaining Treasureship board 남은 판의 오른쪽 끝 모양. 위 줄이 2행, 아래 줄이 1행이며, (0)은 두 행의 길이가 같고, (+1)은 2행이, (−1)은 1행이 한 칸 더 길다. 출처: MIT 6.006 Recitation 17 notes (CC BY-NC-SA 4.0).

그림의 # 하나가 격자 한 칸이다. 오른쪽 끝에서 가로 배 하나를 놓으면 한 행만 두 칸 줄어 두 행의 길이가 어긋나고, 이 어긋난 모양을 표현하려면 부분 문제에 “두 행의 길이 차이”라는 정보를 추가해야 한다. 노트는 차이가 \(\pm 2\)인 모양도 생각하지만, 두 가로 배가 위아래로 나란히 놓인 최적해는 같은 자리를 세로 배 두 개로 덮는 해로 바꿀 수 있으므로 그림의 세 모양 \(j \in \{0, +1, -1\}\)만으로 충분하다.

따라서 부분 문제는 \(x(i, j)\) = 1행의 열 \(1..i\)와 2행의 열 \(1..i+j\)로 이루어진 판에서의 최대 점수다. \(j = 0\)이면 열 \(i\)를 세로 배로 덮거나, 한 행의 끝 칸을 비워 \(j = \pm 1\) 모양으로 넘어간다. \(j = \pm 1\)이면 더 긴 행의 끝 칸을 가로 배로 덮거나 비운다. 칸 수 \(2i + j\)가 엄격히 줄어드므로 비순환이고, 부분 문제 \(O(n)\)개, 각각 \(O(1)\) 작업이므로 \(O(n)\) 시간이다.

웨이퍼 전원 (Wafer Power)

원형 웨이퍼 둘레에 포트 \(n\)개가 일정한 간격으로 놓여 있고, 각 포트는 전원이거나 연산 장치다. 연산 장치와 전원을 서로 교차하지 않는 전선으로 짝지어 전원을 받는 연산 장치 수를 최대화한다. 둘레에서 이웃한 두 포트는 너무 가까워 연결할 수 없다.

Example wafer with non-crossing wires between computing units and power sources 웨이퍼 예. 흰 점이 연산 장치, 검은 점이 전원이며, 굵은 선이 교차하지 않는 전선이다. 출처: MIT 6.006 Recitation 17 notes (CC BY-NC-SA 4.0).

그림에서 각 전선은 웨이퍼를 두 쪽으로 나눈다. 전선이 교차하지 않으므로, 한 전선의 한쪽에 있는 포트는 반대쪽 포트와 연결될 수 없고 각 쪽을 독립적으로 짝지어야 한다. 예를 들어 위쪽 검은 점에서 오른쪽 흰 점으로 가는 긴 전선의 오른쪽 위에는 짧은 전선 하나만, 왼쪽에는 나머지 세 전선이 들어 있다. 이처럼 원을 따라 연속한 포트들, 곧 부분 문자열이 자연스러운 부분 문제가 된다.

포트를 반시계 방향으로 \(a_1, \ldots, a_n\)이라 하고 \(x(i, j)\) = 포트 \(a_i, \ldots, a_j\)만으로 만들 수 있는 최대 연결 수라 하자. 첫 포트 \(a_i\)가 아무와도 연결되지 않거나, 어떤 \(a_t\)(\(t \ge i + 2\))와 연결된다고 추측한다. 연결되면 그 전선 안쪽 \(a_{i+1..t-1}\)과 바깥쪽 \(a_{t+1..j}\)를 독립적으로 푼다.

\[x(i, j) = \max\big(\{x(i+1, j)\} \cup \{m(i, t) + x(i+1, t-1) + x(t+1, j) \mid i + 2 \le t \le j\}\big)\]

여기서 \(m(i, t)\)는 두 포트의 종류가 다르면 1, 같으면 0이다. 원래 문제 \(x(1, n)\)에서는 \(a_1\)과 \(a_n\)도 원 위에서 이웃하므로 \(t \in \{3, \ldots, n-1\}\)만 시도한다. 부분 문제 \(O(n^2)\)개, 각각 \(O(n)\) 작업이므로 \(O(n^3)\) 시간이다. 산술식 괄호 배치처럼 구간을 둘로 나누는 지점을 추측하는 부분 문자열 동적 계획법이다.

정리

  • 사이클이 있는 그래프의 최단 경로는 간선 수 \(k\)를 추가한 부분 문제 \(\delta_k(s, v)\)로 비순환이 되고, 이것이 \(O(\lvert V \rvert \lvert E \rvert)\)의 Bellman-Ford다.
  • Floyd-Warshall은 “중간 정점을 \(\{1, \ldots, k\}\)로 제한”하는 부분 문제로 분기 수를 상수로 줄여 \(\Theta(\lvert V \rvert^3)\)에 전체 쌍 최단 경로를 구한다.
  • 산술식 괄호 배치는 음수 때문에 최솟값과 최댓값을 함께 기록해야 하며, 마지막 연산을 추측해 \(O(n^3)\)에 풀린다.
  • 피아노 운지는 시작 손가락을 부분 문제에 추가해야 전이 비용을 계산할 수 있고, \(\Theta(n F^2)\)에 풀린다.
  • 기타(\(F \to F \cdot S\))나 여러 음 동시 연주(\(T^F\) 상태)도 같은 틀로 일반화된다.
  • 관계식에 필요한 정보가 부족하면 부분 문제를 확장한다는 것이 이번 강의의 공통 주제다.