이번 글에서는 다이내믹 프로그래밍(Dynamic Programming)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

다이내믹 프로그래밍이란 계산 결과를 저장(Memoization)해 두었다가 재활용하는 기법입니다. 본질적으로는 모든 경우의 수를 다 계산해보는 전역 탐색(exhaustive search) 기법입니다만, 이미 저장해 둔 계산 결과를 다시 써먹는 방식으로 반복되는 계산을 줄입니다.

다이내믹 프로그래밍은 원 문제를 작은 부분문제로 쪼개어 푼 뒤 그 결과를 합치는 분할정복(divide and conquer)과는 차이가 있습니다. 분할정복 문제는 부분문제가 서로 독립적일 때 적용하는 기법입니다. 분할정복은 부분문제의 해를 재사용하지 않고 그저 합치기만 합니다. 하지만 다이내믹 프로그래밍은 부분문제가 서로 겹칠 때 씁니다. 덕분에 부분문제의 해(solution)를 재사용할 수 있습니다.

다이내믹 프로그래밍은 optimal value와 optimal solution을 찾는 데 관심이 있습니다. 따로 설명드리겠지만, 행렬 스칼라 곱 연산을 다이내믹 프로그래밍으로 풀 경우 스칼라 곱 최소 횟수가 optimal value, 이 횟수에 대응하는 행렬 곱 순서가 optimal solution이 됩니다. 행렬 스칼라 곱 연산과 관련해서는 이따가 자세히 살펴보겠습니다.

이 글에서는 다이내믹 프로그래밍을 적용할 수 있는 몇 가지 예시를 살펴보도록 하겠습니다. 다만 다이내믹 프로그래밍 기법의 일종인 Assembly-Line Scheduling과 비터비 알고리즘(viterbi algorithm)은 은닉마코프모델, 최대엔트로피마코프모델, Conditional Random Fields 등 시퀀스 예측 모델에 많이 쓰이기 때문에 이 글에서 별도로 다루었습니다.

Rod Cutting

Rod cutting 문제는 우리가 가지고 있는 통나무를 어떻게 쪼개서 팔아야 최대 수익을 낼 수 있는지를 따지는 겁니다. 예컨대 통나무 길이에 따라 다음과 같이 시장 가격이 매겨졌다고 칩시다. (길이의 단위는 미터, 가격은 만원)

고려해야 할 경우의 수는 꽤 많습니다. 가령 길이가 4미터인 통나무를 자르는 가짓수는 아래와 같이 8가지나 됩니다. 여기서 최대 이익을 내는 optimal solution은 길이가 2미터인 통나무 두개로 쪼개 파는 경우입니다. 이 때 optimal value는 10만원이 됩니다. ($n$미터 통나무라면 고려해야할 경우의 수는 $2^{n-1}$가지)

그런데 문제를 자세히 살펴보면 부분문제가 겹친다는 걸 알 수 있습니다. 가령 1미터짜리 통나무의 optimal value는 1입니다(문제 정의상 더 잘게 자를 수 없으므로). 2미터의 optimal value는 다음과 같이 구합니다.

• 1미터짜리 통나무+1미터짜리 통나무를 자르는 모든 경우의 수 가운데 최적 solution : 가격표에서 가져온 1 + 직전 계산결과(1미터짜리의 optimal value) 1 = 2
• 자르지 않고 2미터짜리 통나무 통째로 파는 경우 : 가격표에서 가져온 5
• 가장 큰 값 선택 : $max(2, 5)=5$

3미터의 optimal value는 다음과 같이 구합니다.

• 1미터짜리 통나무+2미터짜리 통나무를 자르는 모든 경우의 수 가운데 최적 solution : 가격표에서 가져온 1 + 직전 계산결과(2미터짜리의 optimal value) 5 = 6
• 2미터짜리 통나무+1미터짜리 통나무를 자르는 모든 경우의 수 가운데 최적 solution : 가격표에서 가져온 5 + 직전 계산결과(1미터짜리의 optimal value) 1 = 6
• 자르지 않고 3미터짜리 통나무 통째로 파는 경우 : 가격표에서 가져온 8
• 가장 큰 값 선택 : $max(6,6,8)=8$

우리의 관심인 4미터의 optimal value는 다음과 같이 구합니다.

• 1미터짜리 통나무+3미터짜리 통나무를 자르는 모든 경우의 수 가운데 최적 solution : 가격표에서 가져온 1 + 직전 계산결과(3미터짜리의 optimal value) 8 = 9
• 2미터짜리 통나무+2미터짜리 통나무를 자르는 모든 경우의 수 가운데 최적 solution : 가격표에서 가져온 5 + 직전 계산결과(2미터짜리의 optimal value) 5 = 10
• 3미터짜리 통나무+1미터짜리 통나무를 자르는 모든 경우의 수 가운데 최적 solution : 가격표에서 가져온 8 + 직전 계산결과(1미터짜리의 optimal value) 1 = 9
• 자르지 않고 4미터짜리 통나무 통째로 파는 경우 : 가격표에서 가져온 9
• 가장 큰 값 선택 : $max(9,10,9,9)=10$

