동적 프로그래밍(Dynamic Programing)

부분 문제들의 해를 결합해서 문제를 해결하는 방법. 분할 정복과 유사해보이나, 재귀적으로 부분문제를 해결할 때, 반복되어 사용될 문제의 해는 저장해서 다른 계산에 꺼내쓴다.

특징

1. 중복되는 하위 문제 (Overlapping Subproblems)
   • 동일한 하위 문제가 여러번 반복 계산
   • ex) Fibo : $F(n) = F(n-1) + F(n-2)$ 에서 $F(n-1)$과 $F(n-2)$가 반복 계산
2. 최적 부분 구조 (Optimal Substructure)
   • 문제의 최적해가 그 부분 문제의 최적해를 포함하고 있을 때 그 문제는 최적 부분 구조를 가짐

구현 방식

상향식 (Bottom-up, Tabulation) :

• 문제의 가장 작은 하위 문제부터 차례로 계산, 그 결과를 테이블에 저장 후 점차 큰 문제로 확장
• 반복문(loop)을 주로 사용하며, 메모이제이션과 달리 재귀 호출 없이 테이블을 채움
• 예시 : 피보나치 수열을 반복문으로 계산

하향식 (Top-down, Memoization) :

• 큰 문제를 재귀적으로 해결, 중간에 계산된 하위 문제의 결과를 메모리에 저장하여 다시 계산하지 않도록 함
• 재귀 호추로가 저장(메모이제이션)을 통해 문제 해결
• 예시 : 재귀적으로 피보나치 수열을 계산하면서 이미 계산한 값을 캐시에 저장하는 방법

예제를 통한 실습 (피보나치 수열)

# 기본 재귀
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

재귀 깊이가 매우 깊어질 수 있음

1. Top-down : 재귀 + 메모이제이션 방식
   • 하위 문제를 필요할때마다 재귀적으로 호출
   • 이미 계산된 값은 저장해서 중복 방지

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

1. Bottom-up : 반복문 + DP table
   • 하위 문제를 작은 문제부터 차례대로 해결
   • 결과는 테이블이나 배열에 저장

def fib(n):
    dp = [0, 1] + [0] * (n-1)
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

풀 수 있는 문제들

공통 특징

• 하위 문제의 중복 : 동일한 계산이 반복됨
• 문제 분할이 가능함 : 더 작은 단위로 나눌 수 있음
• 최적해의 결합 : 작은 문제의 최적해로 전체 문제의 최적해를 구성할 수 있음

대표적인 문제

• 피보나치 수열 : 중복 계산이 많아, 메모이제이션 또는 테이블 방식으로 효율적 계산 가능
• 베낭 문제 (Knapsack Problem) : 각 물건의 가치와 무게를 고려해 최적의 가치 합을 구함
• 최장 공통 부분 수열 (LCS, Longest Common Subsequence) : 두 문자열에서 공통 부분 수열 중 최대 길이를 구함
• 최소 편집 거리 (Edit Distance) : 두 문자열을 동일하게 만들기 위한 최소 편집 횟수를 구함
• 최단 경로 문제 : 그래프 내에서 특정 노드 혹은 모든 노드 쌍 간 최단 경로를 찾음

| **유형** | **예시 문제** | **설명** |
| --- | --- | --- |
| 피보나치 | n번째 수 구하기 | 전통의 맛 |
| 계단 오르기 | 한 번에 1칸/2칸, n칸까지 | 방법 수 세기 |
| 동전 교환 | 가장 적은 동전으로 금액 만들기 | 최솟값 문제 |
| 배낭 문제 | 무게 제한 내 최대 가치 | 대표적인 DP |
| 문자열 유사도 | 최장 공통 부분 수열(LCS) | 두 개의 문자열 비교 |
| 게임 최적 전략 | A와 B가 번갈아 고르며 최대 점수 | 그리디로 안 됨 |