DP: 동적 계획법

동적 계획법(Dynamic Programming, DP) 개념 정리

동적 계획법(DP)은 큰 문제를 작은 문제로 나누어 해결하고, 이미 해결한 작은 문제의 결과를 저장하여 중복 계산을 줄이는 최적화 기법

---

동적 계획법(DP)의 핵심 원리

1. 중복되는 부분 문제 (Overlapping Subproblems)

   • 동일한 작은 문제를 여러 번 계산해야 하는 경우
   • 예제: 피보나치 수열
     • fib(5) = fib(4) + fib(3)
     • fib(4) = fib(3) + fib(2)
     • fib(3) = fib(2) + fib(1)
     • fib(2) = fib(1) + fib(0)
     • 같은 값이 계속 중복 계산됨
     • DP를 사용하면 한 번 계산한 값은 재사용하여 불필요한 계산을 줄일 수 있음

2. 최적 부분 구조 (Optimal Substructure)

   • 문제의 최적 해가 부분 문제의 최적 해로 구성될 수 있는 경우
   • 예제: 최단 경로 문제 (Dijkstra, Floyd-Warshall)
     • A → B → C 경로의 최단 거리는 A → B와 B → C의 최단 거리의 합과 같음
     • 부분 문제의 해를 조합하여 전체 문제의 해를 구할 수 있음

---

DP를 적용하는 방법 (Bottom-Up vs Top-Down)

Bottom-Up 방식 (반복문 + 테이블 저장)

• 작은 문제부터 해결하여 차례대로 큰 문제를 해결하는 방식

• 일반적으로 배열(테이블)을 사용하여 결과를 저장하고, 반복문으로 문제를 해결

• 예제: 피보나치 수열 (반복문 DP)

  def fibonacci(n):
      dp = [0] * (n + 1)  # DP 테이블 초기화
      dp[1] = 1  # 기본 값 설정
      
      for i in range(2, n + 1):
          dp[i] = dp[i - 1] + dp[i - 2]  # 점화식 적용
      
      return dp[n]
  
  print(fibonacci(10))  # 결과: 55

• 장점: 반복문을 사용해 중복 계산을 제거하여 빠름

• 단점: DP 테이블을 저장하는 추가적인 메모리 사용

---

Top-Down 방식 (재귀 + 메모이제이션)

• 재귀(Recursion)를 사용하여 필요한 값만 계산하고, 이미 계산한 값은 저장하여 재사용하는 방식

• 메모이제이션 (Memoization): 계산한 결과를 딕셔너리나 리스트에 저장하여 중복 연산을 방지

• 예제: 피보나치 수열 (재귀 + 메모이제이션)

  def fibonacci(n, memo={}):
      if n in memo:
          return memo[n]  # 이미 계산한 값이면 바로 반환
      if n <= 1:
          return n  # 기본값 처리
      
      memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)  # 저장 후 계산
      return memo[n]
  
  print(fibonacci(10))  # 결과: 55

• 장점: 불필요한 계산을 최소화하여 빠른 속도 제공

• 단점: 재귀 호출이 많아 스택 오버플로우 위험이 있음

---

동적 계획법 vs 분할 정복

비교 항목	동적 계획법 (DP)	분할 정복
핵심 개념	작은 문제들의 결과를 저장하여 중복 계산 방지	문제를 독립적인 작은 문제로 분할
중복되는 부분 문제	있음 (Overlapping Subproblems)	없음 (각 부분 문제는 독립적)
대표 예제	피보나치, 최단 경로, 배낭 문제	병합 정렬, 퀵 정렬, 이진 탐색
적용 방식	Bottom-Up (반복문) / Top-Down (재귀+메모이제이션)	재귀를 사용하여 문제를 나눔

---

DP를 적용할 수 있는 대표적인 문제

1. 피보나치 수열 (중복 계산 제거)
2. 최단 경로 문제 (플로이드-워셜, 벨만-포드)
3. 배낭 문제 (Knapsack Problem) (조합 최적화)
4. 동전 교환 문제 (Coin Change Problem)
5. LCS(최장 공통 부분 수열)
6. 팰린드롬 분할 문제
7. 계단 오르기 문제 (1칸, 2칸씩 이동 가능할 때 총 방법 수)

---

결론

✅ 동적 계획법(DP)은 중복 계산을 줄여 연산 속도를 비약적으로 향상시키는 기법
✅ 재귀 + 메모이제이션(Top-Down) 방식과 반복문(Bottom-Up) 방식이 있음
✅ 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 저장하여 활용하는 것이 핵심 🚀