동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누고, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 기법입니다. 복잡한 문제를 효율적으로 해결할 수 있으며, 특히 최적화 문제에서 자주 사용됩니다.

그 반대로 정적 프로그래밍(Static Programming)은 프로그램의 실행 흐름과 변수 타입 등이 컴파일 시점에 결정되고, 실행 중에는 변경되지 않는 프로그래밍 방식입니다.

⇒ 동적 프로그래밍은 실행 중에 유연하게 바뀔 수 있는 방식

🌟 동적 계획법의 핵심 개념

• 분할 정복과의 차이점 분할 정복은 문제를 독립적인 하위 문제로 나누지만, DP는 하위 문제들이 서로 겹칠 때 그 결과를 저장하여 재사용합니다.

• 메모이제이션(Memoization) : 한 번 계산한 함수의 결과를 저장해 두었다가, 같은 입력이 다시 들어오면 재계산하지 않고 저장된 값을 반환하는 최적화 기법

• ⇒ DFS/BFS의 visited 와 DP의 메모이제이션은 다르다!

  • Top-down 방식: 재귀 호출을 통해 큰 문제를 작은 문제로 나누고, 이미 계산한 결과를 저장하여 다시 쓰는 방식.

  // 피보나치 수열을 Top-down 방식으로 구현
  function fibonacciMemo(n, memo = {}) {
      // 이미 계산된 값이 있으면 바로 반환
      if (memo[n]) return memo[n];
  
      // 기본 조건
      if (n <= 1) return n;
  
      // 재귀 호출하면서 결과를 저장
      memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
      return memo[n];
  }
  
  // 예시 실행
  console.log(fibonacciMemo(10)); // 55
  

• 탭(Tabulation)

  • Bottom-up 방식: 작은 문제부터 차례대로 계산해 테이블에 저장하고, 이를 이용해 큰 문제를 해결하는 방식.

  // 피보나치 수열을 Bottom-up 방식으로 구현
  function fibonacciTab(n) {
      // DP 테이블 초기화
      const dp = [0, 1];
  
      // 작은 문제부터 차례대로 계산
      for (let i = 2; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2];
      }
  
      return dp[n];
  }
  
  // 예시 실행
  console.log(fibonacciTab(10)); // 55
  

📌 DP의 특징

• 중복 계산 방지: 동일한 하위 문제를 여러 번 풀지 않고, 한 번 계산한 값을 저장해 활용.
• 시간 효율성 증가: 메모리를 조금 더 사용하지만, 연산 속도를 크게 향상시킴.
• 최적화 문제에 강력: 예를 들어 최단 경로, 최대/최소 비용, 최대 이익 문제 등에서 자주 쓰임.

🧩 대표적인 예시

• 피보나치 수열
  • 단순 재귀: (F(n) = F(n-1) + F(n-2)) → 중복 계산 많음
  • DP 적용: 이미 계산한 값을 저장하여 (O(n)) 시간에 해결 가능
• 최단 경로 문제 (예: 다익스트라, 플로이드-워셜 알고리즘)
• 배낭 문제(Knapsack Problem)
  • 제한된 자원으로 최대 가치를 얻는 문제 → DP로 효율적 해결
• LCS(Longest Common Subsequence)
  • 두 문자열에서 가장 긴 공통 부분 수열 찾기