1. 다이나믹 프로그래밍
시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터로도 풀기 어렵다. 이 때문에 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 하지만 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 아주 빠르게 할 수 있다. 그 중 하나가 다이나믹 프로그래밍 기법이다.
다이나믹 프로그래밍은 메모리를 적당히 사용해서 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 한번 계산해서 나온 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
다이나믹 프로그래밍을 활용하는 이유
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정한다. 우리는 점화식을 이용해 수열의 항이 이어지는 형태를 간결하게 표현할 수 있다. 점화식은 인접한 항들 사이의 관계식을 의미한다. 피보나치 수열의 점화식은 $a_{n} = a_{n-1} + a_{n-2}, a_{2}=1, a_{1}=1$ 처럼 표현할 수 있다. 이를 코드로 구현하면 다음과 같다.
# 재귀 함수로 구현
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))
# 3
하지만 이렇게 작성하면 n이 커질수록 연산 시간이 기하급수적으로 늘어난다. 일반적으로 $O(N^{N})$의 시간이 소요된다. f(6)의 호출과정을 그림으로 그려보자.
동일한 값이 반복적의로 호출되는 것을 알 수 있다. a3는 총 세번 호출되었다. 즉, a6를 구하기 위해서 a3은 총 세번 계산된 것이다. 따라서 위 코드처럼 재귀함수를 사용해 만들수는 있지만 단순히 매번 계산하도록 하면 문제를 효율적으로 풀 수 없다. 따라서 이러한 문제는 다이나믹 프로그래밍을 사용하면 된다.
다이나믹 프로그래밍을 사용할 수 있는 조건은 다음과 같다.
- 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있을 때 ➔ 탑다운 방식 (Top-Down)
- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결 ➔ 보텀업 (Bottom-Up)
다이나믹 프로그래밍을 구현하는 방법은 탑다운 방식 (Top-Down)과 보텀업 방식(Bottom-Up) 2가지가 있다.
2. 탑다운 방식 (Top-Down) - 재귀함수 사용
탑 다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출한다. 계산된 결과를 일시적으로 기록해 놓는 것이 메모이제이션(Memoization)이다. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다. 메모이제이션은 탑 다운 방식에 국한된 표현이다.
위에서 봤던 피보나치 수열을 탑다운 방식으로 구현해보자.
# 탑 다운 다이나믹 프로그래밍 - 재귀함수로 구현
d = [0] * 100 # # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
# 피보나치 함수
def fibo(x):
# 종료조건 (1 or 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))
# 218922995834555169026
6번째 피보나치 수를 호출할 때는 다음처럼 진한 노드들만 방문하게 된다.
탑 다운 방식은 재귀를 제한하기 위해 sys 라이브러리에 있는 setrecursionlimit()함수를 사용하기도 한다.
3. 보텀업 방식(Bottom-Up) - 반복문 사용
보텀업 방식은 다이나믹 프로그래밍의 전형적인 형태로 작은 문제부터 차근차근 답을 도출한다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP테이블이라고 한다.
이번에는 피보나치 수열을 보텀업 방식으로 구현해보자.
# 보텀업 다이나믹 프로그래밍 - 반복문으로 구현
# dp테이블
d = [0] * 100
d[1]=1
d[2]=1
n=98
for i in range(3,n+1):
d[i] = d[i-1]+d[i-2]
print(d[n])
# 135301852344706746049
일반적으로 반복문을 이용한 다이나믹 프로그래밍이 성능이 좋다.
4. 시간 복잡도: O(N)
정리하면 다이나믹 프로그래밍은 한번 계산해서 나온 결과는 별도의 메모리 영역에 저장하여 연산 시간을 빠르게 하는 방법이다. 다이나믹 프로그래밍으로 문제를 풀려면 먼저 ①부분 문제들의 중복을 확인한 뒤에 ②문제에서 요구하는 내용을 점화식으로 표현하여 ③보텀업 다이나믹 프로그래밍을 구현하면 된다. dp테이블의 크기는 정수의 범위만큼 설정하면 된다.