동적 계획법(Dynamic Programming)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• 동적 계획법(Dynamic Programming)
• 메모이제이션(memoization) 
• 메모이제이션을 활용한 피보나치 수열

 

<동적 계획법>

동적 계획법(Dynamic Programming)

• 동적 계획법은 복잡한 문제를 재귀를 통해 간단한 하위 문제로 분류하여 단순화하여 해결하는 방법이다.
• 어떤 문제가 최적 부분 구조, 중복되는 문제를 가지고 있으면 동적 계획법으로 해결 가능하다.

 

메모이제이션(memoization)

• 메모이제이션은 동적 계획법의 핵심이다.
• 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하는 것.

 

ex) 메모이제이션을 활용한 피보나치 수열

피보나치 수열은 제 0항을 0, 제 1항을 1로 하고, 그 다음 항부터는 이전 두 개 항의 합으로 나타나는 수열이다. 이를 점화식으로 표현하면 fib(n)=fib(n−1)+fib(n−2)(n>2),fib(0)=0,fib(1)=1가 된다.

def fib(n):
    if n == 1 or n == 0: 
        return n 
    return fib(n - 1) + fib(n - 2)

• 위 코드는 분명 잘 작동하지만, 숫자가 조금만 커져도 시간이 너무 오래 걸린다는 단점이 있다.
• 위의 동그라미는 아래 두 개의 동그라미의 합으로 채워진다. 이 과정에서 fib(2)는 3번, fib(3)는 2번 계산됨을 알 수 있다. 이럴 때 사용하면 좋은 기법이 바로 메모이제이션(memoization)이다. 즉, 한번 구한 값을 memo해놨다가 다시 쓰는 것이다.
• 원래는 fib(4)=2+fib(2)로 오른쪽의 fib(2)를 다시 계산해야겠지만, 메모이제이션(memoization)을 이용하면 memo해놨던 fib(2)를 읽어와 fib(4)=2+1=3을 간단히 계산할 수 있다. 

칠해진 노드만 계산을 수행하며, 나머지는 이미 캐시된 값을 불러온다.

def fib(n):
    DT = [None] * (n + 1)
    DT[0], DT[1] = 0, 1
    return cal_fib(DT, n)

def cal_fib(DT, n):
    if DT[n] == None:
        DT[n] = cal_fib(DT, n - 1) + cal_fib(DT, n - 2)
    return DT[n]