[자료구조] 동적계획법(dynamic programming, DP)

동적 계획법을 이해하려면 피보나치 수열부터 알아야한다.

동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있기 때문이다. 

 

피보나치 수열

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 143 ....

피보나치 수열은 제 2항까지 1을 반환, 제 3항부터는 바로 앞의 두 항을 더한 수로 정의된다.

(제 0항은 생략할 수 있다.)

 

피보나치 수열은 재귀를 통해 표현할 수 있다. 재귀란  (자신)함수를 다시 호출하는 방식이다.

int fibonaci(int n) {
  if(n <= 2){
    return 1;
   }
   else {
    return fibonaci(n-1) + fibonaci(n-2);
   }
}

 

하지만 피보나치 수열은 중복이 생기게된다. 그렇기 때문에 동적계획법을 사용하게된다.

 

동적계획법

 

피보나치와 재귀를 통해 표현한다는 점에서 비슷하지만, 동적계획법에서는 처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산이라면 기록되어 있는 값을 가져오는 것이다.

 

동적계획법을 이용해서 피보나치 수열을 구해보면 아래와 같다.

int arr[] = new arr[t];

int fibonaci(int n){
  if(n<=2) {
    return 1;
  }
  
  if(arr[n] == null){
    arr[n] = fibonaci(n-1) + fibonaci(n-2);
  }
  
  return arr[n];
}

배열을 생성하여 연산된 값을 배열에 저장한다.

 

n이 3이상일 경우 배열에 값이 있는지 검사를 하고, 값이 없을 경우 새로 연산하는 방식을 사용한다.

만약 값이 존재한다면, 바로 arr배열에 있는 값을 반환하기 때문에 중복을 막을 수 있는 것이다.

 

동적계획법을 이용하는 경우 시간복잡도는 O(n)으로 매우 효율적이다.

또한 동적계획법을 이용하려면 메모이제이션(Memoization)도 알아야한다.

 

메모이제이션(Memoization)에 대한 정보는 아래 포스팅을 통해 확인할 수 있다.

https://ddongttangcodding.tistory.com/58

[자료구조] 메모이제이션(Memoization)