[코테] 알고리즘 공부 Cheat sheet - III (DP)

Dynamic Programming

 

다이나믹 프로그래밍 (이하 DP) 은 시간이 지남에 따라 일련의 결정 단계로 나누어 의사결정을 단순화하는 방법이다.

(정의가 확 안 와닿는다. 하지만 익히 알고는 있었지 않은가?)

but, 아래 두 가지는 DP 문제를 풀기 위한 필수 캐싱 도구로 알아야 한다.

 

- 메모이제이션 : 탑다운 (top down) 방식에서 사용

• 재귀 사용
• 필요한 부분 문제들에 대해 구해 놓은 값들을 저장하고 다시 사용. (lazy)

 

- 타뷸레이션 (tabulation): 바텀업 (bottm up) 방식에서 사용

• 반복문 사용
• 부분 문제들에 대한 답을 미리 다 구한다. (eager)

바텀업의 경우 부분 문제의 답을 미리 알아야 하는 문제가 있을 수 있어서 탑다운 방식으로 구현하는게 좀 더 쉬울 수 있다.

 

 

피보나치 수열로 이해해보기

DP 문제를 설명할 때 단골로 나오는 문제이다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...와 같이 각 숫자가 그 이전 두 숫자의 합으로 계산되며

 

0 번째 항부터 시작할 경우 다음과 같이 정의한다.

$F_{0} = 0 $

$F_{1} = 1 $

$F_{n} = F_{n-1} + F_{n-2} $

 

# 재귀 방법 = memoization = top down
cache = [-1] * 101
cache[0] = 0
cache[1] = 1

def fibo(n):
    if cache[n] == -1:
        cache[n] = fibo(n-1) + fibo(n-2)
    return cache[n]
print(fibo(int(input())))

# 반복 방법 = tabulation = bottom up
N = int(input())
cache = [-1] * 101
cache[0] = 0
cache[1] = 1

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