동적 계획법(DP, Dynamic Programming)

동적 계획법 DP

"복잡한 문제를 작은 부분 문제로 나누어 해결하고, 중복 계산을 줄여 효율적으로 최적해를 찾는 알고리즘 기법"

• 한 번 계산한 값을 저장(Memoization)하여 중복 계산 방지
• 부분 문제를 조합하여 전체 문제의 해답을 구하는 방식
• 피보나치수열, 최단 경로, 배낭 문제 등 다양한 문제에서 활용

---

동적 계획법(DP) 동작 원리

1. 문제를 작은 부분 문제(Subproblem)로 나눔
2. 각 부분 문제를 해결하면서 결과를 저장(Memoization or Tabulation)
3. 저장된 결과를 이용하여 최종 문제를 해결

# Pseudo Code_Top-Down
FUNCTION Fibonacci(n):
    IF n <= 1 THEN RETURN n
    IF memo[n] IS NOT EMPTY THEN RETURN memo[n]
    
    memo[n] = Fibonacci(n-1) + Fibonacci(n-2)
    RETURN memo[n]


# Pseudo Code_Bottom-Up
FUNCTION Fibonacci(n):
    dp[0] = 0, dp[1] = 1
    
    FOR i FROM 2 TO n DO:
        dp[i] = dp[i-1] + dp[i-2]
    
    RETURN dp[n]


# Full Code_Top-Down
def fibonacci_top_down(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:  # 저장된 값이 없으면 계산
        memo[n] = fibonacci_top_down(n-1, memo) + fibonacci_top_down(n-2, memo)
    return memo[n]

print(fibonacci_top_down(10))  # 55


# Full Code_Bottom-Up
def fibonacci_bottom_up(n):
    dp = [0] * (n+1)
    dp[1] = 1  # 초기값 설정
    
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]  # 이전 결과를 활용
    
    return dp[n]

print(fibonacci_bottom_up(10))  # 55

---

동적 계획법(DP)의 일반적인 시간복잡도

• 탑다운(Top-Down) 방식: O(부분 문제 개수 × 각 문제 풀이 시간)
• 바텀업(Bottom-Up) 방식: O(상태 개수 × 상태 전이 시간)

✅ 대부분의 DP 문제는 O(n) 또는 O(n²), 일부는 O(n³)까지 가능
✅ 일반적으로 탑다운과 바텀업 방식의 시간복잡도는 동일

---

동적 계획법(DP) 활용 예시

문제 유형	예제 문제
피보나치 수열	피보나치 수 구하기 (Top-Down, Bottom-Up)
최단 경로 문제	플로이드-워셜 알고리즘
배낭 문제(Knapsack Problem)	물건을 가방에 최적으로 넣는 문제
LCS (최장 공통 부분 수열)	문자열 비교 최적해 찾기
동전 거스름돈 문제	최소 동전 개수로 거스름돈 주기

---

동적 계획법(DP)의 장단점

장점

• 중복 계산을 줄여 실행 속도를 획기적으로 개선 가능
• 최적 부분 구조가 있는 문제에서 최적해를 보장함

단점

• 모든 문제에 적용할 수 없음 (DP가 적용되려면 "중복되는 하위 문제"와 "최적 부분 구조" 필요)
• 추가적인 메모리(배열, 딕셔너리)를 사용해야 할 수도 있음

결론

DP는 복잡한 최적화 문제를 해결하는 강력한 도구 하지만 적절한 조건(중복 계산 & 최적 부분 구조)이 충족될 때만 효과적이다.