[python] Dynamic Programming

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

큰 문제를 작은 문제로 나눠서 푸는 알고리즘, 1. Overlapping Subproblem 2. Optimal Substructure 의 두가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야하며, 작은 문제의 정답을 한 번 구했으면 정답을 어딘가에 메모해둠(Memoization)으로써 중복된 풀이를 피한다. 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.

다이나믹 프로그래밍의 예시로 아래 타일채우기 문제(link)를 풀어보자.

여기서는 Memoization을 위해 dp라는 배열을 선언한 후, 점화식을 만들어서 문제를 해결하였다. 점화식이 약간 까다로웠지만 큰 문제를 작은 문제로 나누어 생각해보니 답이 나왔다.

import sys

n = int(sys.stdin.readline())
dp = [0 for _ in range(31)]
dp[0], dp[1], dp[2] = 1, 0, 3

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