[Python] 다이나믹 프로그래밍 (DP)

 

 

다이나믹 프로그래밍의 핵심은 점화식과 memoization 이다.

DP는 주로 bottom-up 방식을 사용하지만, top-down으로도 구현 가능하다.

top-down은 재귀+memoization을 통해 구현한다.

 

 

대표적인 DP문제로, 피보나치 수열이 있다.

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

📍 피보나치 수의 점화식은 f(n) = f(n-1) + f(n-2) (n>=2)

 

📌 Bottom-Up

점화식을 반복문으로 구현하여 제일 작은 값부터 구하고자 하는 값까지 반복한다.

위 피보나치 문제를 예로들어, f(10)까지 구하기 위해서는 f(2)부터 반복을 시작한다.

코드로 작성하면,

n = 10
f = [0] * (n+1)
f[0] = 0
f[1] = 1

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

print(f[n])

 

점화식의 범위에 주의하여 반복문을 작성하면 된다.

 

 

📌 Top-Down

재귀와 메모제이션을 이용한다. (단순히 재귀만 이용하면 시간초과 날 가능성 ⬆️)

재귀함수는 구하고자하는 f(10)을 넣어, 답이 나올때가지 재귀함수를 호출한다.

 

코드로 작성하면,

n = 10
memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1

def f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if memo[n] == 0:
        memo[n] = f(n-1) + f(n-2)
    return memo[n]

print(f(n))

 

 

 

하지만, 재귀함수는 스택에 값이 계속 쌓여 오버플로우 날 수 있기 때문에 왠만하면 DP는 bttom-up 하는 걸로..!

💡 중요한 것은 규칙을 찾아 점화식을 만들어 내는 것

 

 

📌 백준 11726번

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

점화식은 다음과 같다.

f(3)부터 규칙이 발견되는데, f(2)에 파란색 타일 하나를 붙이는 방법 + f(1)에 핑크색 타일 한 쌍을 붙이는 방법이 있다.

즉, f(n) = f(n-1)에 파란색 타일을 하나 붙이기 + f(n-2)에 핑크색 타일 한 쌍을 붙이기 (n>=2)

 

 

코드로 작성하면,

f(0) = 1을 해준 이유는, f(2) = f(1) + f(0) = 2가 나오게 하기 위함이다.

import sys

n = int(sys.stdin.readline())

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

print(dp[n])