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

동적계획법이라고 불리는 dp 알고리즘은 dynamic과 아무 상관이 없음.
한국어로는 메모하며 풀기가 더 맞는 번역.

이미 계산한 값을 반복하여 계산하지않고, 저장해놓은 값(메모한 값)에서 가져와 시간복잡도를 줄이는 기법.

주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다. 부분문제에서 겹치는 것들은 memo를 해놓고 거기서 시간복잡도를 줄인다.

ex) fibonacci를 재귀로 구현하면 다음과 같다

def f(n):
    if n <= 1:
        return n
    return f(n-2) + f(n-1)

만약에 f(10)을 호출한다하면, 이미 호출한 f(0) ~ f(8)을 중복적으로 여러번 호출하게 된다.

n = 10일 때는 값이 작아보일 수 있지만, n이 커지면 f(0)등을 중복적으로 호출하는 횟수가 지수적으로 많아지기 때문에 이것을 해결할 방법으로 dp를 사용하자.

10
F(10): 55
호출 횟수
F(0): 34회 호출
F(1): 55회 호출
F(2): 34회 호출
F(3): 21회 호출
F(4): 13회 호출
F(5): 8회 호출
F(6): 5회 호출
F(7): 3회 호출
F(8): 2회 호출
F(9): 1회 호출
F(10): 1회 호출

ex) fibonacci를 dp로 구현 ( top-down, 재귀 )

memo = [-1 for _ in range(N+1)]
memo[0] = 0
memo[1] = 1

def fibo(n):
	# 이미 계산해놓은 값은 다시 계산하지않고, 저장해놓은 값에서 가져와서 return
	if memo[n] != -1:
		return memo[n]
	else: # 아니라면, 계산후 memo하고 return
		memo[n] = fibo(n-1) + fibo(n-2)
		return memo[n]

N = int(input())
print(fibo(N))

ex) fibonacci를 dp로 구현 ( bottom-up, 반복문 )
bottom-up

N = int(input())
memo = [0 for _ in range(N+1)]
memo[1] = 1

for i in range(2,N+1):
	memo[i] = memo[i-1] + memo[i-2]

print(memo[N])

ex) 1463, 1로 만들기

import sys
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
dp = [10**8 for _ in range(10**6+1)]
dp[1] = 0
for i in range(1,N):
    dp[i+1] = min(dp[i+1],dp[i] + 1)
    if i*3 <= N:
        dp[i*3] = min(dp[i*3],dp[i] + 1)
    if i*2 <= N:
        dp[i*2] = min(dp[i*2],dp[i] + 1)

print(dp[N])

top-down

재귀로 풀면 이렇게 풀리지만, 메모리초과가 난다. N이 최대값이면, 재귀 깊이가 아마 최소 10**6까지 들어가서 그런 듯.

import sys
sys.setrecursionlimit(10**7)

N = int(input())
dp = [-1 for _ in range(N+1)]
dp[1] = 0

def solve(n):
    if dp[n] != -1:
        return dp[n]
    else:
        dp[n] = solve(n-1) + 1
        if n % 3 == 0:
            dp[n] = min(dp[n], solve(n//3) + 1)
        if n % 2 == 0:
            dp[n] = min(dp[n], solve(n//2) + 1)
        return dp[n]

print(solve(N))