동적 프로그래밍(Dynamic Programming)
: 큰 문제를 작은 문제로 나누고, 그 결과를 저장하여 중복 계산을 피하는 최적화 기법
메모이제이션 (Memoization)
: 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법
- 하향식(Top-Down) 방식
- 재귀를 사용해 큰 문제부터 내려가며 계산
- 이미 계산한 결과는 저장해두고 다시 사용함
메모이제이션의 장단점
장점
- 재귀 덕분에 하향식 계산 방식으로 어려운 문제를 간단히 해결할 수 있음
- 중복 계산을 하지 않아서 속도가 빠름
단점
- 재귀를 사용하기 때문에 오버헤드가 큼
- 메모이제이션은 속도를 위해 메모리를 사용하기 때문에 메모리 사용량 증가
예시: 피보나치 수열
기본 재귀 방식
function fibonacci1(n){
if(n == 0 || n == 1) return n;
return fibonacci1(n - 2) + fibonacci1(n - 1);
}
- fibonacci1(5)를 호출하면 다음과 같이 함수가 계속 호출됨
- fibonacci1(3)이나 fibonacci1(2)처럼 같은 값을 여러 번 계산하게 됨
- 이렇게 중복 호출이 많아지면 숫자가 클수록 계산 시간이 급격히 증가함
fibonacci1(5)
= fibonacci1(4) + fibonacci1(3)
= (fibonacci1(3) + fibonacci1(2)) + (fibonacci1(2) + fibonacci1(1))
= ...
- 40번째 피보나치 수를 계산하는 데 시간이 오래 걸림
let start = new Date();
console.log(fibonacci1(40)); // 102334155
let end = new Date();
console.log(`fibonacci1 함수 실행시간: ${end - start}ms`); // 871ms
예시: 피보나치 수열을 메모이제이션을 사용해서 구현하기
메모이제이션을 사용한 방식
- 계산하려는 데이터가 있는지 검색하고, 없다면 함수를 호출해 계산하고 그 계산을 저장하면 됨
⇒ 해시 테이블(= 객체) 사용 - memo는 이전에 계산한 값을 저장하는 객체
- 특정 숫자의 피보나치 값을 이미 계산했으면 다시 계산하지 않고 저장된 값을 바로 사용함
- 같은 값은 최대 한 번만 계산하므로 중복 계산이 사라짐
function fibonacci2(n, memo){
if(n == 0 || n == 1) return n;
if(memo[n] == null){ // 객체에 해당 값의 계산 결과가 없다면
memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); // 계산을 하고 결과를 저장함
}
// memo 객체에 n의 계산 결과가 들어있음
return memo[n];
}
- 같은 문제를 훨씬 더 빠르게 해결할 수 있음
let start = new Date();
console.log(fibonacci2(40, {})); // 102334155
let end = new Date();
console.log(`fibonacci2 함수 실행시간: ${end - start}ms`); // 0ms
타뷸레이션 (Tabulation)
: 작은 문제부터 차례로 계산해 테이블에 값을 채워나가는 상향식 방식
- 상향식(Bottom-Up) 방식
- 작은 문제부터 차례대로 테이블에 저장하며 계산
- 계산에 필요하지 않을 수도 있는 값을 미리 계산해 테이블에 저장함
→ 이렇게 저장된 값을 필요할 때 사용해 빠르게 계산함
타뷸레이션의 장단점
장점
- 재귀 사용 X → 오버헤드 없음 X
- 일반적으로 속도 더 빠름
- 메모리 절약 가능
단점
- 테이블에 모든 값을 계산해 저장하므로, 불필요한 계산이 있을 수 있음
예시: 피보나치 수열 타뷸레이션(상향식)으로 계산하기
타뷸레이션(상향식) 방식
- table 배열은 각 피보나치 수를 저장하는 테이블
- fibonacci3(5)를 호출하면 먼저 table[0] = 0, table[1] = 1로 초기화된 후, 반복문을 통해 table[2], table[3], ..., table[5]까지 차례로 계산됨
- 이렇게 하면 앞에서부터 차근차근 계산하면서 한 번만 계산하므로 중복이 없음
function fibonacci3(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];
}
- 계산을 반복문으로 처리하기 때문에 매우 빠름
let start = new Date();
console.log(fibonacci3(40)); // 102334155
let end = new Date();
console.log(`fibonacci3 함수 실행시간: ${end - start}ms`); // 0ms
메모이제이션 vs 타뷸레이션
| 항목 | 메모이제이션 | 타뷸레이션 |
| 방식 | 하향식 (Top-Down) | 상향식 (Bottom-Up) |
| 구현 방식 | 재귀 + 저장 | 반복문 + 테이블 |
| 직관성 | 복잡한 문제에 적합 | 단순한 계산에 적합 |
| 속도 | 빠름 (하지만 느릴 수도 있음) | 더 빠름 (재귀 X) |
| 메모리 사용 | 더 많이 사용될 수 있음 | 상대적으로 적게 사용함 |
동적 프로그래밍이 필요한 분할 정복 문제를 풀 때, 어떤 것을 사용하는게 좋을까?
메모이제이션
- 하향식(Top-down) 방식: 큰 문제를 작게 나눠서 재귀 호출로 해결함
- 재귀 기반: 함수가 자기 자신을 호출하며 결과를 저장해 중복 계산을 피함
- 복잡한 문제를 직관적이고 간단한 코드로 구현 가능
- 함수 호출 스택을 많이 사용하기 때문에 메모리 사용량이 더 많고, 오버헤드가 발생할 수 있음
👉 추천 상황
- 문제를 재귀적으로 푸는 게 더 자연스럽고 이해하기 쉬운 경우
- 복잡한 문제의 구조를 하향식으로 쪼개기 쉬운 경우
타뷸레이션
- 상향식(Bottom-up) 방식: 작은 문제부터 차례로 풀어 나가며 테이블에 값을 저장함
- 반복문 기반: 재귀 없이 배열이나 테이블을 사용해 효율적으로 계산
- 메모리 사용을 줄이고, 함수 호출 오버헤드가 없음
- 다소 덜 직관적일 수 있지만 성능이 더 좋을 수 있음
👉 추천 상황
- 문제를 반복적으로 풀기 쉬운 구조인 경우
- 속도와 메모리 효율성이 중요한 경우
- 재귀 호출보다 반복문이 더 직관적일 때 (재귀가 직관적이지 않을 때)