3 Inseok Kong Schedule

Algorithms 18: Dynamic Programming 4: Rods, Subset Sum, Pseudopolynomial

정수를 부분 문제로 쓰는 막대 자르기와 부분집합 합 문제를 풀고, 다항 시간과 의사 다항 시간의 차이를 설명한 뒤, 지금까지 본 동적 계획법의 주요 특징을 분류해 정리한다.

복습: SRTBOT

SRTBOT의 부분 문제 정의에서 자주 쓰는 선택지는 접두사/접미사/부분 문자열, 여러 입력의 곱, 보조 변수로 기록한 부분 상태였다. 이번 강의의 초점은 하나 더 있다. 주어진 정수보다 작은 정수들을 부분 문제로 쓰는 것이다.

나머지 단계(관계, 위상 순서, 기저 사례, 원래 문제, 시간 분석)는 이전과 같다. 시간은 \(\sum_{x \in X} \text{work}(x)\)이며 재귀 호출은 \(O(1)\)로 센다.

막대 자르기

길이 \(L\)인 막대와, 모든 \(\ell \in \{1, 2, \ldots, L\}\)에 대해 길이 \(\ell\)인 막대의 가치 \(v(\ell)\)이 주어진다. 막대를 잘라 조각 가치의 합을 최대화하는 것이 목표다. 이것이 막대 자르기(rod cutting) 문제다.

예: \(L = 7\), \(v = [0, 1, 10, 13, 18, 20, 31, 32]\) (\(\ell = 0, 1, \ldots, 7\)).

\(\ell\) 0 1 2 3 4 5 6 7
\(v(\ell)\) 0 1 10 13 18 20 31 32

단위 길이당 가치가 가장 큰 조각을 탐욕적으로 고르면 될까? 아니다. \(\arg\max_\ell v[\ell]/\ell = 6\)이지만 \([6, 1]\)로 나누면 32로 최적이 아니다. 최적해는 \(v[2] + v[2] + v[3] = 10 + 10 + 13 = 33\)이다.

SRTBOT

1. 부분 문제. \(x(\ell)\) = 길이 \(\ell\)인 막대를 잘라 얻을 수 있는 최대 가치, \(\ell \in \{0, 1, \ldots, L\}\).

2. 관계. 첫 조각의 길이 \(p\)를 추측한다.

\[x(\ell) = \max\{v(p) + x(\ell - p) \mid p \in \{1, \ldots, \ell\}\}\]

3. 위상 순서. \(\ell\) 증가 순. \(x(\ell)\)은 엄격히 작은 \(\ell\)에만 의존하므로 비순환이다.

4. 기저 사례. \(x(0) = 0\) (길이 0인 막대는 가치가 없다).

5. 원래 문제. \(x(L)\). 선택을 저장해 자른 위치를 복원한다. 현재 길이가 \(\ell\)이고 최적 선택이 \(\ell'\)으로 가는 것이면, 잘라낸 조각은 \(p = \ell - \ell'\)이다. 이는 부분 문제 DAG에서의 최대 가중치 경로다.

6. 시간. 부분 문제 \(L + 1\)개, 부분 문제당 \(O(\ell) = O(L)\) 작업이므로 \(O(L^2)\).

# recursive (top down)
x = {}
def cut_rod(l, v):
    if l < 1: return 0                              # base case
    if l not in x:                                  # check memo
        for piece in range(1, l + 1):               # try piece
            x_ = v[piece] + cut_rod(l - piece, v)   # recurrence
            if (l not in x) or (x[l] < x_):         # update memo
                x[l] = x_
    return x[l]
# iterative with parent pointers
def cut_rod_pieces(L, v):
    x = [0] * (L + 1)                               # base case
    parent = [None] * (L + 1)                       # parent pointers
    for l in range(1, L + 1):                       # topological order
        for piece in range(1, l + 1):               # try piece
            x_ = v[piece] + x[l - piece]            # recurrence
            if x[l] < x_:                           # update memo
                x[l] = x_
                parent[l] = l - piece               # update parent
    l, pieces = L, []
    while parent[l] is not None:                    # walk back through parents
        piece = l - parent[l]
        pieces.append(piece)
        l = parent[l]
    return pieces

