[풀이법 정리] 동적 프로그래밍은 "DAG 그리기"다

핵심 내용

동적 프로그래밍(dynamic programming)은?

• "careful brute force"
• guessing + recursion + memoization
• 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결하며, 부분 문제가 서로 중복될 때 적용 가능함
• 일반적으로 최적화 문제(optimization problem)에 동적 프로그래밍을 적용함
• 동적 프로그래밍 문제의 일반적인 시간 복잡도는 '부분 문제의 개수' x '부분 문제 당 소요 시간'이며, 이 때 재귀 호출의 비용은 고려하지 않음

동적 프로그래밍은 부분 문제 그래프(DAG) 그리기!

• 동적 프로그래밍 문제는 '최적해의 값을 재귀적으로 정의'하는 작업이 중요
• 그 다음에는 부분 문제들이 서로 어떻게 연관되어 있는지를 파악하면서 그 관련성을 전체의 부분 문제로 확장하면 본래의 문제를 어떻게 풀어야 하는지 알 수 있음
• 즉, 부분 문제를 노드, 부분 문제들 간 선후 관계를 간선으로 하는 '방향성 비순환 그래프(DAG)'를 그리고, 이를 위상 정렬된 순서 혹은 역순으로 풀면 본래의 문제를 해결 가능함
• 이 때 활용되는 메모 테이블은 부분 문제들의 최적해를 저장하는 공간이며(!) 그러므로 메모 테이블의 형태와 크기는 전체 부분 문제의 형태와 크기를 따름
• 당연히도 부분 문제 그래프에 순환이 발생한다면 그 문제는 동적 프로그래밍으로 해결할 수 없음

하향식? 상향식?

• 구분
  • 본래의 문제를 작은 문제로 분할하면서 내려오면 하향식 (top-down)
  • 작은 문제들을 먼저 풀면서 본래의 문제까지 쌓아 올라오면 상향식 (bottom-up)
• 그래프로 이해하기
  • 부분 문제 v0의 최적해를 구하기 위해 부분 문제 v1, v2의 최적해가 필요하다면, 부분 문제들을 노드로, 부분 문제들 간 선후 관계를 간선 (v1, v0)와 (v2, v0)로 표현 가능
  • 이 때, v0을 v1, v2로 분할한 뒤 결합하면 하향식
  • v1, v2를 먼저 해결한 뒤 v0을 해결하면 상향식
  • 즉, 부분 문제를 위상 정렬된 순서 혹은 역순으로 문제를 해결하는 것!
• 상향식/하향식의 사용 시점
  • 모든 부분 문제를 적어도 한 번씩 풀어야 한다면 '상향식'이 유리
    • 위 경우 상향식이 하향식보다 반복되는 재귀 호출을 위한 부담이 없고, 테이블을 유지하는 데 드는 비용이 적어 상수 배만큼 더 빠른 수행 시간을 보임
    • 이 때, (편하게 말해) 작은 문제들이 먼저 해결된 뒤 그 다음 크기의 문제들이 해결될 수 있도록 구성하는 것이 중요함
  • 일부의 부분 문제들의 해가 필요 없다면 '하향식'이 유리
    • 위 경우 필요한 부분 문제만 계산하는 하향식이 더 빠른 수행 시간을 보일 수 있음

일반화된 풀이 순서

아래의 풀이 순서 및 예시는 MIT의 알고리즘101 강의에서 DP편의 내용을 기반으로 작성함
MIT CS 알고리즘101 강의 DP편 링크

