다이나믹 프로그래밍

컴퓨터의 연산에는 크게 두 가지의 제약사항이 존재한다. 메모리 공간과 연산 속도의 한계이다.  이러한 상황에서 메모리 공간을 약간 더 할애 한다면 비약적으로 연산속도를 증가시킬 수 있는 방법이 있다. 이 대표적인 방법이 다이나믹 프로그래밍 , 동적 게획법이다. 

 

다이나믹 프로그래밍은 2가지 방식 텀 다운과 보텀 업으로 나눌 수 있는데 텀 다운 같은경우에는 맨 위의 큰 문제에서 아래 문제로 쪼개 가며 해결해가는 하향식 해결 방법이고 보텀업의 경우에는 작은 문제들을 먼저 해결해가면서 큰 문제로 합쳐서 해결하는 상향식 해결방법이다.

 

 

다이나믹 프로그래밍을 설명하는데에는 피보나치 문제가 주로 이용된다

피보나치 수열에 대해서 설명은 생략하고 재귀적으로 풀어낸 피보나치 소스코드를 살펴보면 아래와 같다.

 

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

 

이 때 소스코드는 피보나치 수열의 크기가 커지면 심각한 문제를 야기한다. fibo의 인자값이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이는 아래의 그림를  확인해보자

 

 

피보나치의 층마다 연산이 일어나는 함수의 호출 fibo의 호출이 2^n승만큼 이루어지는 것을 확인 할 수 있다 즉 O(2^n)의 시간 복잡도를 평균으로 가지는 것이다. 이 때의 2^n은 복잡도 측면에서 큰 복잡도를 가진다. 만약 에를 들어 F(100)을 계산한다면 2^100으로 약 1,000,000,000,000,000,000,000,000,000,000번의 호출을 하여 연산을 진행 할 것이고 이는 우리의 수명이 다할 때 까지 연산을 진행해도 답을 도출할 수 없다. ( 일반적인 컴퓨터가 1초에 1억번의 연산을 한다고 한닫면 현대의 기술로는 답을 찾기 힘들다. )

 

 

이 문제는 다이나믹 문제로 효율적으로 해결할 수 있다. 이 때 다이나믹 프로그래밍을 하기 위해서는 다음의 조건을 만족하는 문제여야 한다.

 

•  큰 문제를 작은 문제로 나눌 수 있어야 한다.
•  작은 문제에서  구한 답은 그것을 포함하는 큰 문제에서도 동일하게 적용되어야 한다.

 

우리는 위와 같은 피보나치 문제를 다이나믹 프로그래밍 중에서 메모이제이션 기법을 사용해서 해결할 수  있다. 

메모이제이션이란 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하여 메모한 결과를 그대로 가져오는 기법으로 캐싱이라고도 한다.

이는 파이썬에서 한번 구한 정보를 리스트에 저장하면서 구현할 수 있다. 저장해둔 정보는 재귀적으로 수행하다가 같은 정보의 출현 시 리스트에서 답을 빼오기만 하면 새로운 호출없이 문제를 해결할 수 있다.

이를 이제 소스코드로 구현해보자

 

d = [0] * 100     # 한번 계산된 결과를 메모이제이션 하기 위한 리스트를 초기화한다. def fibo(x):       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]

 

이 소스코드를 이용해서 문제를 접근하면 동일한 인자값에 대한 함수 실행은 한번만 실행되고 다시 실행되지 않는다 즉 맨 왼쪽의 트리에서 다음 단계로 실행하기 위한 d[x] 연산 외에 그 밑의 함수는 인자로 들어온 값보다 작은 인자들만 들어오는 것이 보장되므로 나머지 트리들은 연산이 아닌 리스트에서 값을 가져와서 메모리에 적재하는 추가적인 오버헤드를 제외하면은 O(N)정도의 시간복잡도를 가진다고 볼 수 있다.

 

 

정리하자면 다이나믹 프로그램이란 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

이는 분할 정복과 비슷하지만 차이가 있다

 

분할정복같은 경우에는 정복한 문제에 대해서 재접근하지 않는다. 퀵 정렬을 예로 들면 피벗을 옮기면서 정렬된 후의 피벗에 대해서 재접근을 하지 않고 그 다음 분할된 문제에 대해서만 처리를 한다.

하지만 다이나믹 프로그래밍 같은 경우에는 한번 해결된 문제도 재접근이 가능하고 이를 가능하도록 하기 위해서 메모제이션 기법을 사용하여 해결한 문제에 대해서 저장해 두었다가 동일한 문제를 해결할 때 반복 실행을 줄여서 시간적 복잡도의 향상을 가져오게 한다.

 

 

 

+ 파이썬의 경우 기본 자료형인 리스트 자료형이 연결 리스트의 기능을 포함함 ( 다른 프로그래밍 언어의 배열과의 차이점 )