동적 프로그래밍

동적 프로그래밍

Dynamic programing

빌드업

문제를 풀 때, 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조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이라고 한다. 1

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

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

Honeycam2019-08-2614-03-10.gif

코드


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))

  1. 메모Memo에서 나온 말로써, 메모라이제이션Memoriztion이 아니다. ↩︎

댓글