1. 부분 문제 정의하기
   • 부분 문제의 개수 세기 (#subproblem)
     • 먼저, 하나의 부분 문제를 해결하기 위해 해결되어야 하는 부분 문제 찾기
     • 그 다음, 풀어야 하는 전체 부분 문제의 개수 파악하기
2. 부분 문제의 최적해 예측하기
   • 특정 부분 문제의 최적해를 결정할 때, 고려 가능한 경우의 수 세기 (#choice)
     • 문제에 따라 최적해를 결정하는 경우의 수가 여러 개일 수 있음
     • 가령, '피보나치 수열' 문제는 fib(n)의 최적해를 결정하는 경우의 수가 fib(n-1) + fib(n-2) 로 1개 뿐
     • 반면, '행렬 곱셈 순서' 등의 문제는 여러 부분 문제의 최적해 중 최소값/최대값을 본인의 최적해에 반영함 (즉, 최적해의 경우의 수가 여러 개)
3. 부분 문제의 최적해를 재귀적으로 정의하기
   • 부분 문제들 간의 관계를 재귀식으로 작성하기
   • 부분 문제 당 소요시간 계산하기
4. 하향식 혹은 상향식으로 풀이 구성하기
   • 부분 문제 그래프(DAG) 그리기
     • 그래프의 구성 요소
       • 노드: 부분 문제
       • 간선: 부분 문제들 간 선후관계
     • 그래프 그리는 순서
       • 일차로, 하나의 부분 문제와 그에 선행하는 문제들로 작은 DAG 구성
       • 그 다음 아래로는 가장 작은 문제, 위로는 본래의 문제까지 DAG를 확장
   • 부분 문제들 간 위상 정렬된 순서를 파악하기 (topological order)
     • 순환 여부 체크하기
   • 메모 테이블 구성하기
     • 메모 테이블은 부분 문제들의 최적해를 저장하는 공간!
     • 전체 부분 문제의 형태와 크기에 따라 메모 테이블 구성
     • 부분 문제의 풀이 순서를 고려해 저장 및 탐색이 용이하도록 구성
   • 상향식 혹은 하향식으로 전체 문제 해결하기
     • 전체 풀이의 시간 복잡도는 #subproblem x time/subproblem
5. 본래의 문제 해결하기
   • 부분 문제 중 하나인 경우
     • 피보나치 등
   • 부분 문제들의 최적해를 조합해야 하는 경우
     • 외판원 순회 등

• (덧) 문자열/시퀀스의 부분 문제
  • suffixes x[i:] : Θ(len(x))
  • prefixes x[:i] : Θ(len(x))
  • substrings x[i:j] : Θ(len(x)^2)

적용하기

피보나치 수열

문제

• 백준 2748번 피보나치 수2

접근 방식

1. 부분 문제 정의하기
   • fib(0) = fib(1) = 1
   • fib(2) = fib(0) + fib(1) = 1
   • fib(3) = fib(1) + fib(2) = 2
   • fib(4) = fib(2) + fib(3) = 3
   • ...
   • fib(n) = fib(n-2) + fib(n-1)
     • #subprobs: n
2. 부분 문제의 최적해 예측하기
   • 최적해를 결정할 때 고려 가능한 경우의 수는 1개 뿐임
3. 부분 문제의 최적해를 재귀적으로 정의하기
   • fib(k) = fib(k-2) + fib(k-1)
     • time/subprob: Θ(1)
4. 풀이 구성하기
   • 부분 문제 그래프 그리기
     
   • 풀이 순서 (topological order)
     • for k in range(1, n)
     • 전체 소요시간(#subprobs x time/subprob): Θ(n)
   • 메모 테이블 구성
     • 전체 부분 문제는 k 가 0~n 일 때이므로, 길이 N+1의 1차원 배열 생성
   • 상향식 혹은 하향으로 해결하기
     • 아래 제출 답안 참고
5. 본래의 문제 해결하기
   • fib(n) 혹은 memo[n]

제출 답안

import sys
N = int(sys.stdin.readline())

# 상향식
fib = [0] * (N+1)
for i in range(1, N+1):
    if i <= 2:
        fib[i] = 1
    else:
        fib[i] = fib[i-1] + fib[i-2]

print(fib[N])

# 하향식
memo = [0] * (N+1)
def f(n):
    if memo[n] != 0:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = f(n-1) + f(n-2)
    return memo[n]

print(f(N))

행렬 곱셈 순서

문제

• https://www.acmicpc.net/problem/11049

접근 방식

1. 부분 문제 정의하기

   • 만약 행렬 곱셈이 AxBxCxDxE 라면, 아래 경우의 수 중에 최소값
     • (A)x(BCDE)
     • (AB)x(CDE)
     • (ABC)x(DE)
     • (ABCD)x(E)
   • 부분 문제 AxBxC 는, 다시 아래 경우의 수 중에 최소값
     • (A)x(BC)
     • (AB)x(C)
   • 부분 문제 BxC는, 하나의 값
     • (B)x(C)
   • 부분 문제의 개수
     • 하나의 부분 문제 seq[i:j+1]의 최적해를 구하기 위해서는 (j-i)x2개의 부분 문제에 대한 최적해가 필요함 (고려할 선택지는 (j-i)개)
     • 가장 작은 부분 문제는 길이가 1인 부분 문제들일 것이고, 길이가 1인 부분 문제를 풀어야 길이가 2인 부분 문제를 풀 수 있음 (topological order)
       • 길이가 1인 부분 문제: seq[0:1], ... seq[n-1:n] # 최적해의 값 0
       • 길이가 n인 부분 문제: seq[0:n] # 본래의 문제
     • 결과적으로 전체 부분 문제는 길이가 1인 부분 문제부터 길이가 len(seq)인 부분 문제까지 n*n개일 것
       • 정확히는 n개 중에서 2개의 인덱스 i,j를 고르는 nC2개의 부분 문제

2. 부분 문제의 최적해 예측하기

   • 부분 문제 seq[0:5]의 최적해를 결정할 때 4개의 선택지 존재
   • 하나의 부분 문제 seq[i:j+1]의 최적해를 결정할 때 j-i개의 선택지 존재
     • f(ABCD) = min( f(A)와 f(BCD)의 조합, f(AB)와 f(CD)의 조합, f(ABC)와 f(CD)의 조합)
     • 각 선택지는 부분 문제 2개의 최적해를 필요로 함

3. 부분 문제의 최적해를 재귀적으로 정의하기

   • f(i,i) = 0
   • f(i,j) = min( f(i,k) + f(k+1,j) + cal(i,k,j) for k in range(i,j) )
     • 이 때, cal(i,k,j)는 행렬M(i)~M(k)와 행렬M(k+1)~M(j)를 곱하는데 필요한 계산
     • 즉, cal(i,k,j) = (행렬 i의 행) * (행렬 k의 열) * (행렬 j의 열)
   • 부분 문제당 소요시간: O(j-i) = O(n)

4. 풀이 구성하기

   • 부분 문제 그래프 그리기
     
     • DAG를 2차원 매트릭스로 표현
     • 매트릭스의 각 셀에는 대응하는 부분 문제의 최적해를 저장
   • 메모 테이블 구성
     • 전체 부분 문제는 0<=i<n, 0<=j<n인 f(i,j)
     • 그러므로 n x n의 매트릭스 생성
     • memo[i][j] = seq[i:j+1]의 최적해
   • 풀이 순서 (topological order)
     • 모든 부분 문제를 한 번씩 거치므로 상향식으로 구성
     • 부분 문제의 길이 순서대로 해결
       • 부분 문제들이 좌측하단에서 우측상단 방향으로 해결되어 나가는 한,
       • 풀이 순서를 정할 때 행, 열, 대각선 중 무엇이든 기준으로 삼을 수 있음
   • 전체 소요시간(#subprob x time/subprob): O(n^3)
     • 부분 문제 개수 O(n^2)
     • 부분 문제 당 소요시간 O(n)

5. 본래의 문제 해결하기

   • memo[0][n-1] = seq[0:n]의 최적해

제출 답안

import sys

N = int(sys.stdin.readline())
matrices = []
for _ in range(N):
    m = tuple(map(int, sys.stdin.readline().split()))
    matrices.append(m)

# 메모 테이블 생성하기
memo = []
for _ in range(N):
    row = [0] * N
    memo.append(row)

# 부분 문제의 선후관계에 맞게 순서대로 부분 문제 해결하기
# - 대각선 방향으로 길이가 1인 부분 문제부터 길이가 n인 부분 문제까지 해결
# - diag은 c - r 이며, r == c 인 구간은 이미 0으로 설정되어 있으므로, 1부터 시작
for diag in range(1, N):
    for c in range(diag, N):
        r = c - diag
        m1, m3 = matrices[r], matrices[c]
        min_score = float("inf")
        for k in range(r, c):
            s1, s2 = memo[r][k], memo[k+1][c]
            m2 = matrices[k]
            score = s1 + s2 + m1[0]*m2[1]*m3[1]
            if score < min_score:
                min_score = score
        memo[r][c] = min_score

print(memo[0][N-1])
        

점프

문제

• https://www.acmicpc.net/problem/2253

접근 방식

1. 부분 문제 정의하기
   
   • 찾으려는 답은 위치 k에 진입했을 때 누적 점프 횟수의 최소값
   • 위치 k에 진입했을 때 누적 점프 횟수는 속도 v에 따라 다름
     • 가령, 위치 4에 속도 1로 진입했을 때 누적 점프 횟수 3회
     • 반면, 위치 4에 속도 2로 진입했을 때 누적 점프 횟수 2회
   • 동일 위치의 동일 속도이더라도 누적 점프 횟수가 다를 수 있음
     • 가령, 위치 5에 속도 1을 유지해 진입했을 때 누적 점프 횟수 4회
     • 반면, 위치 5에 속도 2에서 1을 감속해 진입했을 때 누적 점프 횟수 3회
     • 이 사례에서는 전자의 최적의 답이 될 수 없으므로 후자를 선택
     • 즉, (위치5, 속도1)인 부분 문제를 풀기 위해서는 (위치4,속도1)과 (위치4,속도2)의 부분 문제를 모두 고려해주어야 함
   • 전체 부분 문제의 개수는 위치(k) x 속도(v)
     • 위치 범위: 1 <= k <= 목표 지점 K
     • 속도 범위: 1 <= v <= 속도의 최대값 V
       • 속도의 최대값 V은 위치 1에서 출발하여 점프를 1번 할 때마다 속도가 1에서부터 1씩 계속 증가하여 목표 지점 K에 도착했을 때의 속도
       • 즉, sum(1, 2, ... V) = 이동거리 K-1 이며
       • V*V < V(V+1) = 2(K-1) 이므로
       • V < math.ceil(math.sqrt(2*K -2))
2. 부분 문제의 최적해 예측하기
   • f(k,v)를 '위치 k에 속도 v로 진입했을 때 누적 점프 횟수의 최소값'으로 정의
   • 위치 k에 속도 v로 진입할 수 있는 경우는 3가지
     • 위치 k - (v-1)에서 속도 1 가속
     • 위치 k - (v)에서 속도 유지
     • 위치 k - (v+1)에서 속도 1 감속
   • 그러므로 f(k,v)의 최적해를 결정하기 위한 선택지는 3개이며 선행되어야 하는 부분 문제 또한 3개
3. 부분 문제의 최적해를 재귀적으로 정의하기
   • f(k, v) = 1 + min( f(k-v, v-1), f(k-v, v), f(k-v, v+1) )
   • 부분 문제 당 소요시간: O(1)
4. 풀이 구성하기
   • 부분 문제 그래프 그리기
     • 상단 이미지 참고
   • 메모 테이블 구성
     • 전체 부분 문제의 형태와 크기에 맞게 구성
     • 위치 1~K x 속도 1~V-1의 매트릭스 형태로 구성
   • 풀이 순서 (topological order)
     • 위치 1부터 K까지 순차적으로 진행
   • 전체 소요 시간
     • O(KV)
5. 본래의 문제 해결하기
   • 부분 문제들의 최적해를 조합하는 경우에 해당
   • answer = min(f(K, v) for v in range(1, V))