[JS] 다이나믹 프로그래밍

 1. 다이나믹 프로그래밍

 다이나믹 프로그래밍이란, 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 이전에 나는 퀵 정렬, 병합 정렬, 이진검색과 같은 자료구조를 포스팅한 적이 있다. 이 셋을 언급한 이유는 분할 기법을 이용하기 때문이다. 퀵 정렬, 병합 정렬, 이진검색은 분할 기법을 이용해서 평균 시간복잡도 O(Nlog₂N)이라는 굉장히 빠른 속도를 장점으로 가질 수 있었다. 하지만 되게 빨라보이는 분할기법도 어떤 상황에서는 단점이 존재하는데, 그것은 바로 동일한 문제를 반복해서 푼다는 것이다. 그 대표적인 예시가 피보나치 수열이다.

 

 

 피보나치 수열은 제 0항, 제 1항을 1로 제쳐두고 두 번째 항부터는 앞에 두 수를 더한 값을 결과로 두는 수열을 말한다. 피보나치 수열은 보통 프로그래밍 언어에서 재귀용법을 배울 때 첫 예시로 등장하곤 한다. 피보나치 수열의 식은 다음과 같이 표현할 수 있다.

$$ F_{n} = F_{n-2} + F_{n-1} $$

 

 또한, 우리는 피보나치 수열을 간단하게 아래와 같이 프로그래밍할 수 있다. 이 프로그래밍은 대표적인 분할 기법임과 동시에 분할 기법의 단점을 보여주는 예시다.

funtion fibonachi(n){
  if(n === 1) return 1;
  if(n === 2) return 1;
  return fibonachi(n-2) + fibonachi(n-1);
}

fibonachi(5);               // (1)
fibonachi(50);              // (2)

 

 위 예시를 보자. 출력 상황 (1), (2) 두개가 주어져있는데, (1)의 경우 5를 짧은 시간안에 출력할 것이다. 하지만 (2)는 출력 결과가 나타나지 않을 것이다. 그 이유는 동일한 문제를 반복해서 푸는것으로 인한 딜레이 때문이다. (2)의 상황을 그림으로 나타내면 다음과 같다.

 

 

[그림 1] (2) 의 상황

 

 처음에 50을 입력받으면, 어느 길이든 간에 종착지는 n이 2 또는 1일 때이다. 그리고 50번째까지 계속 더해지고 더해져서 최종 결과를 출력할 것이다. 이는 엄청난 시간을 야기한다. 왜냐하면 밑에 층으로 내려갈 수록 2의 n승 번씩 계산이 늘어나기 때문이다. 그래서 위 프로그램에 50을 입력했을 때 걸리는 시간은

$$ 2^{50} $$ 

 이다. 2를 10번 곱한 값이 1024이고 이 값을 1000이라고 볼 때, 2를 50번 곱한 값은 0이 15개인 1000000000000000이다. 아무리 컴퓨터라도 저정도 큰 시간은 감당할 수가 없다. 시간의 단위를 ms로 보더라도, 저 시간은 하루를 초로 계산한 것보다도 많다. 이 상황을 타개하기 위해서 하나의 문제를 단 한번만 풀 수 있도록하는 다이나믹 프로그래밍기법을 이용해야한다. 이 상황에서 그 목적을 이루기 위해서는 메모이제이션, 즉 저장 장치를 만들어야한다. [그림 1]을 보면 47번째 피보나치 수열을 계산하는 것에 3번의 반복이 필요하다. 이를 세 번 반복할 경우 2의 47승에 세 번을 곱한 값의 시간이 걸린다. 하지만 계산한 값을 미리 저장한다면? 계산할 필요 없이 꺼내쓰기만 하면 된다.

 

[그림 2] 메모이제이션

 

 따라서 이 방법을 프로그래밍하면 다음과 같다.

const memory = [0];


function fibonachi(n){
  if(n === 1)
    return 1;
  if(n === 2)
    return 1;
  if(memory[n] != null)
    return memory[n];
  return memory[n] = fibonachi(n-1) + fibonachi(n-2);
}

console.log(fibonachi(50)); // 12586269025

 

2. 참고 자료

안경잡이 개발자 - 20. 다이나믹 프로그래밍(Dynamic Programming)