[Python] DP, 동적계획법

DP, 동적계획법

>>  주어진 문제를 작은 문제로 쪼개서 더 큰 문제의 답을 구하는 것을 반복 하는 패러다임 (분할정복과 비슷하다)

 

분할 정복과 DP 의 차이는 아래 그림과 같다. 

분할 정복과 DP의 차이를  그림으로.

 

 

 

Memoization 메모이제이션, 한 번 구한 답들은 저장해두자!

>> 부분 문제들의 답을 전역 변수 리스트 같은 것에 넣고 사용할 때마다 꺼내 써야 한다.

 

 

Top-down ? Bottom-Up?

Top-down	Bottom-Up
재귀	반복문
큰거  ➡ 작은 거	작은 거 ➡ 큰거
직관적/ 코드 가독성 👍	덜 직관적(문제 따라 다름) 시간-메모리 save 여지 O

 

---

백준 문제 풀며 DP 유형 이해 하기

DP 유형은 아래 3가지를 찾겠다는 생각을 하고, 찾은 후 풀어나가야한다.

1. 정의: f(i) = i번째 피보나치 수. 입력 N에 대해 f(N)을 출력한다.
2. 초기값: 𝑖0 = 0, 𝑖1 = 1
3. 점화식: f(i) = f(i-2) + f(i-1)

 

 

# 백준 2748 피보나치 수

f(i) = i번째 피보나치 수. 입력 N에 대해 f(N)을 출력한다.
초기값: 𝑖0 = 0, 𝑖1 = 1
점화식: f(i) = f(i-2) + f(i-1)

import sys

n = int(input())

cache = [0] * (n+1)

cache[0] = 0
cache[1] = 1

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

 

 

# 백준 11051 이항 계수

이항계수 규칙

f(i) =  iCk
초기값: f(0,0) = 1, f(1,0)= 1, f(1,1) = 1 & i==k 이면 1
점화식: f(i,k) = f(i-1, k-1) + f(i-1,k)

N, K = map(int, input().split())
cache=[]

for i in range(N+1):
	cache.append([1]*(i+1))
    
for i in range(2, N+1):
	for j in range(1,i):
    	cache[i][j] = (cache[i-1][j-1] +cache[i-1][j])%10007
        
print(cache[N][K])

 

 

# 백준 11726 2xN 타일링

f(i) =  2*i
초기값: f(1) = 1, f(2) = 2
점화식: f(i) = f (i-1) +f(i-2)

import sys
sys.setrecursionlimit(10**6) 

n = int(input()) # n<=1000

cache =[0]*(n+1)
cache[1] =1
cache[2] =2

def f(n):
    if n<3:
        return cache[n]
    if cache[n] != 0:
        return cache[n]%10007
    else:
        cache[n] = f(n-1)+f(n-2)
        return cache[n]%10007
        

print(f(n))