Dynamic Programming (동적 계획법)

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

Dynamic Programming (동적 계획법)¶

Objective¶

1. Dynamic Programming 특징, 정의, 방식, 유의사항
2. Dynamic Programming 구현 방법
3. Dynamic Programming 예시 문제

1. Dynamic Programming 특징, 정의, 방식, 유의사항¶

1-1. Dynamic Programming 문제 특징¶

• 최적 부분 구조 (Optimal Substructure)
  • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있습니다.
• 중복되는 부분 문제 (Overlapping Subproblem)
  • 동일한 작은 문제를 반복적으로 해결해야 합니다.

1-2. Dynamic Programming 정의¶

• Dynamic Programming 이란 위와 같은 특징을 가지는 문제를 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법입니다.
• 이때 메모리를 적절하게 사용한다는 의미는 이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장 하여 다시 계산하지 않는다는 의미입니다.
• 자료구조에서의 동적 할당(Dynamic Allocation)과는 다른 의미입니다. 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미합니다.

1-3. Dynamic Programming 방식¶

• Top Down (하향식)
  • 재귀 함수 사용
  • memoization (caching) 기법을 사용
  • memoization 은 Dynamic Programming 국한된 표현이 아닙니다. memoization이란 이전에 계산된 결과를 일시적으로 기록(캐싱)해 놓는 넓은 개념을 의미합니다.
• Bottom up (상향식)
  • 반복문 사용
  • dp table 사용

1-4. Dynamic Programming 유의 사항¶

• 분할 정복(Divide and Conquer)과의 차이점은 다이나믹 프로그래밍의 경우 중복되는 부분 문제가 존재한다는 것입니다. 예) 퀵 정렬에서 한번 처리한 pivot은 다시 처리하지 않습니다.
• Bottom up (상향식)으로 구현하는 것을 권장 합니다. 첫째로, 1) 함수를 호출했을 때 메모리 상에 적재되는 과정이 발생하므로 오버헤드가 발생합니다. 둘째로, 2) 시스템상 재귀 함수의 스택 크기가 한정되어 있는 경우 오류가 발생합니다. Python에서는 recursion depth 오류가 발생합니다. 다만 setrecursionlimit() 함수를 호출하여 제한을 완화할 수는 있습니다.

2. Dynamic Programming 구현 방법¶

2-1. fibonacci¶

• $a_n = a_{n-1} + a_{n-2}$, $a_1 = 1$, $a_2 = 1$
• 시간복잡도는 일반적으로 $O(2^n)$ 입니다.
  • 트리의 깊이로 생각하면 편합니다. 부모노드 f(6) -> f(5) -> f(4) -> f(3) -> 말단노드 f(2), f(1) 로 순차적으로 계산해야 되야 합니다.
  • 즉 완전 이진 트리라고 일반적으로 가정을 하고 각 level에서의 연산량을 합하면 $2^0 + 2^1 + ... + 2^5 = 31 = 2^{n -1} \approx 2^n$ 입니다.
• DP를 사용하지 않고 재귀함수로 구현시 $ f(100) \approx O(2^{100}) \approx 1000^{10}$ 이 걸립니다.

In [1]:

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

In [2]:

%time print(fibo(30))

832040
CPU times: user 195 ms, sys: 4.41 ms, total: 199 ms
Wall time: 212 ms

2-2. fibonacci with memoization¶

• $a_n = a_{n-1} + a_{n-2}$, $a_1 = 1$, $a_2 = 1$
• Top-Down (하향식)
• 시간복잡도는 일반적으로 O($N$) 입니다.
  • 트리의 깊이로 생각하면 편합니다. 부모노드 f(6) -> f(5) -> f(4) -> f(3) -> 말단노드 f(2), f(1) 로 순차적으로 계산해야 되야 합니다.
  • memoization 을 활용하면 완전 이진 트리라고 일반적으로 가정하지만 각 level 에서 연산을 1번만 수행하면 됩니다.
  • 즉 f(6) -> f(5) -> f(4) -> f(3) -> f(1), f(2) 가 호출 됩니다.
  • 즉 memoization을 활용하여 DP로 구현시 $O(N)$ 이 걸립니다.
