동적 계획법 (DP) 개념

🚀 동적 계획법(DP)이란?

동적 계획법(Dynamic Programming, DP)은 반복 계산을 줄여 성능을 향상시키는 알고리즘 기법입니다.

✔️ 작은 문제를 해결하고 결과를 저장해 불필요한 계산을 방지!
✔️ 피보나치 수열, 배낭 문제, 최단 경로 문제 등에 활용 가능!
✔️ 재귀(메모이제이션)와 반복문(타뷸레이션) 방식으로 구현할 수 있음!

---

💡 DP의 핵심 개념

🔥 왜 DP가 필요할까?

프로그래밍을 하다 보면 같은 계산을 반복하는 비효율적인 코드로 인해 성능이 저하되는 경우가 많아요. 예를 들어, 피보나치 수열을 단순 재귀로 구현하면 중복 연산이 많아져 실행 속도가 느려질 수밖에 없죠. 😵

이럴 때 필요한 게 바로 동적 계획법(DP)!
DP를 사용하면 중복 계산을 최소화하고 실행 속도를 최적화할 수 있어요. 🎯

🏗️ DP가 적용되는 조건

1. 중복되는 부분 문제(Overlapping Subproblems)
   • 큰 문제를 해결하는 과정에서 같은 작은 문제를 반복해서 해결해야 함.
2. 최적 부분 구조(Optimal Substructure)
   • 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있어야 함.

이 두 가지를 만족하면 DP를 적용할 수 있어요! ✅

---

⚡ DP의 구현 방식

📌 1. 메모이제이션 (탑다운 방식)

✔️ 재귀 함수를 사용해 문제를 해결!
✔️ 계산한 값을 저장하여 중복 연산 방지!
✔️ 필요할 때만 계산하여 불필요한 연산 최소화!

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

📌 2. 타뷸레이션 (바텀업 방식)

✔️ 반복문을 사용해 작은 문제부터 해결!
✔️ 모든 경우를 미리 계산하여 실행 속도 향상!
✔️ 재귀를 사용하지 않아 스택 오버플로우 방지!

function fib(n) {
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

---

🏆 DP가 활용되는 문제

1️⃣ 피보나치 수열

📌 단순 재귀 → O(2^n) (비효율적 😰)
📌 DP 적용 → O(n) (빠름 🚀)

2️⃣ 배낭 문제 (0-1 Knapsack Problem)

✔️ 가방에 최대 무게 제한이 있을 때, 최대한 높은 가치를 얻는 방법을 찾는 문제
✔️ DP를 활용하면 O(nW)의 시간 복잡도로 해결 가능!

3️⃣ 최단 경로 문제

✔️ 플로이드-워셜 알고리즘 같은 그래프 문제에서도 DP를 활용 가능!
✔️ 최단 거리 계산을 효율적으로 수행할 수 있음!

---

🤔 DP에 대한 오해와 진실

❌ DP는 특정한 알고리즘이다? → DP는 패러다임이지, 특정한 알고리즘이 아님!
❌ 모든 문제에 DP를 적용할 수 있다? → 중복 부분 문제와 최적 부분 구조를 만족해야 적용 가능!

---

📢 DP의 장단점

✅ 장점

• 중복 계산을 줄여 실행 속도 최적화
• 문제를 체계적으로 해결할 수 있음

❌ 단점

• 추가적인 메모리 사용이 필요할 수 있음
• 모든 문제에 적용 가능한 것은 아님

---

🎯 결론

DP는 불필요한 연산을 줄여 성능을 극대화하는 강력한 기법입니다. 하지만 적용할 수 있는 문제인지 판단하는 것이 중요합니다!