동적 계획법(Dynamic programming)
동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘입니다. 즉, 재귀함수를 풀어나갈 때 쓰던 함수의 수식화를 시키면 됩니다. F(string) = F(string[1:n-2]) 라고 정의했던 것 처럼 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있습니다.
재귀 알고리즘과 굉장히 흡사하지만 그 결과들을 기록해놓고 가져다 쓴다는 점이 다릅니다.
결과를 기록하는것을 메모이제이션(Memoization) 이라고 하고 문제를 쪼갤 수 있는 구조를 겹치는 부분문제(Overlapping Subproblem)라고 합니다.
재귀와 동적계획법의 차이를 볼 수 있는 대표적인 예시중 하나로 피보나치 수열이 있습니다. 그냥 재귀함수를 이용해 피보나치 수열을 하게 되면 100번째 수열 값을 받을려면 연산이 엄청나게 많아지고 오래걸립니다. 하지만 기록해놓고 찾아서 쓰게되면 연산의 수를 엄청나게 줄일수 있습니다.
재귀함수를 이용한 피보나치
def fibo_recursion(n):
if n == 1 or n == 2:
return 1
return fibo_recursion(n - 1) + fibo_recursion(n - 2)
경우
n=4면 fibo(3), dibo(2)를 받고 fibo(3)은 다시 fibo(2)와 fib0(1)을 받는 방식이라 했던 연산을 계속해서 반복해서 하게 됩니다.
동적계획법을 이용한 피보나치
def fibo_recursion(n, fibo_memo):
if n in fibo_memo:
return fibo_memo[n]
nth_fibo = fibo_recursion(n-1, fibo_memo) + fibo_recursion(n-2, fibo_memo)
fibo_memo[n] = nth_fibo
return nth_fibo이경우는 값을 fibo_memo 딕셔너리에 값을 저장해둔채로 연산하기 때문에
했던 연산일 경우 기록된 값을 불러오기만 하면 됩니다.
이래서 시간복잡도의 차이가 엄청나게 많이 나게 됩니다.
