🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
동적 프로그래밍 - 타뷸레이션
📍 타뷸레이션(Tabulation)
👉🏻 분할 정복을 하기 위한 하향식 계산 방식: 메모이제이션
👉🏻 함수 하나를 사용하는 것보다는 오버 헤드가 큼
👉🏻 상향식 계산으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장해 둘 것
// 구하고 싶은 수의 자릿수를 매개변수로 받음
function fibonacci1(n) {
if(n == 0 || n == 1) return n; // 기저 조건
return fibonacci1(n - 2) + fibonacci1(n - 1);
}
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);
}
return memo[n];
}
function fibonacci3(n) { // 타뷸레이션
if(n == 0 || 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(fibonacci1(110));
let end = new Date();
console.log(`fibonacci1 함수 실행 시간: ${end - start}ms`);
start = new Date();
console.log(fibonacci2(110, {}));
end = new Date();
console.log(`fibonacci2 함수 실행 시간: ${end - start}ms`);
start = new Date();
console.log(fibonacci3(110, {}));
end = new Date();
console.log(`fibonacci3 함수 실행 시간: ${end - start}ms`);
📍 메모이제이션 vs 타뷸레이션
메모이제이션 | 타뷸레이션 | |
장점 | 해결하기 힘든 문제를 하향식 접근 | 메모리 절약, 빠른 속도 |
단점 | 많은 메모리 이용 | |
재귀가 직관적일 때 사용하는 것이 좋음 | 상향식 접근이 필요할 때 사용 |