다이나믹 프로그래밍이란?
-
다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 기법이다.
-
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
-
다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식
조건
다이나믹 프로그래밍은 다음 조건들을 만족할 때 사용할 수 있다.
-
큰 문제를 작은 문제로 나눌 수 있고 그 작은 문제의 답을 모에서 큰 문제를 해결할 수 있는 경우
-
동일한 작은 문제를 반복적으로 해결해야하는 경우
메모이제이션(Memoization)
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다.
- 한 번 계산한 결과를 말 그대로 메모리 공간에 메모하는 기법이다.
-
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
-
값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
- 메모이제이션은 한 번 구한 정보를 리스트에 저장하는 형태로 구현할 수 있다.
- 이 리스트를 보통 DP테이블이라고 부른다.
탑다운(top-down) vs 보텀업(bottom-up)
탑다운 방식은 재귀함수로 구현할 수 있고, 보텀업 방식은 반복문으로 구현할 수 있다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
뭐가 더 좋은지는 문제마다 다르다. 하지만 일반적으로 재귀함수를 사용하는 것 보다 반복문을 사용하는 것이 성능이 좀 더 좋다(오버헤드가 줄기 때문에). 시간 복잡도 측면에서는 동일하다.
따라서 특정 케이스를 제외하고는 그냥 자신이 편한걸로 쓰면 된다.
피보나치 수열문제는 다이나믹 프로그래밍 기법을 통해 효율적으로 풀 수 있는 문제 중 하나이다.
피보나치 수열 문제를 통해 DP문제의 흐름을 살펴보자.
우선 피보나치 수열을 점화식으로 나타내면 다음과 같다.
a[n] = a[n-1] + a[n-2],
a[1] = 1, a[2] = 1
n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
99번째 피보나치 수열을 구한다고 할 때 DP방식을 활용하지 않고, 재귀 함수를 사용하여 해결하면 다음과 같다.
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(99))이렇게 하면 n이 커질 수록 계산했던 함수가 반복적으로 호출되기 때문에 수행 시간이 기하급수적으로 늘어난다.
이런 문제에서 다이나믹 프로그래밍 기법을 사용하면 시간을 매우 단축시킬 수 있다.
탑다운 방식을 이용한 코드
DP테이블 초기화 (1부터 99까지 계산 가능하다고 가정)
d = [0] * 100
피보나치 함수를 재귀함수로 구현(탑다운)
def fibo(x):
# 종료 조건(1 또는 2일때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환(결과를 리스트에 저장)
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))보텀업 방식을 이용한 코드
DP테이블 초기화
d = [0] * 100
첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
피보나치 함수 반복문으로 구현
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])