동적 프로그래밍 - 타뷸레이션

동적 프로그래밍 타뷸레이션

• 타뷸레이션(Tabulation)은 동적 프로그래밍(Dynamic Programming, DP)의 또 다른 접근 방법
• 하향식 접근 방식인 메모이제이션과 달리 상향식 접근 방식을 사용
• 즉, 작은 부분 문제부터 해결해 나가며 최종 문제를 해결하는 방식입니다.

특징

• 부분 문제의 중복: 작은 부분 문제를 먼저 해결해 이를 조합하여 큰 문제를 해결.
• 상향식 접근법: 배열이나 테이블을 사용해 작은 부분 문제부터 차례대로 해결.
• 공간 복잡도: 배열이나 테이블을 저장하기 위한 메모리가 필요.

장단점

장점	단점
명확한 순서로 문제를 해결	추가 메모리 사용
반복적 접근으로 재귀 호출 오버헤드 없음	초기 메모리 할당 및 관리 필요
일부 문제에 대해 간단하고 효율적인 솔루션 제공	DP가 적용되지 않는 문제도 존재

 

시간복잡도

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

 

자바스크립트 예시

function fibonacci(n) {
    if (n <= 1) {
        return n;
    }

    const fib = new Array(n + 1).fill(0);
    fib[1] = 1;

    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

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