Dynamic Programming(동적 계획법)

도입

오늘은 동적계획법(DP)에 대해 소개 해보겠다.

먼저 필자는 아직도 동적 계획법을 잘 못한다.

Dynamic Programming이라는 어려운 이름에 ㅎㄷㄷ 할 수 있지만,

당시 연구실에서 연구비 많이 받을려고,

이런 이름으로 지었다고 한다.

 

1. 동적계획법 정의 

먼저 동적계획법은 

어떠한 문제를 다른 부분 문제로 나누는 것을 의미한다.

예를 들어 대표적인 예는 피보나치 수열이다.

Fibo n = Fibo n-1 + Fibo n-2

로 나타낼 수 있다.

Fibo n이라는 문제를 부분적으로 나눈 것이다.

이 경우에 n부터 시작해 함수 호출이 약 2배씩 증가함으로

총 O(2^N)에 근사하는 시간복잡도를 가지지만,

메모이제이션이라는 기법을 사용하면

간단해진다.

 

2. 메모이제이션

우리는 4번째 항의 피보나치 수열을 구한다고 하자.

전체적인 수행을 나타내 보자면,

Fibo 4=Fibo 3+Fibo 2

Fibo 3=Fibo 2+Fibo 1

Fibo 2=Fibo 1+Fibo 0(0)

Fibo 2=Fibo 1+Fibo 0(0)

이러한 동등한 항의 계산이 있을 경우

계산량이 기하급수적으로 증가하니,

이러한 항을 배열에 저장한다면

더 이상 함수 호출로 기저사례에 도달하지 않아도

원하는 답을 더욱 빠른 시간내에 도출 할 수 있다.

이런 저장을 메모이제이션이라고 하고,

이 경우 O(N)만에 구할 수 있다.

 

3. 여담

행렬을 이용시 O(log N)만에 피보나치 수열의 값을 구할 수 있다.