Dynamic Programming (with JavaScript)

# Dynamic Programming (DP)

Wikipedia의 설명을 인용하자면 일반적인 Dynamic Programming이란,

'it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.'

즉, 어떤 문제를 해결하고자 할 때 작은 단위의 문제를 재귀적으로 풀어내어 단순화시키는 것을 의미한다.

따라서 DP를 활용하기 위해서는 다음 조건이 필요하다.

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다. (optimal substructure)

 

범위를 Computer Sicence로 한정시키자면 여기에 하나의 조건이 더 추가되게 된다.

2. 작은 문제의 답은 그것을 포함하는 큰 문제에서도 동일해야 한다. (overlapping sub-problems)

 

DP에서는 이 overlapping 한 속성을 이용해 한 번 계산한 값을 저장해 놓고 이후에 저장된 값을 재사용하는 형태로 효율성을 증대시킨다.

메모리와 효율성 간 trade-off를 감수하는 것이다.

 

또한 이 두 번째 조건이 얼핏 보면 비슷한 divide and conquer algorithm과 DP를 구분하는 기준이 된다.

Divide and conquer은 해결한 작은 문제들이 서로 영향을 미치지 않으나 DP는 어떤 문제를 해결하는데 다른 문제의 해답이 직접 활용되며 영향을 미친다.

Divide and conquer의 예시인 quick sort에서 pivot의 왼쪽 결과가 오른쪽 결과에 영향을 미칠 수 없으나, DP의 예시인 피보나치 수열에서 f(3)은 f(4), f(5)를 계산하는데 직접적으로 활용한다는 점을 생각하면 이해하기가 편리하다.

 

# 피보나치 수열 예시

DP를 설명하는데 가장 많이 활용되는 피보나치 수열을 살펴보자.

피보나치 수열은 다음과 같은 점화식으로 표현될 수 있다.

$$ a_{1} = a_{2} = 1 $$

$$ a_{n} = a_{n-1} + a_{n-2}\quad\quad\{n\in {3, 4, ...}\} $$

피보나치 수열은 점화식으로 표현된다는 점에서 1번 조건을 만족시키며, a_n-1, a_n-2 값이 한 번 정해지면 그대로 다음 문제의 해결에 사용된다는 점에서 2번 조건을 만족시킨다.

 

먼저, DP 없이 피보나치 수열의 점화식만을 계산하는 코드는 다음과 같다.

function fibonacciSimple(value) {
    if (value === 1 || value === 2) return 1;
    let result = fibonacciSimple(value - 1) + fibonacciSimple(value - 2);
    return result;
}

console.log(fibonacciSimple(10));	// 55

이 방식의 단점은 같은 계산이 반복적으로 수행되어야 하며 이로 인한 비효율이 초래된다는 것이다.

아래 그림을 보면, fib(2)의 결과는 항상 같지만 3번이나 반복하여 계산되어야 함을 알 수 있다.

DP를 적용해 반복 계산 과정을 단 한 번으로 최소화시키는 방법으론 top-down, bottom-up 두 가지 방법이 존재한다.

 

# Top-Down

Top-down 방식은 큰 문제를 해결하기 위한 로직이 먼저 불리고 이것을 해결하기 위해 작은 문제가 호출되는 방식이기 때문에 이런 이름을 가지고 있으며, 주로 memoization을 이용해 구현된다.

Memoization이란 이전에 계산된 결과를 일시적으로 기록해 놓는 개념으로, 아래 코드에서는 'memo'라는 이름의 Object에 계산 값을 저장하는 형태로 구현되었다.

function fibonacciTopDown(value, memo) {
    if (value === 1 || value === 2) return 1;
    if (memo[value]) return memo[value];	// 이미 계산된 값이 있으면 사용
    let result = fibonacciTopDown(value - 1, memo) + fibonacciTopDown(value - 2, memo);
    memo[value] = result;	// 계산 결과 저장
    return result; 
}

console.log(fibonacciTopDown(10, {}));	// 55

 

# Bottom-Up

Bottom-up 방식은 가장 작은 문제들을 우선적으로 호출하여 해결하고, 이를 바탕으로 큰 값을 차례대로 계산해 나가는 방식이며, tabulation 방법을 이용하여 구현된다.

Bottom-up 방식은 재귀 함수를 활용한 앞선 방법과는 다르게 반복문을 사용하게 된다.

function fibonacciBottomUp(value) {
    const table = new Array(value + 1);
    table[1] = 1;
    table[2] = 1;

    for (let i = 3; i <= value; i += 1) {
        table[i] = table[i - 1] + table[i - 2];
    }
    return table[value];
}

console.log(fibonacciBottomUp(10))	// 55

 

# Brute-force vs. Top-down vs. Bottom-up

먼저 실행 시간을 비교해보자

console.time('Brute-force');
fibonacciSimple(45);
console.timeEnd('Brute-force');

console.time('Top-down');
fibonacciTopDown(45, {});
console.timeEnd('Top-down');

console.time('Bottom-up');
fibonacciBottomUp(45);
console.timeEnd('Bottom-up');

DP를 사용하는 것이 100배 이상 빠르며, top-down보다는 bottom-up이 살짝 빠르다.

 

Input 값을 더 크게 설정하여 bottom-up이 더 빠르다는 것을 명확히 확인할 수 있다.

console.time('Top-down');
fibonacciTopDown(3000, {});
console.timeEnd('Top-down');

console.time('Bottom-up');
fibonacciBottomUp(3000);
console.timeEnd('Bottom-up');

Top-down은 재귀함수 호출에 따른 부하가 있지만, bottom-up은 단순 반복문이므로 이러한 차이가 생긴다.

 

또한, top-down 방식에서는 간혹 아래와 같은 stack overflow 메세지를 볼 수 있다.

함수는 무한히 호출될 수 없으며 호출 횟수의 한도를 가지고 있는데, 재귀 함수로 이루어진 top-down에 매우 큰 input이 들어간 경우에 이 한도에 도달하는 것이다.

 

그렇다면 DP 문제는 항상 bottom-up으로 해결하는 것이 옳은지 생각해 볼 필요가 있다.

Bottom-up 방식의 단점은 다음과 같다.

1. 재귀적이지 않으며 base case부터 거꾸로 올라가며 답을 구해야 한다. 반복문을 통해 역방향으로 문제를 해결해야 하므로 이에 맞는 해법을 고안해 내는 것에 큰 공수가 소요될 여지가 있다.
2. Base case부터 목표로 하는 값까지 모두 계산을 해내므로 원하는 답을 구하는데 불필요한 계산이 추가될 수 있다.

 

무엇이든지 장점이 있으면 단점이 있으므로 상황에 맞게 적절히 적용하는 것이 중요하다.