동적 프로그래밍
동적 프로그래밍
우선 전혀 동적이지 않다.
옛날 수학자인 벨만이라는 사람이 고안해낸 기법인데, 그저 단어가 멋있어서(?) 연구비를 위해 선택했다는 일화가 있다(…).
동적 프로그래밍(Dynamic Programming)은 최적화 이론의 한 기술이며,
복잡한 문제를 쪼개어 간단한 부분 문제로 나눈 후에 답을 구하고, 이를 사용해 더 큰 문제의 답을 해결하는 최적화 기법이다.
얼핏 들으면 분할 정복 방법과 유사해 보이지만, 다른 점도 분명히 있다.
공통점
- 부분 문제로 분할
- 재귀적 접근
차이점
- 부분 문제의 중복 처리 :
- 동적 프로그래밍에서는 동일한 부분 문제가 여러 번 반복해서 등장하는 경우에 유리하다
- 중복된 부분 문제의 해를 저장하고 재사용함으로써 시간 복잡도를 줄인다
- 최적 부분 구조 :
- 동적 프로그래밍에서는 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성될 수 있어야 한다
- 문제 해결 접근 방식 :
- 동적 프로그래밍에서는 Memoization(하향식) 또는 Tabulation(상향식) 방법으로 구현된다
- 반면 분할 정복 방법에서는 문제를 반으로 나누어서 해결한다
처리 과정
동적 프로그래밍 방법의 전체적인 처리 과정은 다음과 같다:
- 주어진 문제에 대해서 최적해를 제공하는 점화식을 도출한다.
- 가장 작은 소문제부터 점화식의 해를 구한 뒤 이를 cache에 저장한다.
- cache에 저장된 소문제의 해를 이용하여 점차적으로 큰 상위 문제의 해를 구한다.
두 가지 방식
위 차이점에서 언급했는데, 하향식인 메모이제이션 또는 상향식인 타뷸레이션 방법으로 문제를 해결한다.
둘의 차이점을 알아보자:
| Top-Down | Bottom-Up | |
|---|---|---|
| 구현 | 재귀 | 반복문 |
| 저장 방식 | 메모이제이션 | 타뷸레이션 |
메모이제이션
한 번 구한 답들은 저장해두자
부분 문제들의 답을 한 번 구했으면 다시 구할 필요가 없도록 cache에 저장해두고 갖다 쓰는 방식이다. 이는 중복 연산을 방지함으로 속도를 향상시킬 수 있다.
메모이제이션 방식은 필요한 부분 문제들만 구해서 DP테이블에서 해당하는 칸들만 채우며, 이는 Lazy-Evaluation이라고도 한다.
DP 테이블이란?
동적 프로그래밍을 사용할 때 이전에 구한 부분 문제의 해를 저장해두는 테이블.
Cache와 같은 말이다.
타뷸레이션
부분 문제들의 답을 미리 다 구해두면 편하다
테이블을 채워나간다는 의미로 타뷸레이션이라고 한다. 메모이제이션과 같이 부분 문제들의 해를 구하며 cache에 저장해두지만, 타뷸레이션 방법에서는 필요 없는 부분 문제들까지도 모두 해를 구하여 cache에 저장한다. 이는 Eager-Evaluation이라고도 한다.
예제
가장 대표적으로 사용되는 예는 피보나치 수열이다.
재귀함수 설명할때도 대표적으로 사용되는 예인데, 아무래도 동적 프로그래밍이 재귀에 기반을 두고 있어서 같이 쓰이는 듯 하다.
피보나치 수열의 기본 전제는 다음과 같다:
- 첫 항은 0 : f(0) = 0
- 두 번째 항은 1 : f(1) = 1
- 이후의 항들은 직전 두 항의 합 : f(i) = f(i-1) + f(i-2)
메모이제이션
1
2
3
4
5
6
7
8
9
def fibonacci(n : int, table : List[Any]) -> int:
if n <= 1:
return n
if table[n] is not None:
return table[n]
table[n] = fibonacci(n-1, table) + fibonacci(n-2, table)
return table[n]
메모이제이션에선 보다시피 필요한 부분만 채워서 값을 반환한다.
타뷸레이션
1
2
3
4
5
6
7
8
9
10
11
def fibonacci (n : int, table : List[Any]) -> int:
if n <= 1:
return n
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
타뷸레이션에선 보다시피 전체 테이블을 먼저 다 만들고, 해당 테이블에서 값을 찾아 반환한다.