다이나믹 프로그래밍

 컴퓨터를 이용하여 최적의 해를 구하는데 메모리 공간에는 한계가 있다. 그래서 우리는 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

 

 반대로, 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 증가시키는 방법이다. 다이나믹 프로그래밍은 탑다운과 보텀업 두가지 방식으로 나뉘다. 그리고 메모이제이션 기법까지 알아야 된다.

 

 피보나치 수열은 다이나믹 프로그래밍의 대표적인 예이다. 점화식으로 표현하여 푸는 것을 다이나믹 프로그래밍의 문제라고 생각하면 된다. 

 

def fibo(x):
	if x==1 or x==2 :
    	return 1
    return fibo(x-1)+fibo(x-2)

다음과 같이 코드를 짜면 fibo(x)에서 x에 값이 중복되면 계속 새로 계산해야된다는 단점이 있다. 그렇다면 시간복잡도가 기하급수적으로 늘어난다. 따라서 다이나믹 프로그래밍을 통해 문제를 해결한다. 다이나믹 프로그래밍을 항상 사용할 수 수는 없고 다음 조건을 만족할 때 사용할 수 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

피보나치 수열은 다음과 같은 조건을 만족한다. 이 문제를 메모이제이션(Memoization)기법을 사용해서 해결할 수 있다.

 

아래는 탑다운 방식이다.

#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화

d = [0]*100

def fibo(x):
    if x==1 or x==2:
        retun 1
    if d[x]!=0:
        return d[x]
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]

이렇게 되면 시간복잡도가 O(N)이 된다.

 

 이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위하여 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다. 

 

 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다. 피보나치 수열 문제를 보텀업으로도 풀어보자.

 

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]  

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.