목차
동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 작은 문제를 해결한 결과를 저장하여 큰 문제를 해결할 때 사용하는 문제 해결 패러다임이다.
일반적으로 재귀 함수의 불필요한 연산을 줄이기 위해서 동적 계획법을 사용한다.
재귀 함수도 이전의 결과값을 활용해서 다음 결과를 계산한다는 점에서 동적 계획법과 비슷하다. 하지만, 재귀 함수는 결과를 구한 동일한 문제에 대해 다시 계산을 하는 문제점이 있다.
대표적인 사례로 피보나치 수열이 있다. 피보나치 수열은 1번째 수는 0, 2번째 수는 1로 정의하고, 3번째 수 부터는 바로 앞의 두 수를 더한 값을 저장하는 것이다.
0, 1, 1, 2, 3, 5, 8, 13, ...
이를 재귀 함수로 구현하면 다음과 같다.
const fibo = (n) => {
if (n <= 1) // 1번째 수와 2번째 수에 도달했을 때, 각각 0과 1을 반환
return n;
return fibo(n - 1) + fibo(n - 2);
}
n = 4 라고 했을 때, $fibo(4) = fibo(3) + fibo(2)$ 이다.
이때, $fibo(3) = fibo(2) + fibo(1)$ 이다. 하지만, $fibo(2)$ 의 결과는 $fibo(3)$ 구할 때와 $fibo(4)$ 를 구할 때 모두 필요한데, 결과값을 따로 저장하지 않아서 매번 계산을 다시 해주어야 한다. 이를 그림으로 표현하면 다음과 같다.
즉, 재귀 함수로 구현하면 동일한 값을 2번씩 구하게 되며, 시간 복잡도는 $O(2^n)$ (f(4) = f(3) + f(2) + f(1) + f(0) + f(2) + f(1) + f(1)) 이 된다. 그래서 n 의 값이 커질 수록 연산이 기하급수 적으로 증가하는 문제가 생긴다.
이러한 재귀 함수의 문제 때문에 이미 계산을 마친 결과에 대해서는 값을 저장해놓고, 그 값을 다시 활용하여 연산을 줄이는 동적 계획법이 등장하게 되었다.
동적 계획법은 크게 2가지 방식으로 구현할 수 있다.