[알고리즘] 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘

다이나믹 프로그래밍 알고리즘이란?

다이나믹 프로그래밍 알고리즘 특징

• 부분 문제 분할: 큰 문제를 작은 문제로 나누어 해결

• 중복 계산 방지: 이미 계산한 결과를 저장(메모이제이션 / 테이블화)하여 다시 활용

• 시간 복잡도 개선: 중복 연산을 줄여 지수 시간 → 다항 시간으로 단축 가능

• 조건: 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems)가 존재해야 함

다이나믹 프로그래밍 알고리즘 실제 적용 사례

• 피보나치 수열 계산

• 최단 경로 문제 (플로이드-워셜, 다익스트라 변형)

• 배낭 문제 (Knapsack Problem)

• 최적화 문제: 최소 비용, 최대 이익 찾기

• 문자열 처리: 최장 공통 부분 수열(LCS), 편집 거리(Edit Distance)

다이나믹 프로그래밍 알고리즘의 단계

다이나믹 프로그래밍 구현 (ex. python)

• Top-down (재귀 + 메모이제이션)

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

• Bottom-up (반복문 + DP 테이블)

def fib_dp(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]