DP(동적계획법)

복잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결하고, 이러한 작은 문제의 해결 결과를 저장하여 재사용함으로써 전체 문제의 효율적인 해결을 가능하게 하는 알고리즘

DP 조건

1. 최적 부분 구조(Optimal Substructure): 부분 문제에 대한 최적 해결 방법으로 큰 문제의 최적 해결 방법을 구함
2. 중복되는 부분 문제(Overlapping Subproblems): 동일한 작은 문제를 저장, 재사용

DP의 구현 방법

1. 메모이제이션(Memoization): 하향식(top-down) 접근 방법, 재귀, 큰 문제를 작은 부분 문제로 나누어 해결
2. 타뷸레이션(Tabulation): 상향식(bottom-up) 접근 방법, 반복문, 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결

피보나치 수열 예시

메모이제이션

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 2) return 1;
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

타뷸레이션

function fibonacciTab(n) {
    const table = Array(n + 1).fill(0);
    table[1] = 1;
    table[2] = 1;
    for (let i = 3; i <= n; i++) {
        table[i] = table[i - 1] + table[i - 2];
    }
    return table[n];
}