동적 계획법

병합 정렬도, 계단 오르기도 큰 문제를 작은 문제로 나누어 푼다. 그런데 병합 정렬에는 메모를 붙이지 않고, 계단 오르기에는 붙인다. 둘을 가르는 기준은 무엇일까?

1공통점, 부분 문제의 답으로 전체를 만든다

두 방법 모두 문제를 같은 모양의 작은 부분 문제로 나누고, 부분 문제의 답을 조합해 전체의 답을 만든다. 그래서 둘 다 재귀식(점화식)으로 쓸 수 있다. 차이는 부분 문제들이 서로 겹치는가에 있다. 병합 정렬은 배열의 왼쪽 절반과 오른쪽 절반을 따로 정렬하므로, 같은 부분 배열을 두 번 정렬하는 일이 없다. 계단 오르기에서는 ways(5)를 구하려고 부른 ways(4)와 ways(3)이 둘 다 다시 ways(2)를 부른다.

단순 재귀로 짠 계단 오르기는 분할 정복처럼 생겼지만 부분 문제가 겹치기 때문에 지수 시간이 걸린다. 반대로 이진 탐색이나 병합 정렬에 메모를 붙여도 같은 부분 문제를 다시 만나지 않으므로 메모리만 더 쓴다.

2예, 두 DNA 서열이 얼마나 닮았을까

생명과학에서는 두 DNA 서열이 얼마나 닮았는지 비교한다. 가장 간단한 척도가 최장 공통 부분 수열(LCS)이다. 순서는 지키되 중간을 건너뛰어도 되는 공통 문자열 가운데 가장 긴 것이다. GATTACA와 TACGCA의 LCS는 길이 4인 TACA이다.

X의 앞 i글자와 Y의 앞 j글자의 LCS 길이를 L[i][j]라 하면, 두 마지막 글자가 같을 때 L[i][j] = L[i−1][j−1] + 1, 다를 때 L[i][j] = max(L[i−1][j], L[i][j−1])이다. 한 글자를 빼고 비교하는 부분 문제들이 서로 겹치므로 표에 저장한다.

def lcs(X, Y):
          n, m = len(X), len(Y)
          L = [[0] * (m + 1) for _ in range(n + 1)]
          for i in range(1, n + 1):
              for j in range(1, m + 1):
                  if X[i - 1] == Y[j - 1]:
                      L[i][j] = L[i - 1][j - 1] + 1
                  else:
                      L[i][j] = max(L[i - 1][j], L[i][j - 1])
          return L[n][m]

      print(lcs("GATTACA", "TACGCA"))   # 4

행은 GATTACA, 열은 TACGCA의 글자이다. 주황 칸은 두 글자가 같아 대각선 위 칸에서 1을 더한 곳으로, 오른쪽 아래에서 거꾸로 따라가면 T, A, C, A를 얻는다. 표의 칸은 (n+1)(m+1)개이므로 시간은 O(nm)이다. 모든 부분 수열을 비교하는 완전 탐색이라면 길이 n인 서열의 부분 수열만 2ⁿ개이다.

3동적 계획법으로 설계하는 순서

부분 문제 정하기

“앞의 i개만 볼 때”, “허용 무게가 w일 때”처럼 표의 한 칸이 무엇을 뜻하는지 문장으로 쓴다.

점화식 세우기

마지막 선택(마지막 물건을 넣는가, 마지막 글자가 같은가)으로 경우를 나누어 더 작은 칸으로 표현한다.

기저 조건

빈 서열, 물건 0개처럼 바로 답을 아는 칸을 채운다.

계산 순서

어떤 칸을 계산할 때 필요한 칸이 이미 채워져 있도록 순서를 정한다.

답과 역추적

답이 들어 있는 칸을 찾고, 필요하면 표를 거꾸로 따라가 실제 선택을 복원한다.

판단‘동적 계획법(dynamic programming)’의 programming은 코드를 짜는 일이 아니라 표를 만들어 계획한다는 뜻으로, 1950년대에 리처드 벨먼이 붙인 이름이다. 이름에 ‘동적’이 들어 있다고 실행 중에 무언가가 움직이는 방법은 아니다. 또 동적 계획법은 최적 부분 구조가 있을 때만 맞는 답을 준다. 예를 들어 같은 정점을 두 번 지나지 않는 가장 긴 경로 문제는 부분 경로의 최적해를 이어 붙여도 전체 최적해가 되지 않아 이 방법을 그대로 쓸 수 없다.