동적 계획법 DP Dynamic Programming

문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 걸 반복
분할 정복과 비슷한 느낌
DP는 중복되는 부분 문제를 가지고 있는 경우에 사용
DP는 최적 부분 구조를 가지고 있는 경우에 사용

구현 2가지

탑다운 → 재귀 → 메모이제이션
바텀업 → 반복문 → 타뷸레이션

메모이제이션

한 번 구한 답들은 저장해두자
부분 문제들의 답을 한번 구했으면 또 구하지 않도록(중복 연산 방지) 캐시에 저장하고 다음부턴 가져다 쓴다.
필요한 부분 문제들만 구한다 Lazy-Evaluation
탑다운 방식에서 사용

타뷸레이션

모든 부분 문제를 구해놓고 그걸로 큰 문제를 푼다.
바텀업 방식에서 사용
모든 부분 문제를 구하기 때문에 메모리 사용량이 많다.
모든 부분 문제를 구하기 때문에 시간 복잡도가 O(n)인 경우에만 사용
모든 부분 문제를 구하기 때문에 시간 복잡도가 O(n^2)인 경우에는 사용하지 않는다.

DP 문제 유형

피보나치 수열
이항계수
최장 공통 부분 수열
최소 편집 거리
최소 비용 경로
최대 부분 수열 합

예시 코드 : 피보나치 수열

0 1 1 2 3 5 8 13 21 34 단순하게 재귀로 돌리면 이미 계산한 값을 또 계산하게 된다. 메모이제이션을 사용하여 이미 계산한 값을 저장해두고 재사용한다. https://www.acmicpc.net/problem/2748 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력 첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 1 10 예제 출력 1 55

1. 단순 구현 → 시간 초과

import sys
input = sys.stdin.readline
 
def f(n):
    return f(n - 1) + f(n - 2) if n > 1 else n
print(f(int(input())))

2. 메모이제이션 → 탑다운

# 메모이제이션을 사용하여 이미 계산한 값을 저장해두고 재사용한다.
cache = [-1] * 91
cache[0] = 0
cache[1] = 1  # 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
def f(n):
    # 처음 계산할 때는 -1로 초기화 되어있다.
    if cache[n] == -1:
        cache[n] = f(n - 1) + f(n - 2)
    return cache[n]
print(f(int(input())))

3. 타뷸레이션 → 바텀업

import sys
input = sys.stdin.readline
 
N = int(input())
cache = [-1] * 91
cache[0] = 0
cache[1] = 1 # 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
 
for i in range(2, N+1):
    cache[i] = cache[i-1] + cache[i-2]
print(cache[N])

시스매

탐색기

동적 계획법