다항 시간인가?

(강) 다항 시간((strongly) polynomial time)이란 실행 시간이 워드 단위로 잰 입력 크기의 상수 차수 다항식으로 위에서 bound된다는 뜻이다. 막대 자르기의 입력 크기는 \(L + 1\)워드(정수 \(L\) 하나와 \(v\)의 정수 \(L\)개)다. \(O(L^2)\)은 \(L + 1\)의 상수 차수 다항식이므로, 그렇다. (강) 다항 시간이다.

부분집합 합

입력: 양의 정수 \(n\)개의 수열 \(A = \{a_0, a_1, \ldots, a_{n-1}\}\).

출력: 합이 정확히 \(T\)가 되는 \(A\)의 부분집합이 있는가? 즉 \(\sum_{a \in A'} a = T\)인 \(A' \subseteq A\)가 존재하는가?

예: \(A = (1, 3, 4, 12, 19, 21, 22)\), \(T = 47\)이면 \(A' = \{3, 4, 19, 21\}\)이 있다.

이것은 최적화 문제가 아니라 결정 문제(decision problem) 다. 답은 YES/NO(참/거짓)다. 위 예에서 답은 YES이지만, \(T = 2, 6, 9, 10, 11, \ldots\) 같은 값에서는 NO다.

SRTBOT

1. 부분 문제. \(x(i, t)\) = \(A[i:]\)의 어떤 부분집합의 합이 \(t\)인가? \(i \in \{0, 1, \ldots, n\}\), \(t \in \{0, 1, \ldots, T\}\).

2. 관계. 첫 원소 \(a_i\)가 유효한 부분집합 \(A'\)에 들어가는지 추측한다. 들어간다면 남은 원소로 \(t - a_i \ge 0\)을 만들어야 하고, 들어가지 않는다면 남은 원소로 \(t\)를 만들어야 한다.

\[x(i, t) = \text{OR}\begin{cases} x(i+1, t - A[i]) & t \ge A[i] \text{일 때} \\ x(i+1, t) & \text{항상} \end{cases}\]

3. 위상 순서. \(x(i, t)\)는 엄격히 큰 \(i\)에만 의존하므로 비순환이다. \(i\) 감소 순으로 푼다.

4. 기저 사례.

  • \(i \in \{0, \ldots, n\}\)에 대해 \(x(i, 0) = \text{YES}\) (정확히 채움).
  • \(t \in \{1, \ldots, T\}\)에 대해 \(x(n, t) = \text{NO}\) (더 넣을 원소가 없음).

5. 원래 문제. \(x(0, T)\).

예: \(A = (3, 4, 3, 1)\), \(T = 6\)이면 해는 \(A' = (3, 3)\)이다. 상향식으로는 부분 문제 \(5 \times 7 = 35\)개를 모두 풀지만, 하향식으로는 도달 가능한 부분 문제 14개만 푼다.

강의 노트의 그림은 이 예제를 격자로 그린다. 다만 그림은 Recitation 18처럼 접두사 버전을 쓴다. 행 \(i\)는 앞의 \(i\)개 원소 \(A[1..i]\)만 쓸 수 있는 상태(아래가 \(i = 0\), 위가 \(i = 4\))이고, 열 \(j\)는 만들려는 합이다. 정점 \((i, j)\)에서는 세로 간선이 \((i-1, j)\)로(“\(A[i]\)를 쓰지 않는다”), 기울어진 간선이 \((i-1, j - A[i])\)로(“\(A[i]\)를 쓴다”) 내려간다. 접미사 버전과 방향만 반대일 뿐 구조는 같다.

Subset sum subproblem grid with base cases marked \(A = (3, 4, 3, 1)\), \(T = 6\)인 부분집합 합의 부분 문제 격자와 기저 사례. 왼쪽 상자 안의 열 \(j = 0\)은 모두 참(T, 검은 점), 아래 상자 안의 행 \(i = 0\)은 \(j \ge 1\)에서 모두 거짓(F, 흰 점)이다. 출처: MIT 6.006 Lecture 18 notes (CC BY-NC-SA 4.0).

격자의 회색 점이 아직 풀지 않은 부분 문제다. 각 행의 오른쪽에 적힌 \(A[i]\) 값이 그 행에서 나가는 기울어진 간선의 가로 폭을 정한다. 예를 들어 맨 위 행은 \(A[4] = 1\)이므로 한 칸 왼쪽 아래로, 그 아래 행은 \(A[3] = 3\)이므로 세 칸 왼쪽 아래로 이어진다. 기울어진 간선은 \(j \ge A[i]\)일 때만 있으므로 왼쪽 가장자리 근처의 정점에는 세로 간선 하나만 있다. 모든 간선이 한 행 아래로 향하므로 격자는 DAG이고, 아래 행부터 위로 채우는 것이 위상 순서다.

Subset sum grid fully solved bottom up 상향식으로 모든 부분 문제를 푼 결과. 검은 점이 참, 흰 점이 거짓이며, 굵은 선은 각 참 값이 어느 참 값에서 왔는지를 나타낸다. 오른쪽 위 상자가 원래 문제 \(x(4, 6)\)이다. 출처: MIT 6.006 Lecture 18 notes (CC BY-NC-SA 4.0).

맨 위 행을 읽으면 원소 네 개로 만들 수 있는 합이 0, 1, 3, 4, 5, 6이고 2만 만들 수 없음을 알 수 있다. 원래 문제 \(x(4, 6)\)에서 굵은 선을 거꾸로 따라가면 해가 복원된다. \((4, 6)\)에서 세로로 내려가 \((3, 6)\)으로 가므로 \(A[4] = 1\)은 쓰지 않는다. \((3, 6)\)에서는 기울어진 선을 타고 \((2, 3)\)으로 가므로 \(A[3] = 3\)을 쓴다. \((2, 3)\)에서 세로로 \((1, 3)\), 다시 기울어진 선으로 \((0, 0)\)에 닿으므로 \(A[1] = 3\)을 쓴다. 따라서 \(A' = (3, 3)\)이다. 굵은 선 하나하나가 부모 포인터 역할을 하는 셈이다.

Subset sum solved top down, visiting only reachable subproblems 하향식 풀이. 왼쪽은 원래 문제 \(x(4, 6)\)에서 출발하기 전의 격자이고, 오른쪽은 메모이제이션 재귀가 실제로 방문한 부분 문제(흰 점과 검은 점)와 그 의존 간선(굵은 선)이다. 방문하지 않은 부분 문제는 회색으로 남는다. 출처: MIT 6.006 Lecture 18 notes (CC BY-NC-SA 4.0).

오른쪽 그림에서 굵은 선은 \((4, 6)\)에서 시작해 아래로 퍼져 나간다. 각 정점은 많아야 두 개의 정점을 호출하고, 같은 정점에 두 번 도달하면 메모를 조회한다. 바닥 행에서 실제로 닿은 기저 사례는 상자로 표시된 \(j = 0, 1, 2, 5\)의 네 개뿐이고, \((0, 0)\)만 참이다. 방문한 부분 문제는 모두 14개로, 상향식이 채우는 35개의 절반에도 못 미친다.

두 그림의 차이가 하향식과 상향식의 실용적인 차이다. 상향식은 위상 순서대로 모든 칸을 채우므로 구현이 단순하고 재귀 오버헤드가 없지만, 원래 문제와 무관한 칸까지 계산한다. 하향식은 원래 문제에서 도달 가능한 칸만 계산한다. 최악의 경우 둘 다 \(O(nT)\)이지만, \(T\)가 크고 원소가 적을 때는 도달 가능한 칸이 훨씬 적을 수 있다.

6. 시간. 부분 문제 \(O(nT)\)개, 각각 \(O(1)\) 작업이므로 \(O(nT)\).

def subset_sum(A, T):
    n = len(A)
    x = [[False] * (T + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        x[i][0] = True                              # base: sum 0 is always possible
    for i in reversed(range(n)):                    # decreasing i
        for t in range(1, T + 1):
            x[i][t] = x[i + 1][t]                   # don't use A[i]
            if t >= A[i] and x[i + 1][t - A[i]]:    # use A[i]
                x[i][t] = True
    return x[0][T]

다항 시간인가? 의사 다항 시간

부분집합 합의 입력 크기는 \(n + 1\)워드(정수 \(T\) 하나와 \(A\)의 정수 \(n\)개)다. \(O(nT)\)는 \(n + 1\)의 다항식으로 bound될까? 반드시 그렇지는 않다.

워드 크기가 \(w\)비트인 word-RAM에서 \(T \le 2^w\)이고 \(w \ge \lg(n+1)\)이지만, \(w\)의 상한은 없다. 예를 들어 \(w = n\)도 무리한 가정이 아닌데, 그러면 실행 시간은 \(O(n 2^n)\)으로 지수적이다.

의사 다항 시간

알고리즘이 의사 다항 시간(pseudopolynomial time) 이라는 것은 실행 시간이 입력 크기와 입력 정수들의 상수 차수 다항식으로 bound된다는 뜻이다.

  • 이런 알고리즘은 정수들이 입력 크기의 다항식, 즉 \(n^{O(1)}\)으로 bound되는 경우에 다항 시간이 된다. 기수 정렬이 \(O(n)\)에 동작하는 것과 같은 조건이다.
  • 이미 본 의사 다항 알고리즘: 계수 정렬 \(O(n + u)\), 기수 정렬 \(O(n \log_n u)\), 직접 접근 배열 구축 \(O(n + u)\), 피보나치 \(O(n)\).
  • 기수 정렬은 사실 약 다항(weakly polynomial) 이다. 이는 강 다항과 의사 다항의 중간 개념으로, 비트 단위로 잰 입력 크기, 즉 입력 정수의 로그에 대한 상수 차수 다항식으로 bound된다는 뜻이다.

막대 자르기와 대조해 보자. 막대 자르기도 \(L\)에 대해 의사 다항적으로 의존했지만, 다행히 입력에 정수가 \(L\)개 이상 있었기 때문에 다항 시간이었다. 만약 팔 수 있는 막대 길이의 일부만 주어진다면(막대 자르기와 부분집합 합을 일반화한 배낭 문제(knapsack problem)) 알고리즘은 의사 다항 시간일 뿐이다.

Recitation 예제: 0-1 배낭과 변형

Recitation 18은 부분집합 합의 변형들을 다룬다.

0-1 배낭(0-1 knapsack). 크기 \(S\)인 배낭과 크기 \(s_i\), 가치 \(v_i\)인 물건들이 있다. 각 물건을 0개 또는 1개 골라 \(\sum s_i \le S\)이면서 \(\sum v_i\)를 최대화한다. 모든 \(v_i = s_i\)이면 부분집합 합과 같다. 예: \(\{(6, 6), (9, 9), (10, 12)\}\), \(S = 15\)이면 마지막 물건을 뺀 집합이 최적이다(가치 15). 단위 크기당 가치로 고르는 탐욕법은 실패한다.

  • 부분 문제: \(x(i, j)\) = 물건 \(1..i\)로 크기 \(j\)인 배낭을 채울 때의 최대 가치.
  • 관계: 마지막 물건을 넣는지 추측한다.
\[x(i, j) = \max\begin{cases} v_i + x(i-1, j - s_i) & j \ge s_i \text{일 때} \\ x(i-1, j) & \text{항상} \end{cases}\]
  • 기저 사례: \(x(i, 0) = 0\), \(x(0, j) = 0\). 원래 문제: \(x(n, S)\). 시간: \(O(nS)\)로 의사 다항이다.

분할(partition). 양의 정수 집합을 합이 같은 두 집합으로 나눌 수 있는지는 \(S = \frac{1}{2} \sum_{a \in A} a\)로 부분집합 합을 풀면 된다. 차이를 최소화하는 분할은 \(S' \le \frac{1}{2}\sum a\) 중 참인 가장 큰 \(S'\)을 찾으면 되며 여전히 \(O(nS)\)다.

무제한 배낭(unbounded knapsack). 같은 물건을 여러 번 쓸 수 있으면 \(x(j) = \max(\{v_i + x(j - s_i) \mid s_i \le j\} \cup \{0\})\)로 부분 문제 \(O(S)\)개, 각각 \(O(n)\) 작업, 총 \(O(nS)\)에 풀린다.

복잡도와의 연결

정수가 다항식으로 bound되지 않을 때 부분집합 합을 다항 시간에 풀 수 있을까? \(\text{P} \ne \text{NP}\)라면 불가능하다. 그것이 무슨 뜻인지는 다음 강의에서 다룬다.

동적 계획법의 주요 특징

강의에서 본 예제들을 특징별로 분류하면 다음과 같다.

부분 문제

  • 접두사/접미사: 볼링, LCS, LIS, Floyd-Warshall, 막대 자르기(사실상 정수 부분 문제), 부분집합 합
  • 부분 문자열: 번갈아 동전 게임, 산술식 괄호 배치
  • 여러 수열: LCS
  • 정수: 피보나치, 막대 자르기, 부분집합 합 (의사 다항: 피보나치, 부분집합 합)
  • 정점: DAG 최단 경로, Bellman-Ford, Floyd-Warshall

부분 문제 제약/확장

  • 확장 없는 제약: LIS (첫 원소 포함)
  • 2배 확장: 번갈아 동전 게임(누가 먼저 두는가), 산술식 괄호 배치(min/max)
  • \(\Theta(1)\)배 확장: 피아노 운지(첫 손가락 배정)
  • \(\Theta(n)\)배 확장: Bellman-Ford(간선 수)

관계 (분기 수 = 각 부분 문제가 의존하는 부분 문제 수)

  • \(\Theta(1)\) 분기: 피보나치, 볼링, LCS, 번갈아 동전 게임, Floyd-Warshall, 부분집합 합
  • \(\Theta(\text{degree})\) 분기(실행 시간에서 \(\lvert E \rvert\)의 원천): DAG 최단 경로, Bellman-Ford
  • \(\Theta(n)\) 분기: LIS, 산술식 괄호 배치, 막대 자르기
  • 여러 해를 결합(부분 문제 DAG에서의 경로가 아님): 피보나치, Floyd-Warshall, 산술식 괄호 배치

원래 문제

  • 여러 부분 문제를 결합: DAG 최단 경로, Bellman-Ford, Floyd-Warshall, LIS, 피아노 운지

정리

  • 정수 자체를 부분 문제의 매개변수로 쓰는 동적 계획법이 있다. 막대 자르기는 \(x(\ell)\)로 \(O(L^2)\), 부분집합 합은 \(x(i, t)\)로 \(O(nT)\)에 풀린다.
  • 막대 자르기에서 단위 길이당 가치 기준의 탐욕법은 최적이 아니다(\(L = 7\) 예에서 32 대 33).
  • 강 다항 시간은 워드 단위 입력 크기의 다항식, 의사 다항 시간은 입력 크기와 입력 정수 값의 다항식으로 bound되는 시간이다.
  • 막대 자르기는 입력에 정수가 \(L\)개 이상 있어 다항 시간이지만, 부분집합 합의 \(O(nT)\)는 \(T\)가 \(2^n\)처럼 크면 지수적이다.
  • 계수 정렬, 기수 정렬, 직접 접근 배열, 피보나치도 의사 다항 알고리즘이며, 기수 정렬은 약 다항이다.
  • 동적 계획법은 부분 문제 종류, 제약/확장의 크기, 관계의 분기 수, 원래 문제의 결합 방식으로 분류할 수 있다.