[Algorithm] 동적계획법 Dynamic Programming

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 복잡한 문제를 작은 하위 문제로 나누고, 그 하위 문제의 결과를 저장하여 중복 계산을 피하는 프로그래밍 기법입니다. 최적화 문제에서 자주 사용되며, 문제를 푸는 데 중요한 패러다임 중 하나입니다.

다이나믹 프로그래밍 원리

1. 분할 정복 (Divide and Conquer): 문제를 더 작은 하위 문제로 나눕니다.
2. 중복 하위 문제 (Overlapping Subproblems): 하위 문제의 결과를 재활용합니다.
3. 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적해가 하위 문제의 최적해로 구성됩니다.
4. 메모이제이션(Memoization) 또는 테뷸레이션(Tabulation):

• 메모이제이션: 재귀적으로 문제를 해결하며, 이미 계산된 값을 저장하여 재사용.
• 테뷸레이션: 반복문을 사용해 작은 문제부터 해결하며, 값을 저장.

다이나믹 프로그래밍 구현

function fibTabulation(n) {
    if (n <= 1) return n;

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

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

    return dp[n];
}

console.log(fibTabulation(10)); // 55
console.log(fibTabulation(50)); // 12586269025

장점과 단점

장점

• 중복 계산을 줄이기 때문에 계산 속도가 빠릅니다.
• 문제를 구조적으로 해결할 수 있습니다.
• 최적화 문제에서 효과적으로 사용됩니다.

단점

• 추가 메모리 공간을 사용해야 합니다(특히 테뷸레이션 방식에서).
• 문제의 구조가 적합하지 않다면 적용이 어렵습니다.
• 구현 과정이 복잡할 수 있습니다.