1950년대 미국의 수학자인 벨만(Richard E. Bellman)이 최적화 문제(Optimization Problem)를 해결하기 위해서 고안한 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. (위키백과)
2. 다이나믹 프로그래밍 조건
다이나믹 프로그래밍을 적용하려면 아래 2가지 조건을 만족해야한다.
1) 부분 반복 문제(Overlapping Subproblem)
작은 문제들이 중복된다는 것이다. DP는 기본적으로 문제를 나누고, 그 문제의 결과 값을 재활용해서 전체 답을 구하므로 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
대표적인 예가 피보나치 수열이다.
f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타난다. 그러므로 우리는 1회 계산했을 때, 저장된 값을 재활용할 수 있게 되는 것이다.
2) 최적 부분 구조(Optimal Substructure)
작은 부분 문제에서 구한 최적의 답으로, 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.
예를 들어, 최단경로 찾기가 있다.
만약, A → B까지의 가장 짧은 경로를 찾고자 하는 경우, 중간에 X가 있을 때, A → X , X → B가 많은 경로들 중 가장 짧은 경로라면 전체 최적 경로도 A → X → B가 된다.
이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있고, 피보나치 수열도 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조를 갖고 있다.
3. Memoization(메모이제이션)
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.(위키백과)
예를 들어,
위의 피보나치 수열 함수 호출 트리 f(n) = f(n-1) + f(n-2) 에서
f(5)에서 구한 f(2)나 f(4)에서 구한 f(2)나 f(3)에서 구한 f(2)나 다 같은 값이다.
이걸 반복해서 연산하는 것은 비효율적이므로 연산 과정을 줄이기 위해 메모이제이션(Memoization)을 사용한다.
즉, 메모리에 계산한 값을 저장해 나감으로써 다음 반복 수행때는 연산 없이 저장된 값을 불러와주는(재사용하는) 방법이며, 메모이제이션은 동적 계획법의 핵심이 되는 기술이다.
4. 다이나믹 프로그래밍 해결 방법
DP의 구현 방식에는 대표적으로 2가지가 있다.
1) Top-Down(하향식)
큰 문제를 작은 문제로 쪼개면서 풀어나가는 방식
메모이제이션을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나
재귀함수를 사용하여 구현
예시
# 한번 계산된 결과를 메모이제이션하기 위한 리스트
memo = [0] * 100
# 피보나치 수열을 재귀함수로 구현(top-down)
def f(x):
# f(1) = f(2) = 1
if x == 1 or x == 2:
return 1
# 이미 계산한 적있는 문제라면 그대로 반환
if memo[x] != 0:
return memo[x]
# 아직 계산하지 않은 문제라면 피보나치 결과 반환
memo[x] = f(x-1) + f(x-2)
return memo[x]
print(f(99))
2) Bottom-Up(상향식)
가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
타블레이션(tabulation)을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나
반복문을 이용하여 구현
👏타블레이션(tabulation)이란 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법을 말한다. 타블레이션이라고 부르는 이유는 작은 문제부터 큰 문제까지 하나하나 테이블을 채워간다는 의미 때문이다.
예시
# 작은 문제부터 해결해서 저장할 dp 테이블
dp = [0] * 100
# f(1) = f(2) = 1 부분
dp[1] = 1
dp[2] = 1
n = 99
# 피보나치 수열을 반복문으로 구현(bottom-up)
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])
