알고리즘 기초 - 다이나믹 프로그래밍

반응형

다이나믹 프로그래밍(Dynamic Programming)이란?

메모리를 조금 더 사용하면서 연산 속도를 크게 증가시킬 수 있는 방법 중 하나입니다. 다이나믹 프로그래밍이 가능하려면 아래 두 가지 조건을 충족해야 합니다.

1) 최적 부분 구조: 작은 문제의 답을 모아 큰 문제를 해결할 수 있어야 합니다.

2) 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 수 있어야 합니다.

​

다이나믹 프로그래밍의  대표적인 문제에는 "피보나치 함수"가 있습니다.

피보나치 함수를 재귀 함수를 이용해 작성해보겠습니다.

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

 

그러나 재귀 함수를 이용하여 작성하는 경우 입력값 n이 커질수록 시간이 급격하게 늘어나는 문제가 생깁니다. 그 이유는 아래 그림처럼 동일한 함수들이 반복적으로 호출되기 때문입니다. 

위 그림에서 처럼 6번째 피보나치 수를 재귀를 이용하여 구하려면 f(3)을 3번 호출해야 합니다. 마찬가지로 f(4)도 반복적으로 호출됩니다. 이러한 문제점은 이미 계산된 수는 별도의 메모리 공간에 저장함으로써 해결할 수 있습니다. 아래 코드가 바로 다이나믹 프로그래밍을 사용한 코드입니다.

d = [0] * 100
d[1] = 1
d[2] = 1
n=99
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])

피보나치 수열을 저장하는 리스트 변수 d를 선언해줍니다. 그리고 이 리스트안에 차례대로 값을 채워주면 됩니다. 이 방법을 사용하면 중복 호출 없이 모든 경우가 한번만 계산되기 때문에 연산 수를 획기적으로 줄일 수 있습니다.

​

다이나믹 프로그래밍은 어려운 난이도에 속하는 문제입니다. 하지만 맨 위에서 설명한 두 가지 조건을 충족하고 문제가 의미하는 점화식만 잘 찾아낸다면 큰 어려움 없이 풀 수 있습니다.