Dynamic Programming 개념
다이나믹 프로그래밍
중복되는 연산을 줄이자
컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다. 그래서 효율적인 알고리즘을 작성해야 한다. 다이나믹 프로그래밍(동적 프로그래밍, Dynamic Prgramming)의 경우 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 상승시킨다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치의 점화식은 다음과 같이 표현할 수 있다.
\[a_{n+2} = f(a_{n+1}, a_n) = a_{n+1} + a_n\]이러한 다점화식은 인접 3항간 점화식이라고 부르는데 인접한 총 3개의 항에 대해서 식이 정의되기 때문이다. 최종적으로 정리를하면 다음과 같이 정의된다.
\[a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 2\]프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 리스트는 연속된 많은 데이터를 처리한다. 수학적 점화식은 재귀 함수를 사용하면 간단하다.
재귀함수를 사용한 피보나치
1
2
3
4
5
6
7
# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
1
3
그런데 이런식의 소스코드는 n이 커질수록 수행 시간이 기하급수적으로 늘어난다. 시간복잡도는 $O(2^N)$ 으로 표시한다. N=30이면, 약 10억 가량의 연산을 수행한다. 이처럼 피보나치 수열의 점화식을 재귀 함수를 이용해 만들 수는 있지만 효율적으로 계산할 수 없다. 이러한 문제를 해결할 때 다이나믹 프로그래밍을 사용하면된다. 단, 다이나믹 프로그래밍은 다음의 두가지 조건이 필요하다.
- 큰 문제를 작은 문제로 나눈 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 다음의 두가지 조건을 만족하는 대표적인 문제이다. 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로 메모이제이션(Memoization) 기법이 있다. 이 방법은 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가저오는 기법이다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.
한 번 구한 정보를 리스트에 저장하는 방식으로 메모이제이션을 구현하며, 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.
메모이제이션과 재귀함수를 사용한 피보나치
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
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))
1
218922995834555169026
정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 큰 문제를 작게 나누는 방법은 퀵 정렬도 있다. 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복 알고리즘으로 분류된다. 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다. 다이나믹 프로그래밍은 해결된 부분 문제에 대한 답을 저장해 놓기 때문에 시간 복잡도가 \(0(N)\)이다.
1
2
3
4
5
6
7
8
9
10
11
12
d = [0] * 100
def fibo(x):
print('f(' + str(x) + ')', end=' ')
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]
fibo(6)
1
f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)
위의 코드는 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하였으며, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라 한다. 반면 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 답을 도출하여 바텀업 방식이라고 한다.
반면 아래의 코드는 피보나치 수열 문제를 아래에서 위로 올라가는 바텀업 반식으로 푼것이다. 동일한 원리를 적용하되, 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
1
218922995834555169026
탑다운(메모이제이션)방식은 ‘하향식’이라고 하며, 바텀업 방식은 ‘상향식’이라고 한다. 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 이때 사용되는 결과 저장용 리스트는 ‘DP 테이블’이라고 하며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 그록해 놓는 넓은 개념이므로 다이나믹 프로그래밍과는 별도의 개념이다.
Comments