💾 동적계획법 (Dynamic Programming, DP)

동적계획법(DP) 은
👉 “모든 경우를 다 해보면 너무 느릴 때” 사용하는 방법입니다.

이미 계산한 결과를 다시 사용할 때 유용

1️⃣ 핵심 개념

"큰 문제를 작은 문제로 나누고, 결과를 재활용한다"

DP의 핵심은 속도를 줄이는 방식이 아니라
👉 중복 계산 자체를 없애는 것입니다.

같은 입력, 같은 상태라면 결과도 항상 같기 때문에
한 번 계산한 값은 저장해 두고 재사용합니다.

이를 통해 시간 복잡도를 획기적으로 줄일 수 있습니다.

2️⃣ 적용 조건

동적계획법은 “비슷한 계산을 여러 번 해야 하는 문제” 에서 특히 유용합니다.

👉 이 두 가지 조건이 모두 맞을 때,
동적계획법(DP) 으로 문제를 훨씬 효율적으로 풀 수 있습니다.

3️⃣ 예시: 배낭 문제 (Knapsack Problem)

문제
무게 제한이 있는 배낭에 물건을 넣을 때,
총 가치가 최대가 되도록 어떤 물건을 선택해야 할까?

🧠 아이디어

이 문제를 완전탐색으로 풀면
👉 “이 물건을 넣을까 말까” 를 전부 시도해야 합니다.

대신 이렇게 생각합니다.

"앞에서부터 물건을 하나씩 보면서 지금 무게 제한 안에서 얻을 수 있는 최대 가치는?"

이 질문에 대한 답을 표로 저장해 나가는 것이 DP입니다.

📌 DP 배열의 의미

dp[i][w] = 
i번째 물건까지 고려했을 때,
배낭 무게가 w일 경우 얻을 수 있는 최대 가치

• i : 어디까지 물건을 봤는지
• w : 현재 사용한 무게
• 값 : 그 상태에서의 최적의 가치

⚙️ Bottom-Up 방식

function knapsack(weights, values, maxWeight) {
    const n = weights.length;

    // dp[i][w]의 의미:
    // i번째 물건까지 봤을 때, 무게 w로 얻을 수 있는 최대 가치
    const dp = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= maxWeight; w++) {

            // 현재 물건을 넣을 수 있는 경우
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i - 1][w], // 현재 물건을 안 넣는 경우
                    dp[i - 1][w - weights[i - 1]] + values[i - 1] // 넣는 경우 (이전 무게를 빼고 넣음)
                );
            } 
            // 무게 초과로 넣을 수 없는 경우 
            else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][maxWeight];
}

const weights = [2, 3, 4];
const values = [3, 4, 5];
const maxWeight = 5;

console.log(knapsack(weights, values, maxWeight)); // ✅ 출력: 7

📊 DP 테이블 개념 (시각적으로 보면)

• 각 칸은 "이 상태에서의 최선"
• 한 번 채워진 값은 다시 계산하지 않음

✅ 결과: 최대 가치 = 7 (1번, 2번 물건을 넣으면 무게 5, 가치 7)

🔑 한 줄 정리

DP는 “선택의 결과를 저장하면서, 같은 상태를 다시 계산하지 않는 방법”