동적 프로그래밍 - 메모이제이션

동적 프로그래밍 메모이제이션

• 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누어 해결하는 방법.
• 메모이제이션(Memoization)은 이미 계산한 결과를 저장해두고, 동일한 계산을 반복하지 않도록 하는 기술.

특징

• 부분 문제의 중복: DP는 동일한 부분 문제를 여러 번 계산하는데, 메모이제이션을 통해 이를 방지합니다.
• 탑다운 접근법: 재귀적으로 문제를 해결하면서, 이미 계산한 결과를 저장.
• 공간 복잡도: 결과를 저장하기 위한 추가 메모리가 필요.

장단점

장점	단점
중복 계산 방지로 성능 향상	추가 메모리 사용
재귀적 접근으로 코드 가독성 향상	초기 메모리 할당 및 관리 필요
일부 문제에 대해 간단하고 효율적인 솔루션 제공	DP가 적용되지 않는 문제도 존재

 

시간복잡도

알고리즘 종류	시간 복잡도
피보나치 수열 (재귀)	O(2^n)
피보나치 수열 (메모이제이션)	O(n)
최장 공통 부분 수열	O(m * n)
배낭 문제	O(n * W)

 

자바스크립트 예시

function memoize(fn) {
    const cache = {};
    return function(...args) {
        const n = args[0];
        if (n in cache) {
            return cache[n];
        } else {
            const result = fn(n);
            cache[n] = result;
            return result;
        }
    };
}

function fibonacci(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

const memoizedFibonacci = memoize(fibonacci);

console.log(memoizedFibonacci(10)); // 55
console.log(memoizedFibonacci(20)); // 6765
console.log(memoizedFibonacci(30)); // 832040