🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
동적 프로그래밍 - 메모이제이션
📍 메모이제이션의 필요성
👉🏻 재귀를 이용해 큰 문제를 작은 문제로 분할 정복을 이용하여 풀어 왔음
👉🏻 하지만 재귀를 사용하면 스택에 함수를 쌓는 단점 이외에도 이미 계산한 것을 또 계산하게 되는 치명적인 단점이 있음
// 피보나치 수열
// 앞의 두 수를 더한 수를 뒤에 나열
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
[ fibonacci.mjs ]
// 구하고 싶은 수의 자릿수를 매개변수로 받음
function fibonacci(n) {
if(n == 0 || n == 1) return n; // 기저 조건
return fibonacci(n - 2) + fibonacci(n - 1);
}
console.log(fibonacci(5));
👉🏻 같은 계산을 너무 많이 함!
📍 중복 계산을 줄이는 방법?
👉🏻 계산 결과를 저장하고 같은 계산이 필요할 때 저장된 계산을 사용함
👉🏻 성능 향상과 함수 호출을 줄이는 효과
📍 메모이제이션(Memoization)
👉🏻 계산 결과를 저장해서 여러 번 계산되지 않도록 하는 기법
👉🏻 데이터 삽입, 삭제가 빠른 해시 테이블을 사용! (자바 스크립트의 객체도 해시 테이블이므로 그것을 사용할 것)
// 구하고 싶은 수의 자릿수를 매개변수로 받음
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];
}
let start = new Date();
console.log(fibonacci1(40));
let end = new Date();
console.log(`fibonacci1 함수 실행 시간: ${end - start}ms`);
start = new Date();
console.log(fibonacci2(40, {}));
end = new Date();
console.log(`fibonacci1 함수 실행 시간: ${end - start}ms`);
👉🏻 엄청난 속도 향상 효과가 있으나 메모리를 많이 쓴다는 단점도 존재하기는 함!
👉🏻 fibonacci1의 성능은 O(n^2), fibonacci2의 성능은 O(n)임!