10. 메모이제이션 과 타뷸레이션

메모이제이션 (직관적일 때 사용)

재귀함수를 이용하여 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있다.

계산 결과를 해시 테이블에 저장하고 재사용 하기 때문에 속도가 빠르지만 메모리를 사용한다.

중복 계산을 하지 않아 속도가 빠름

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(`fibonacci2 함수 실행 시간 : ${end - start}ms`);

동적 프로그래밍 타뷸레이션 (직관적이지 않을 때 사용)

상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장

저장된 값을 필요할 때 사용하여 빠르게 계산한다.

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];
}

start = new Date();
console.log(fibonacci3(40));
end = new Date();
console.log(`fibonacci3 함수 실행 시간 : ${end - start}ms`);