동적 계획법(Dynamic Programming, DP)

개요

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 중복된 하위 문제로 나누고, 이들을 한 번만 계산하여 결과를 저장해 재사용함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 전략이다. 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack), 경로 탐색 등 다양한 최적화 문제에 활용되며, **탑다운(메모이제이션)**과 바텀업(테이블화) 방식이 있다.

---

1. 핵심 개념 및 정의

동적 계획법의 핵심은 다음 두 가지 조건을 만족하는 문제에서 적용 가능하다:

• 중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 반복적으로 등장함
• 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 하위 문제의 최적해로 구성됨

---

2. 구현 방식

방식	설명	장점
탑다운 (Top-down)	재귀 + 메모이제이션 (cache 저장)	직관적, 구현 쉬움
바텀업 (Bottom-up)	작은 문제부터 테이블에 누적 계산	반복 기반, 스택오버플로 방지

---

3. 대표 문제 예시

문제	설명	시간 복잡도
피보나치 수열	n번째 수는 n-1과 n-2의 합	O(n) (DP 적용 시)
0-1 배낭 문제	무게 제한 내에서 최대 가치 선택	O(nW) (n: 물건 수, W: 무게 한도)
최장 공통 부분 수열 (LCS)	두 문자열의 공통된 부분 문자열 중 최장 길이	O(n×m)
최소 동전 교환	최소 개수의 동전으로 목표 금액 만들기	O(n×k) (n: 동전 수, k: 금액)
계단 오르기	1칸 또는 2칸씩 올라 목표 층 도달	O(n)

---

4. 파이썬 예시 (피보나치 수열)

Top-down (메모이제이션)

memo = {}

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

print(fib(10))  # 출력: 55

Bottom-up (반복)

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]

print(fib(10))  # 출력: 55

---

5. 시간 및 공간 복잡도

항목	평균 복잡도
시간 복잡도	O(n), O(n×m), O(n×W) 등 문제 유형별 상이
공간 복잡도	O(n) 이상 (테이블, 캐시 사용)

공간 최적화: 일부 문제는 O(1) 공간으로도 최적화 가능 (ex. 피보나치 → 변수 2개만 사용)

---

6. 특징 및 장단점

항목	장점	단점
중복 계산 제거	불필요한 연산 최소화 → 속도 향상	메모리 사용 증가 가능
최적화 문제 강함	경로 탐색, 조합 문제에 강력	점화식 설계 난이도 있음
직관적 구현 가능	메모이제이션으로 간단하게 구현	반복 구조 어려운 경우 있음

---

7. 시각적 예시 (피보나치 수열)

• 일반 재귀: 트리 구조, 동일 노드 여러 번 계산
• DP: 한 번 계산 후 테이블 저장 → 중복 호출 없음

예: fib(5)

• 일반 재귀: 15번 호출
• DP: 6번 계산 후 재사용

---

8. DP 문제 유형 분류

유형	예시 문제
배열 기반	최대 연속 합, LIS (최장 증가 부분 수열)
2차원 테이블	LCS, 최소 편집 거리, 최단 경로
배낭 문제형	0-1 Knapsack, 부분 집합 합
그래프형	플로이드 워셜, 벨만-포드

---

9. 활용 분야

분야	활용 예시
컴퓨터 과학	알고리즘 최적화, 문자열 처리
경영학/최적화	생산 최적화, 자원 배분
금융	최소 비용 계산, 환율 계산 경로
게임 개발	이동 경로, 최단 시나리오 선택

---

10. 결론

동적 계획법은 복잡하고 비효율적인 완전 탐색 문제를 효율적으로 최적화할 수 있는 알고리즘 전략이다. 중복 계산을 방지하고, 작은 문제부터 큰 문제를 해결하는 방식으로 많은 실전 문제에서 필수적으로 사용된다. 점화식 설계와 테이블 활용 능력을 기르면, 다양한 문제를 빠르고 정확하게 해결할 수 있다.