동적 계획법

동적 계획법

동적 계획법은 부분 문제들의 해를 결합하여 문제를 해결하는 최적화 방법으로, 문제를 서로 겹치지 않는 부분 문제들로 분할한 후에 재귀적으로 해결한 다음, 이 해들을 결합하여 원래의 문제를 해결하는 방법입니다. 분할 정복 알고리즘이 공유되는 부분 문제를 반복적으로 해결하여 중복 계산을 하게 될 때 동적 계획법을 사용한다면 각 부분 문제를 한 번만 푼 후 그 해를 테이블에 저장해두면 각 부분 문제를 풀 때마다 다시 계산하는 불필요한 작업을 피할 수 있습니다.

동적 계획법은 다음 4단계를 따릅니다.

• 최적해의 구조적 특징을 찾는다.
• 최적해의 값을 재귀적으로 정의한다.
• 최적해의 값을 일반적으로 상향식 방법으로 계산한다.
• 계산한 정보들로부터 최적해를 만든다.

메모이제이션(Memoization)과 하향식(Top-down)

이 방법은 문제를 재귀적으로 해결하지만, 각 부분 문제의 결과를 보통 배열이나, 해시 테이블에 저장해두는 방식입니다. 따라서 이전에 푼 적 있는지 확인하고, 이전에 풀었다면 그 값을 리턴합니다.

import math
import sys

input = sys.stdin.readline
n = int(input())
dp = [-1] * (n + 1)
dp[0] = 1
dp[1] = 1

def fib(n):
    if dp[n] != -1: # 이전에 연산을 수행했었는지 확인
        return dp[n]
    dp[n] = fib(n - 1) + fib(n - 2) # 배열에 저장
    return dp[n]

print(fib(n))

상향식(Bottom-up)

상향식은 부분 문제의 ‘크기’라는 개념을 따르는데, 특정 부분 문제를 푸는 것이 더 ‘작은’ 부분 문제를 푸는 것에만 의존합니다. 부분 문제를 크기별로 정렬한 후 가장 작은 것을 첫번째로 하여 크기 순으로 풀면서 각 부분 문제를 처음 풀었을 때의 해를 저장합니다.

import math
import sys

input = sys.stdin.readline
n = int(input())
dp = [1, 1]
for i in range(n):
    dp.append(dp[-1] + dp[-2])
    
print(dp[n])

일반적으로 하향식 방법이 모든 부분 문제를 재귀적으로 호출하지 않는 경우를 제외하고는 똑같은 점근적인 수행 시간을 가진 알고리즘들을 만듭니다. 상향식 방법은 프로시저 호출에 대한 오버헤드가 더 작아 종종 훨씬 더 나은 상수 인자를 가집니다.

Optimal Structure

부분문제의 최적의 솔루션을 사용해서 주어진 문제의 최적의 해를 구할 수 있다면, 이를 Optimal Structure 라고 합니다. 피보나치 수열의 경우 n - 1 까지 구하는 방법이 Optimal Structure 이 될 수 있고, 그 작은 것 또한 Optimal Structure가 될 수 있습니다.