📂알고리즘

동적 프로그래밍

빌드업

문제를 풀 때, 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조^{optimal Substructure}를 가진다고 한다. 최적 부분 구조를 갖춘 문제의 예로써 가장 쉬운 것이 바로 피보나치 수를 구하는 것이다. $n$ 번째 피보나치 수는 $a_{n} = a_{n-1} + a_{n-2}$ 와 같이 구해지므로, 큰 문제 $a_{n}$ 에 작은 문제 $a_{n-1}$, $a_{n-2}$ 가 포함되어 있기 때문이다.

이를 간단하게 푸는 방법은 바로 재귀함수를 사용하는 것이다. 사실 최적 부분 구조를 갖고 있다면 어지간한 문제는 재귀함수로 풀 수 있어보이지만, 실제로 구현해보면 중복호출 때문에 몹시 비효율적이다.

정의

동적 프로그래밍^{dynamic Programing}은 이러한 어려움을 우회하기 위한 기법으로써, 다음의 조건을 만족할 때 사용해봄직하다:

• (i): 주어진 문제가 최적 부분 구조를 가진다.
• (ii): 재귀함수로 구현하기에는 비효율적이다.

예시

동적 프로그래밍의 개념은 간단하다. 작은 문제의 해답을 저장해가면서 중복 호출을 생략하는 것이다. 가령 6번째 피보나치 수 $a_{6}$ 를 구하기 위해서는 $$ a_{1} = 1 \\ a_{2} = 1 \\ a_{3} = 2 \\ a_{4} = 3 \\ a_{5} = 5 $$ 을 매번 계산하는 것이 아니라 메모리에 저장해두고, 마지막 $a_{4}$ 와 $a_{5}$ 만을 호출해서 $a_{6} = a_{5} + a_{4} = 8$ 을 계산하는 것이다. 이를 메모이제이션^memoization이라고 한다¹.

설명을 읽어보면 딱히 동적Dynamic이지는 않은데, 원래 제어 분야에서 해답을 테이블에 저장해나가면서 풀어간다는 것에서 유래된 말이라는 설이 있었다. 그러나 동적 프로그래밍의 고안자인 벨만^bellman이 직접 자신의 저서에서 밝히기로는 그냥 다이내믹이라는 말이 멋있고, 펀딩을 받기 좋은 단어라서 선택했다고 한다.

다음은 $a_{36}=14930352$ 을 두 가지 방법으로 계산하고 그 시간을 계산한 움짤과 그 파이썬 코드다. 동적프로그래밍으로는 0.01초가 조금 넘는 시간밖에 걸리지 않았지만, 재귀함수로는 5초이상 걸렸다. 이 차이는 $n$ 이 클수록 더 커진다. 이론적으로도 주어진 $n$ 에 대해서 재귀함수는 지수적으로, 동적 프로그래밍은 선형적으로 시간을 쓴다는 것을 간단하게 증명할 수 있다.

코드

import Time

def fibo1(n) :
    if n==1 or n==2 :
        return 1
    else :
        return fibo1(n-1) + fibo1(n-2)

def fibo2(n) :
    memoization = [1,1]
    for i in range(n-2) :
        memoization.append(memoization[-1]+memoization[-2])
    return memoization[-1]

start = Time.time() 
print(fibo2(36))
print("동적 프로그래밍으로 계산할 때 걸린 시간 : %5.3f" % (time.time() - start))

start = Time.time() 
print(fibo1(36))
print("재귀함수로 계산할 때 걸린 시간 : %5.3f" % (time.time() - start))