[Algorithm] 다이나믹 프로그래밍

* Python을 기준으로 합니다

---

다이나믹 프로그래밍 (Dynamic Programming)

- 개념

• 다이나믹 프로그래밍 (동적 계획법) : 전체 문제를 각각의 부분 문제로 나눈 다음 하나의 결과로 합쳐서 해결하는 방법
  • 즉, 전체 문제를 부분 문제로 나누어 해결할 수 있어야 하고 동시에 중복되는 부분 문제가 존재하는 경우 사용
  • 다이나믹 프로그래밍의 구현
    1. 메모이제이션 (Memoization) : 하향식 (Top-down) 방식
       - 주어진 문제를 작은 부분 문제로 나누어 가면서 전체 문제를 해결하는 방식
       - 재귀를 기반으로 이전 값들이 모두 계산되어 있다는 가정 하에 나머지 계산을 수행함
       
    2. 타뷸레이션 (Tabulation) : 상향식 (Bottom-up) 방식
       - 작은 부분 문제부터 해결한 다음, 해당 과정을 반복해 정답을 확인하면서 전체 문제를 해결하는 방식
       - 주로 반복문 형태로 구현되고 정확한 반복 횟수에 대한 기준이 필요함
       
    3. 일반적으로는 타뷸레이션 보다는 메모이제이션을 활용하는 것이 좋음
  • 다이나믹 프로그래밍 (메모이제이션)의 동작
    1. 이전해들을 저장할 공간(배열)을 생성
    2. 재귀/반복문으로 문제를 해결할 함수를 정의
       - 재귀의 경우 종료 조건을 정의
    3. 계산된 결과값을 배열에 저장

메모이제이션의 동작

- 구현

1. 피보나치 수열

• 메모이제이션을 활용한 피보나치 수열
  • 피보나치 수열은 대표적인 다이나믹 프로그래밍의 예시 (예시 문제 : 프로그래머스 - 피보나치 수)
    - 위 그림과 같이 중복되는 최적 부분 구조 (Fibo(2), Fibo(1) 등)가 존재하기 때문
  • 이때 문제 해결을 위해 분할 정복을 활용할 수도 있지만, 다이나믹 프로그래밍을 적용하면 $O(n)$의 time complexity로 해결 가능함

피보나치 수 문제

import sys
sys.setrecursionlimit(200000) #재귀 상한

def fibo(n, dp):
    if n < 2: #종료조건
        return 1

    if dp[n] == 0: #현재 값이 계산되어 있지 않으면 
        dp[n] = (fibo(n-1, dp) + fibo(n-2, dp))%1234567 #피보나치 계산 후 배열에 저장 
    
    #배열에서 값 가져오기
    return dp[n]

def solution(n):
    dp = [0]*n #이전 값들 저장할 배열
    dp[0] = 1
    dp[1] = 1
    
    answer = fibo(n-1, dp)
    return answer

• 타뷸레이션을 활용해도 $O(n)$ 내에 해결 가능함

def solution(n):
    dp = [0,1]
    for i in range(2, n+1): #반복문 활용
        dp.append( (dp[i-1] + dp[i-2]) % 1234567 )
    return dp[n]

2. 0-1 배낭 문제

• 0-1 배낭 문제 : 무게 $w$와 가치 $v$를 가지는 $n$개의 물건들을 용량이 $W$인 배낭에 넣을 때, 배낭의 가치 $A(n, W)$가 최대가 되도록 하는 방법을 탐색하는 것
  • 그리디로 해결할 수 있는 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 물건 일부분만 나누어 넣을 수 없으므로 그리디를 사용할 수 없고, 완전 탐색으로 구현하는 경우 $O(2^{n})$의 time complexity를 가지므로 비효율적임
  • 이때 0-1 배낭 문제가 실수 형태로 정의되는 경우, 다음의 점화식에 따라 분할 정복을 사용할 수 있음:
    (Eq. 1) $A(n,w) = \left\{\begin{matrix}
    0, & W=0 \,\,\mathrm{or}\,\, n=0 \\
    A(n-1, W) & w_{n}>W \\
    \max(v_{n} + A(n-1, W-w_{n}), A(n-1, W)) & \mathrm{otherwise} \\
    \end{matrix}\right.$

def knapsack(W, w, v, n):
  if n==0 or W==0:
    return 0
  
  if w[n-1] > W:
    return knapsack(W, w, v, n-1)
  else:
    tmp1 = knapsack(W, w, v, n-1)
    tmp2 = v[n-1] + knapsack(W - w[n-1], w, v, n-1)
    return max(tmp1, tmp2)

w = [10.123, 7.902, 6.468]
v = [19.905, 10.716, 10.824]
weight = 15.546

print(knapsack(weight, w, v, 3)) #21.54

• 모두 정수로 정의되는 경우 다이나믹 프로그래밍을 적용할 수 있음 (예시 문제 : BOJ 12865 - 평범한 배낭)

평범한 배낭 문제

import sys
input = sys.stdin.readline

def knapsack(K,N,item):
    dp = [[0]*(K+1) for _ in range(N+1)] #dp

    for i in range(1, N+1): #물건 개수 만큼 반복
        for j in range(1, K+1): #배낭 용량 만큼 반복            
            if item[i][0] > j: #물건의 무게가 배낭 용량 보다 크면
                dp[i][j] = dp[i-1][j]
            else: #물건의 무게가 배낭 용량 보다 작으면
                tmp1 = dp[i-1][j-item[i][0]] + item[i][1]
                tmp2 = dp[i-1][j]
                dp[i][j] = max(tmp1, tmp2) #최대값으로 넣음

    return dp

#-----
N, K = map(int, input().split())
item = [[0, 0]]
for _ in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split())
    item.append([w, v])

print(knapsack(K, N, item)[N][K])

3. 예시 문제

• 프로그래머스 - 2 x n 타일링 
  • 가장 작은 부분 문제에 대한 해는 다음과 같음
    1. 타일을 가로로 배치하는 경우 : 2가지 패턴을 가짐
    2. 타일을 세로로 배치하는 경우 : 1가지 패턴을 가짐
  • 이때 해당 문제는 아래 그림과 같이 서로 중복되는 최적 부분 구조를 가짐

• 따라서 $n\geq 3$에 대해 타일을 채우는 경우에 대한 점화식은:
  (Eq. 2) $S_{n} = S_{n-1}+S_{n-2}, \,\,\, n\geq 3$

$2\times n$ 타일링 문제

def solution(n):    
    dp = [0] * (n+1) #dp
    dp[1] = 1
    dp[2] = 2

    #가로 길이 3부터 n까지 
    for i in range(3, n+1):
      dp[i] = (dp[i-1]+dp[i-2])%1000000007
    return dp[n]