Algorithms : Dynamic Programming

이번 포스트에는 Dynamic Programming 에 대한 알고리즘과 예제에 대해 다룬다.

Dynamic Programming

DP (Dynamic Programming)

• D&C (분할 정복) 기법과는 달리, sub problem이 중복될 경우에는 DP가 효과적임
• 핵심 전략
  • 재귀적 성질 정의 (recursive property)
  • Bottom-up 방식으로 해결
  • 결과를 배열에 저장하고 이후에 계산에 재사용함.
• Design

Step 1

• Establish a recursive property from the problem
• Identify a recurrence equation from P
• 큰 문제를 작은 문제와 작은문제 작은문제로 나눔

Step 2

• Solve in a bottom-up fashion programming
• Solve smaller problems first (easy problem first)
• Save them(smaller problems) in arrays
• Use them later

예제 1 ) Bionimal Coefficient

이항 계수 문제이다.

• 재귀에 대한 정의로 푸는 알고리즘

if k == 0 or k == n then
    bin(n,k) = 1;
else
    bin(n,k) = bin(n-1,k-1) + bin(n-1,k);

=> 중복 계산이 너무 많아서 시간 복잡도가 지수

• DP 로 푸는 알고리즘

function bin2(n, k: integer): integer;
var B: array[0..n, 0..n] of integer;
for i = 0 to n:
    for j = 0 to min(i,k):
        if j == 0 or j == i:
            B[i,j] = 1;
        else:
            B[i,j] = B[i-1,j-1] + B[i-1,j];
return B[n,k];

=> 훨씬 빠르게 해결 가능함. 실제로는 1차원 배열로도 해결이 가능함.

예제 2) CMM

CMM (Chained Matrix Multiplication) : 연속 행렬 곱셈 최적화

• 행렬의 곱을 가장 적은 곱셈 연산으로 계산

• 가능한 곱셈 순서가 지수적으로 많음. => 단순 탐색 방식은 불가능

• DP 를 통한 해결

  • M[i][j] = 행렬 Aᵢ ~ Aⱼ의 최소 곱셈 연산 수

    M[i][j] = min(M[i][k] + M[k+1][j] + d_{i-1}·d_k·d_j)

• 코드로 구현

Function minmult(n:integer; d: array[0..n]): integer;
var M: array[1..n][1..n] of integer;
for i := 1 to n:
    M[i][i] := 0;
for diagonal := 1 to n - 1:
    for i := 1 to n - diagonal:
        j := i + diagonal;
        M[i][j] := min(M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j])
return M[1][n];

예제 3) Floyd’s Algorithm

개념

• 그래프 : 가중치 있는 방향 그래프 (Weighted Directed Graph)
• 목표 : 모든 정점 쌍 간의 최단 경로 (All-paris Shortest Path, APSP) 구하기
• 단순한 방법 (모든 경로 탐색) -> DP를 이용한 알고리즘 O(n^3)

핵심 재귀식

D(k)[i][j] = {v₁,…,vₖ}만을 거쳐 i→j 최단경로의 길이 \(D^{(k)}[i][j] = \min(D^{(k-1)}[i][j], D^{(k-1)}[i][k] + D^{(k-1)}[k][j])\)

\[D^{(0)}[i][j] = W[i][j]\]

구현

for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])

최적화 문제와 DP

• 최단 경로, 최소 곱셈 비용, TSP
• DP의 적용 조건 : Optimal Substructure (최적 부분 구조)를 성립해야함.
  • 문제의 최적해는 항상 그 부분 문제들의 최적해를 포함

TSP (Traveling Salesperson Problem)

• 입력 : 그래프 G, 거리 행렬 W

• 목표 : 모든 정점을 한 번씩 방문하고 돌아오는 최단 순회 경로

• 점화식

  • D[vi, A] = 시작이 vi이고, 집합 A의 정점을 한 번씩 방문하여 v₁로 돌아오는 최소 거리 \(D[vi, A] = \min_{vj \in A}(W[vi][vj] + D[vj, A \setminus \{vj\}])\)

    \[\min_{j \in V - \{v_1\}}(W[v_1][vj] + D[vj, V - \{v_1, v_j\}])\] \[O(n²·2ⁿ)\]

---

DP 가 적용되지 않는 경우

• 최적 부분 구조가 성립하지 않은 문제
  • ex) Longest Simple Path