이를 파이썬으로 구현한 코드는 다음과 같습니다(출처). 약간 손질하였습니다.

INT_MIN = -32767
def cutRod(price, n):
  	# val : optimal value
    # 0으로 초기화 
    val = [0 for x in range(n+1)]
    for i in range(1, n+1):
        max_val = INT_MIN
        for j in range(i):
          	 if max_val < price[j] + val[i-j-1]:
             	max_val = price[j] + val[i-j-1]
        val[i] = max_val
    return val[n]
 
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))

Longest Common Subsequence

최장공통부분수열(Longest Common Subsequence) 문제 또한 다이내믹 프로그래밍으로 풀 수 있습니다. 이를 풀려면 먼저 공통수열의 길이를 구해야 합니다. 3가지 경우가 있을 수 있습니다.

• case1 수열 $A$와 $B$의 마지막 원소가 공통부분 수열인 경우 : abcd와 ad의 LCS 길이는 2이다. 이는 abc와 a의 LCS 길이에 1을 더한 것과 같다.
• case2 수열 $A$의 마지막 원소가 공통부분 수열이 아닌 경우 : abcd와 ac의 길이는 2이다. 이는 abc와 ac의 LCS 길이와 같다.
• case3 수열 $B$의 마지막 원소가 공통부분 수열이 아닌 경우 : abcd와 ade의 길이는 2이다. 이는 abcd와 ad의 LCS 길이와 같다.

수열 $A$와 $B$의 마지막 원소가 서로 같다면 case1에 해당하고, 다르다면 case2이거나 case3에 해당합니다. 그런데 우리는 제일 긴 수열에 관심이 있으므로 case2, case3 가운데 최대값을 취합니다. 입력 문자열 길이에 해당하는 행렬(0으로 초기화)을 만들어 놓고 행렬을 위와 같은 규칙을 바탕으로 업데이트합니다. 이를 파이썬으로 구현한 코드는 다음과 같습니다.

def lcs(a, b):
    lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
    # row 0 and column 0 are initialized to 0 already
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i+1][j+1] = lengths[i][j] + 1
            else:
                lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])

optimal value를 찾았으니 이제는 optimal solution을 찾을 차례입니다. 위 코드를 바탕으로 ABCBDAB, BDCABA 두 수열의 LCS 길이를 아래 그림처럼 구했다고 칩시다.

위 행렬 계산은 우측 하단 모서리인 (7, 6)에서 시작합니다. 대상 칸의 값과 바로 위 칸의 값(4)이 같으면 한 칸 위로 옮깁니다. 다르다면 대상 칸의 값과 바로 왼쪽 칸의 값을 비교해 같으면 한 칸 왼쪽으로 옮깁니다. 바로 위 칸과 왼쪽 칸 모두 대상 칸의 값과 다르다면 해당 위치의 원소가 공통수열의 원소에 해당하므로 결과 result 변수에 저장하고, 대각선으로 한 칸 옮깁니다. 이를 구현한 파이썬 코드는 다음과 같습니다.

    # read the substring out from the matrix
    result = ""
    x, y = len(a), len(b)
    while x != 0 and y != 0:
        if lengths[x][y] == lengths[x-1][y]:
            x -= 1
        elif lengths[x][y] == lengths[x][y-1]:
            y -= 1
        else:
            result = a[x-1] + result
            x -= 1
            y -= 1
    return result

Matrix chain multiplication

행렬끼리의 곱셈은 곱셈 순서에 따라 스칼라 곱 횟수에 큰 차이가 날 수 있습니다. 예컨대 행렬 $A$의 차원수가 2×3, $B$는 3×4, $C$는 4×5이고 셋을 곱한다고 가정해 봅시다. $(AB)C$의 경우 2×3×4+2×4×5, 총 64회의 스칼라곱 연산을 수행해야 합니다. 그런데 $A(BC)$의 경우 3×4×5+2×3×5, 총 90회의 스칼라곱 연산을 수행해야 합니다. 행렬 곱을 수행하기 전에 스칼라 곱 횟수를 미리 가늠해서 전체적인 계산량을 줄이려는 것이 이 문제의 관심이 되겠습니다.

그런데 행렬 곱셈은 다음과 같이 부분문제가 서로 겹치기 때문에 다이내믹 프로그래밍을 적용할 수 있습니다.

• $ABC$ : $(AB)C$, $A(BC)$
• $ABCD$ : $(AB)(CD)$, $A(BC)D$, …
• …

이를 파이썬으로 구현한 코드는 다음과 같습니다(출처). 약간 손질하였습니다.

def MatrixChainOrder(p):
    n = len(p)
    m = [[0 for x in range(n)] for x in range(n)]
    for L in range(2, n):
        for i in range(1, n - L + 1):
            j = i + L - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                # q = cost/scalar multiplications
                q = m[i][k] + m[k + 1][j] + \
                	p[i - 1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
    return m[1][n - 1]

위 코드에서 $p$는 행렬 크기를 나타냅니다. 예컨대 [1,2,3,4]라면 행렬 $A$의 차원수가 1×2, $B$는 2×3, $C$는 3×4이고 셋을 곱한다는 뜻입니다.