Dynamic Programming - 컴퓨터공학 > 알고리즘 | AI Insight Note

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 겹치는 하위 문제(Overlapping Subproblems) 로 분할하고, 결과를 저장·재사용해 중복 계산을 제거하는 알고리즘 설계 기법이다. 분할 정복과 달리 하위 문제의 결과를 메모이제이션(Memoization) 또는 타뷸레이션(Tabulation) 으로 저장한다.

핵심 조건

DP를 적용하려면 두 가지 조건이 필요하다.

조건	설명
최적 부분 구조	전체 최적해가 하위 문제의 최적해로 구성됨
겹치는 하위 문제	같은 하위 문제가 여러 번 반복됨

피보나치 수열로 보는 DP

일반 재귀 — O(2ⁿ) (매우 느림)

python

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
# fib(5) 호출 시 fib(3)이 2번, fib(2)가 3번 중복 계산

메모이제이션 (Top-Down) — O(n)

python

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
# 한 번 계산된 결과를 캐시에 저장 → 중복 계산 없음

타뷸레이션 (Bottom-Up) — O(n)

python

def fib(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]
# 테이블을 아래에서 위로 채워나감

대표 DP 문제 유형

배낭 문제 (0-1 Knapsack)

python

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 물건 i를 넣지 않는 경우
            dp[i][w] = dp[i-1][w]
            # 물건 i를 넣는 경우
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

최장 공통 부분 수열 (LCS)

X = "ABCBDAB", Y = "BDCAB"
LCS = "BCAB" (길이 4)

dp[i][j] = X[0..i]와 Y[0..j]의 LCS 길이
X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1
X[i] != Y[j]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

최단 경로 — 다익스트라

python

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

추가 대표 DP 문제

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

arr = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 101] → 길이 4

•O(n²) DP 또는 O(n log n) 이진 탐색 최적화
•주식 가격 상승 구간, 인내심 분류 문제에 활용

편집 거리 (Edit Distance / Levenshtein Distance)

두 문자열 s1, s2를 같게 만들기 위한 최소 삽입·삭제·교체 횟수.

dp[i][j] = s1[:i]를 s2[:j]로 만드는 최소 편집 횟수

•맞춤법 검사, DNA 서열 비교, 유사도 측정에 활용

행렬 경로 문제

m×n 격자를 (0,0)에서 (m-1,n-1)까지 이동하는 최적 경로.

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

DP vs 분할 정복

항목	동적 프로그래밍	분할 정복
하위 문제	겹침 (중복 존재)	독립적 (겹치지 않음)
결과 저장	메모이제이션/테이블	불필요
대표 예	피보나치, 배낭 문제	병합 정렬, 퀵 정렬

참고문헌

•Cormen et al. Introduction to Algorithms — Chapter 15
•Bellman, R. (1957). Dynamic Programming

Dynamic Programming동적 프로그래밍