동적 프로그래밍이란?
복잡한 문제를 간단한 여러 개의 부분 문제로 나누어 해결하는 방법이다. 특히, 이 방법은 부분 문제의 해결 결과를 저장해 두고(메모이제이션 또는 타뷸레이션을 통해), 그것을 활용하여 같은 문제를 반복하여 해결하는 것을 방지하므로 계산 효율성이 향상된다. 동적 프로그래밍은 최적화 문제를 효과적으로 해결할 때 주로 사용한다.
동적 프로그래밍의 구현 방식
- 탑다운 (Top-down)
재귀적 방법으로 큰 문제를 작은 문제로 나누면서 해결한다. 메모이제이션을 사용하여 중복 계산을 방지한다. - 바텀업 (Bottom-up)
작은 문제부터 시작하여 큰 문제로 나아가면서 해결책을 구축한다. 타뷸레이션 방식으로 테이블에 결과를 저장한다.
메모이제이션 (Memoization)
메모이제이션은 프로그래밍에서 사용되는 최적화 기법 중 하나이다. 이 기법은 높은 비용의 연산 결과를 메모리에 저장해두었다가, 동일한 입력에 대한 연산을 반복해야 할 때 이전에 계산된 결과를 재활용 하는 방식으로 동작한다.
메모이제이션의 핵심 개념
- 저장 : 함수의 결과를 특정 자료 구조에 저장한다.
- 확인 : 함수를 호출하기 전에 해당입력에 대한 결과가 이미 저장되어 있는지 반환한다.
- 재활용 : 저장된 결과가 있다면, 다시 계산하지 않고 저장된 값을 반환한다.
메모이제이션 기법을 활용한 구현 사례
function fibonacci(n) {
if(n == 0 || n == 1) return n;
return fibonacci(n - 2) + fibonacci(n - 1);
}
위의 예제는 재귀만 사용하여 피보나치 수열을 계산할 경우이다.
이미지처럼 같은 분 문제를 여러 번 계산하게 된다. 더 큰 수에서는 이런 중복 계산이 늘어나게 된다. 또한 중복 계산 때문에, n이 커질수록 계산 시간이 지수적으로 늘어나게 된다.
function fibonacci(n, memo) {
if(n == 0 || n == 1) return n;
if(memo[n] == null) {
memo[n] = fibonacci(n - 2, memo) + fibonacci(n - 1, memo);
}
}위의 문제를 해결하기 위해 메모이제이션 기법을 활용하면 중복 계산을 제거할 수 있다. 메모이제이션은 이미 계산된 부분 문제의 결과를 저장하므로, 같은 부분 문제를 다시 계산할 필요가 없다.
메모이제이션은 재귀적인 방법으로 어려운 문제를 단순히 풀 수 있고, 계산 결과를 저장하고 재사용하기 때문에 속도가 빠르다. 하지만 메모이제이션도 결국 함수를 여러 번 호출하는 재귀를 사용하기 때문에 함수 하나를 호출하는 것 보다 오버헤드가 더 클 수 밖에 없다.
타뷸레이션(Tabulation)
동적 프로그래밍에서 사용되는 방법으로, 문제를 부분 문제로 나눈 다음 작은 문제부터 차례대로 그 결과를 테이블에 저장하는 방식을 말한다. 이렇게 저장된 테이블을 기반으로 큰 문제의 해결을 단계적으로 구축한다.
타뷸레이션은 상향식 계산 방식으로 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장한다. 그리고 이렇게 계산되어 저장된 값을 필요할 때 사용해 빠르게 계산한다.
타뷸레이션 기법을 활용한 구현 사례
function fibonacci(n) {
if(n <= 1) return n;
let table = [0, 1];
for(let i = 2; i <= n; i ++) {
table[i] = table[i - 2] + table[i - 1];
}
return table[n];
}메모이제이션과 타뷸레이션의 비교
메모이제이션을 통한 피보나치 함수는 여러 번의 함수 호출로 메모리 공간의 스택을 차지하고 메모이제이션을 위한 공간까지 차지하기 때문에 메모리를 더 많이 사용한다. 반면 타뷸레이션을 통한 피보나치 함수는 적은 메모리 사용인데도 불구하고 빠른 시간을 보인다.
그럼 동적 프로그래밍이 필요한 분할 정복 문제를 풀 때 메모이제이션과 타뷸레이션 중 어떤 것이 더 좋은 접근 방식일까?
메모이제이션의 장점은 재귀를 이용해 문제를 하향식으로 해결하여 복잡한 문제를 쉽게 해결할 수 있는 장점이 있다. 재귀만 이용한다면 중복 계산을 하기 때문에 성능에 문제가 발생하는데, 계산 결과를 저장하는 방식으로 단점을 해결했다.
그렇기 때문에 분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리하다. 하지만 재귀가 직관적이지 않은 문제라면, 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 해결할 수 있다.