• 빠르게 계산하지만, 함수 호출시 메모리 상에 적재되는 과정이 있으므로 오베해드가 발생합니다.

In [3]:

d = [0] * 100

def fibo_memo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    
    return d[x]

In [4]:

%time print(fibo_memo(30))

832040
CPU times: user 199 ms, sys: 4.7 ms, total: 203 ms
Wall time: 216 ms

2-3. fibonacci with dp table¶

• $a_n = a_{n-1} + a_{n-2}$, $a_1 = 1$, $a_2 = 1$
• Bottom-Up (상향식)
• dp table 을 활용합니다.
• 시간복잡도는 O($N$) 입니다.
  • f(1) -> f(2) -> f(3) -> f(4) -> f(5) -> f(6) 순으로 계산이 이루어집니다.

In [5]:

def fibo_dp(n):
    d = [0] * (n+1)
    d[1] = 1
    d[2] = 1

    for i in range(3, n+1):
        d[i] = d[i-1] + d[i-2]
    
    return d[n]

In [6]:

%time print(fibo_dp(30))

832040
CPU times: user 500 µs, sys: 392 µs, total: 892 µs
Wall time: 2.33 ms

3. Dynamic Programming 예시 문제¶

3-1. 1로 만들기¶

• https://github.com/ndb796/python-for-coding-test 참고
• $ a_i = min(a_{n-1}, a_{n/2}, a_{n/3}, a_{n/5}) + 1 $

In [7]:

x = int(input())

d = [0] * 300001

for i in range(2, x + 1):
    # 1 을 빼는 경우
    d[i] = d[i-1] + 1
    
    # 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
        
    # 3로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
        
    # 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5] + 1)

print(d[x])

26
3

3-2. 개미 전사¶

• https://github.com/ndb796/python-for-coding-test 참고
• $ a_i = max(a_{i-1}, a_{i-2} + k_i) $

In [8]:

import sys

n = int(input())
arr = list(map(int, input().split(' ')))

def ant_soldier(arr, n):
    if len(arr) == 2:
        return max(arr)
    
    for i in range(2, n):
        arr[i] = max(arr[i-1], arr[i-2] + arr[i])
        
    return arr[n-1]

print(ant_soldier(arr, n))

4
1 3 1 5
8

3-3. 바닥 공사¶

• https://github.com/nd₩b796/python-for-coding-test 참고
• $ a_i = a_{i-1} + 2 * a_{i-2} , a_1 = 1, a_2 = 3$

In [9]:

n = int(input())

def floor_work(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 3

    for i in range(3, n + 1):
        dp[i] = dp[i-1] + 2 * dp[i-2]

    return dp[n] % 796796

print(floor_work(n))

3
5

3-4. 효율적인 화폐 구성¶

• https://github.com/nd₩b796/python-for-coding-test 참고
• 금액 : $ i $, 화폐단위 : $ k $
• 금액 i 를 만들 수 있는 최소 화페 개수 : $ a_i $
• 금액 i-k 를 만들 수 있는 최소 화폐 개수 : $ a_{i-k} $

• $ a_{i-k} $ 가 존재 하는 경우, $ a_i = min(a_i, a_{i-k} + 1) $
• $ a_{i-k} $ 가 존재 하지 않는 경우, $ a_i = 100001 $
• 문제에서 최대 가치의 합이 10000 이므로 초기값을 10001 로 주어 불가능한 수로 설정

In [10]:

n, m = map(int, input().split(' '))

money = [int(input()) for _ in range(n)]

def get_money(money, m):
    dp = [10001] * (m + 1)
    dp[0] = 0
    
    for unit in money:
        for index in range(unit, m + 1):
            dp[index] = min(dp[index], dp[index - unit] + 1)

    if dp[m] != 10001:
        return dp[m]
    else:
        return -1


print(get_money(money, m))

3 4
3
5
7
-1