파이썬 DP 개념정리와 예제문제

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 7: PART 2. 알고리즘 유형 분석 - 동적계획법 Dynamic Programming 43강 ~ 50강 내용 요약입니다.

 

Chapter 6.
동적 계획법

문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복함
분할 정복과 비슷한 느낌임

# DP 구현 2가지
Top-down : 구현-재귀 저장방식-메모이제이션(Memoization)
Bottom-up : 구현-반복문 저장방식-타뷸레이션(Tabulation)

# Memoization - 한 번 구한 답들은 저장해두자
부분 문제들의 답을 한 번 구했으면 또 구하지 않도록(중복연산 방지)
Cache에 저장해두고 다음부턴 갖다 쓰자
필요한 부분 문제들만 구한다 Lazy-Evaluation
Top-down 방식에서 사용함

# 4살 아이한테 메모이제이션을 설명하기
아빠 : 1+1+1+1+1..= 정답이 뭘까?
아이 : n이요
아빠 : (+1을 붙여쓰고) 이번에는?
아이:  n+1이요.
아빠: 어떻게 그렇게 빨리 알았니?
아이: 하나 더했으니까요
아빠: n이라는 것을 기억하고 있으니 다시 계산할 필요가 없었구나

# 미리 다 구해두자 Tabulation
부분 문제들의 답을 미리 다 구해두면 편하다
테이블을 채워나간다는 의미라서 타불레이션
필요 없는 부분 문제들까지 전부 구한다 Eager-Evaluation
Bottom-up 방식에서 사용

# 피보나치 수열
f(0) = 0
f(1) = 1
f(i+2) = f(i+1) + f(i)

 

# boj.kr/2748
# 피보나치 수 2
# 메모이제이션 - 순서가 덜중요

cache = [-1] * 91
cache[0] = 0
cache[1] = 1
cnt = 0

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

print(f(int(input())))

 

#테뷸레이션 - 순서가 중요
N = int(input())
cache = [-1] * 91
cache[0] = 0
cache[1] = 1

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

print(cache[N])

 

# 이항계수 nCr
bino(n,0) = 1
bino(n,n) = 1
bino(n,r) = bino(n-1, r-1) + bino(n-1, r)
삼각수로 확인가능, 맨위, 좌우를 1로 채우고 좌우 위에서 더한 값을 저장하는 것을 반복

 

# boj.kr/11051
# 이항계수 2
# 메모이제이션

import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10007
cache = [[0] * 1001 for _ in range(1001)]
N, K = map(int, input().split())

def bino(n, k):
    if cache[n][k]:
        return cache[n][k]

    if k == 0 or k == n:
        cache[n][k] = 1
    else:
        cache[n][k] = bino(n-1, k-1) + bino(n-1, k)
        cache[n][k] %= MOD

    return cache[n][k]

print(bino(N, K))

 

#타뷸레이션

MOD = 10007

cache = [[0] * 1001 for _ in range(1001)]
N, K = map(int, input().split())

for i in range(1001):
    cache[i][0] = cache[i][i] = 1
    for j in range(1, i):
        cache[i][j] = cache[i-1][j-1] + cache[i-1][j]
        cache[i][j] %= MOD

print(cache[N][K])

 

# DP 구현 2가지
Top-down
재귀, 메모이제이션, 직관적이라 코드 가독성이 좋다, 재귀함수 호출을 많이 해서 느릴 수 있다.
Bottom-up
반복문, 타뷸레이션, 시간과 메모리를 좀 더 아낄 수도 있다. DP테이블을 채워나가는 순서를 알아야 한다.

 

# boj.kr/11726
# 2*n 타일링

MOD = 10_007

dp = [0]*1001
dp[1] = 1
dp[2] = 2
n = int(input())
for i in range(3, 1001):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[n])

 

# boj.kr/10844
# 쉬운 계단 수

MOD = 1_000_000_000
#cache[n][d]: 길이가 n, 마지막 숫자가 d인 계단수 개수
cache = [[0] * 10 for _ in range(101)]
for j in range(1, 10):
    cache[1][j] = 1

for i in range(2, 101):
    for j in range(10):
        if j > 0:
            cache[i][j] += cache[i-1][j-1]
            cache[i][j] %= MOD
        if j < 9:
            cache[i][j] += cache[i-1][j+1]
            cache[i][j] %= MOD

ans = 0
N = int(input())
for j in range(10):
    ans += cache[N][j]
    ans %= MOD

print(ans)

 

# 정리
동적계획법은 문제를 쪼개서 작은 문제부터 구해가며 원래 문제의 답을 구하는 방식
메모이제이션, 타뷸레이션 방식을 사용한다.
점화식을 찾고 테이블만 잘 정의하면 풀리는 문제들이 많다. 점화식 찾기가 쉽지 않다.