[자료구조 이론] 동적계획법(Dynamic Programming, DP)

동적 계획법이란?

동적계획법은 Dynamic Programming, DP라고도 불린다. 동적계획법은 하나의 문제를 "단 한번만" 푸는 문제이다. 분할정복과 비슷한 성격을 띄고있다. 단 다른 점이라면, 분할정복같은 경우에는 동일한 문제를 여러번 푼다는 점에 있어서 동적계획법과 차이가 있다.

 

동적계획법을 사용하는데에 있어 아래 두가지 조건을 만족해야한다.

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다
2. 작은 문제에서 구한 정답이 큰 문제에서도 동일한 정답으로 적용해야한다.

 

동적계획법은 메모이제이션(Memoization)기법을 사용하면서 값을 구하게 된다. 메모이제이션이란, 이미 구한 답을 잠시 배열에 기록해두고, 나중에 동일한 연산을 할 때 사용한다는 기법이다. 

 

분할정복에서의 비효율성

분할정복법의 비효율성은 대표적으로 피보나치 수열 알고리즘에서 볼 수 있다.

피보나치 수열은 기본적으로 자신보다 앞에있는 두 수를 더한 값으로 수열을 만들어 나간다. 그리고 아래 코드와 같이 이를 재귀적 처리로 작성해 풀었다. 

def fibo_recursion(x):
    if x <= 2:
        return 1
    else:
        return fibo_recursion(x-1) + fibo_recursion(x-2)

하지만 이 재귀적 풀이의 치명적 단점이 있다. 바로 위의 사진과 같이 동일한 값을 한번 구했음에도 재귀적 연산에 의해 여러번 반복적으로 계산해야한다는 단점이 있다. 즉 불필요한 연산이 많이 이루어진다는 것이다. 분할정복 재귀 피보나치는 기본적으로 연산 2번을 n층의 트리만큼의 연산이 들어가기 때문에 재귀적인 피보나치 수열의 시간 복잡도는 O(2^n)이다. 한번 50번째 피보나치 수를 구하고 싶다 가정하고 위 함수에 넣으면 답이 나오지 않는다. 이유는 그만큼 연산이 많기 때문에 연산이 끝나지 않는것이다.

피보나치를 DP로 풀어보자

이번에는 피보나치를 DP를 이용해서 풀어보자. DP를 이용해서 풀때는 기본적으로 메모이제이션, 즉 연산한 값을 배열에 저장해야한다는 가정이 있었다.  그렇기 때문에 값을 저장할 배열 하나를 선언해 주어야한다. 코드는 아래와 같이 작성했다.

count = int(input())
datas = [None] * (count + 1)

def fibo_DP(x):
    if x <= 2: return 1
    if datas[x]:
        return datas[x]
    else:
        datas[x] = fibo_DP(x-1) + fibo_DP(x - 2)
        return datas[x]

if __name__ == "__main__":
    print(fibo_DP(count))
    print(fibo_recursion(count))

DP를 이용해서 구하는 경우는 시간복잡도가 O(n)밖에 소요되지 않는다. 기본적으로 구한 값은 배열에 저장되고, 다시 연산하지 않고 배열에서 값만 불러오면 되기 때문이다.