현실의 문제는 너무 다양하고 컴퓨터로 해결하기 어려운 문제도 있다. 가령 최적의 해를 구하기 위해 매우 많은 시간이 필요하거나 메모리 공간이 많이 필요한 경우들이 이에 해당한다. 컴퓨터는 연산속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터 개수도 한정적이라는 사실이 이러한 제약들을 발생시킨다.
그래서 연산 속도와 메모리 공간을 최대한으로 사용할 수 있는 효율적인 알고리즘을 작성해야한다. 이때 어떤 문제들은 약간의 메모리 공간을 더 사용하면 연산 속도를 비약적으로 상승시킬 수 있는 방법이 있는데 가장 대표적인게 바로 다이나믹 프로그래밍이다.
피보나치 수열은 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예이다. 아래 코드는 재귀함수를 통해 구현한 가장 간단한 형태의 피보나치 수열이다.
1
2
3
4
5
6
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))
그러나 이렇게 코드를 작성하는 건 n이 커지면 커질수록 처리 시간이 기하급수적으로 늘어나는 치명적인 문제가 있다. 이때의 시간 복잡도는 O(N^2)이기 때문이다.
따라서 피보나치 수열같은 문제는 다이나믹 프로그래밍을 사용하면 효과적으로 문제를 해결 할 수있다. 다만, 다이나믹 프로그래밍은 언제나 사용가능한 건 아니고 두가지 조건이 선행되야한다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에도 동일하다.
피보나치 수열 문제가 바로 이 두조건을 충족하는 문제이다. 이 문제를 다이나믹 프로그래밍의 한 방법인 메모이제이션 기법을 사용하여 해결하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 한번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
def fibo(x):
# 0 이상의 x값을 입력
if x == 0:
return '0 보다 큰 정수를 입력해주세요'
# 종료조건
if x == 1 or x == 2:
return 1
# 이미 계산한적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
d[x] = fibo(x-2) + fibo(x-1)
return d[x]
print(fibo(99))
메모이제이션은 한번 구한 결과를 메모리 공간에 메모해놓고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 캐싱이라고 부르기도 한다. 이렇게 문제를 풀면 시간 복잡도는 O(N)이 되는데 구한값은 다시 계산이 이루어지지않는 대신 저장되고 다음 결과를 도출할때 사용되기만 하기 때문이다.
이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을 큰문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 한다. 반면 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업 방식이라고 말한다.
아래의 코드는 반복문을 사용한 바텀업 방식의 다이나믹 프로그래밍 소스코드다.
1
2
3
4
5
6
7
8
9
10
11
12
# DP 테이블 초기화
d = [0] * 100
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])
탑다운과 바텀업 중에서 바텀업 방식이 더 전형적인 다이나믹 프로그래밍 방식이다. 따라서 가능하다면 바텀업 방식으로 구현하기를 권장한다.
참고로 바텀업에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.