동적 계획법(Dynamic Programming)

기술노트

동적 계획법(Dynamic Programming)

동적 계획법(DP)은 복잡한 문제를 간단한 하위 문제로 분할하여 해결하는 알고리즘 설계 기법입니다. 이 방법은 중복되는 하위 문제의 결과를 저장하고 재사용하여 계산 효율성을 크게 향상시킵니다.

동적 계획법의 핵심 원리

1. 최적 부분 구조(Optimal Substructure)

  • 큰 문제의 최적해가 작은 문제의 최적해로 구성되는 성질입니다.
  • 즉, 문제의 최적 솔루션에는 하위 문제의 최적 솔루션이 포함되어 있습니다.

2. 중복되는 부분 문제(Overlapping Subproblems)

  • 같은 작은 문제가 반복해서 발생하는 특성입니다.
  • 이 결과를 저장하여 재계산을 피하는 것이 DP의 핵심입니다.

동적 계획법 구현 방식

1. 하향식 접근법(Top-Down): 메모이제이션(Memoization)

  • 재귀 호출을 사용하여 문제를 더 작은 하위 문제로 분할합니다.
  • 계산된 결과를 메모리(일반적으로 배열이나 해시 테이블)에 저장합니다.
  • 이미 계산된 하위 문제의 값이 필요하면 저장된 값을 재사용합니다.
# 피보나치 수열의 하향식 접근법 (메모이제이션)
def fibonacci_top_down(n, memo={}):
    if n in memo:
        return memo[n]  # 이미 계산된 값을 사용
    
    if n <= 2:
        return 1
    
    # 결과 계산 및 저장
    memo[n] = fibonacci_top_down(n-1, memo) + fibonacci_top_down(n-2, memo)
    return memo[n]

2. 상향식 접근법(Bottom-Up): 타뷸레이션(Tabulation)

  • 작은 하위 문제부터 시작하여 큰 문제를 해결해 나가는 방식입니다.
  • 결과를 테이블(일반적으로 배열)에 저장하며 진행합니다.
  • 반복문을 사용하여 구현하므로 스택 오버플로우 위험이 없습니다.
# 피보나치 수열의 상향식 접근법 (타뷸레이션)
def fibonacci_bottom_up(n):
    if n <= 2:
        return 1
    
    # DP 테이블 초기화
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    
    # 작은 문제부터 해결
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

동적 계획법 문제 해결 단계

  1. 문제가 DP로 해결 가능한지 확인: 최적 부분 구조와 중복되는 부분 문제 특성을 가지는지 분석
  2. 상태(State) 정의: 문제의 변수를 명확히 정의 (예: dp[i]는 i번째 요소까지의 최적값)
  3. 점화식(Recurrence Relation) 수립: 상태 간의 관계 정의 (예: dp[i] = max(dp[i-1] + arr[i], dp[i-2] + arr[i]))
  4. 기저 사례(Base Case) 설정: 가장 작은 하위 문제의 해답 정의 (예: dp[0] = 0, dp[1] = arr[0])
  5. 계산 순서 결정: 하향식 또는 상향식 접근법 선택
  6. 결과 계산: 정의된 방식으로 문제 해결

대표적인 동적 계획법 문제

피보나치 수열(Fibonacci Sequence)

  • 문제: n번째 피보나치 수를 계산
  • 점화식: F(n) = F(n-1) + F(n-2), F(1) = F(2) = 1
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(n)

최장 공통 부분 수열(Longest Common Subsequence, LCS)

  • 문제: 두 문자열의 가장 긴 공통 부분 수열 찾기
  • 접근법: dp[i][j]는 문자열 X의 i번째 문자까지와 Y의 j번째 문자까지의 LCS 길이
def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

배낭 문제(Knapsack Problem)

  • 문제: 주어진 무게 제한 내에서 최대 가치를 갖는 물건들의 조합 찾기
  • 접근법: dp[i][w]는 i번째 물건까지 고려했을 때, 무게 w의 배낭에 담을 수 있는 최대 가치
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(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

최단 경로 문제(Shortest Path)

  • 문제: 그래프에서 두 노드 간의 최단 경로 찾기
  • 알고리즘: 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘
  • 플로이드-워셜 예시:
def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # 그래프 복사
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

최대 부분 배열 합(Maximum Subarray Sum)

  • 문제: 연속된 부분 배열의 최대 합 찾기
  • 접근법: dp[i]는 i번째 요소까지의 최대 부분 배열 합
def max_subarray_sum(arr):
    n = len(arr)
    dp = [0] * n
    dp[0] = arr[0]
    max_sum = dp[0]
    
    for i in range(1, n):
        dp[i] = max(arr[i], dp[i-1] + arr[i])
        max_sum = max(max_sum, dp[i])
    
    return max_sum

동적 계획법의 최적화 기법

1. 공간 복잡도 최적화

  • 많은 DP 문제에서 전체 dp 배열이 아닌 마지막 몇 개의 상태만 필요한 경우가 있습니다.
  • 이러한 경우 공간 복잡도를 O(n)에서 O(1) 또는 O(k)로 줄일 수 있습니다.
# 공간 최적화된 피보나치 계산
def fibonacci_optimized(n):
    if n <= 2:
        return 1
    
    a, b = 1, 1
    for _ in range(3, n + 1):
        a, b = b, a + b
    
    return b

2. 상태 압축(State Compression)

  • 큰 상태 공간을 작은 비트마스크로 표현하여 메모리 사용을 최적화합니다.
  • 특히 집합이나 부분집합을 다루는 문제에서 유용합니다.

3. 분할 정복 최적화(Divide and Conquer Optimization)

  • 특정 조건을 만족하는 DP 문제에서 상태 전이를 더 효율적으로 계산할 수 있습니다.
  • O(n²)에서 O(n log n)으로 시간 복잡도를 개선할 수 있습니다.

동적 계획법 vs 다른 알고리즘 기법

1. 동적 계획법 vs 분할 정복(Divide and Conquer)

  • 공통점: 문제를 더 작은 하위 문제로 분할
  • 차이점:
    • 분할 정복은 하위 문제가 중복되지 않음
    • DP는 중복되는 하위 문제의 결과를 저장하고 재사용

2. 동적 계획법 vs 그리디 알고리즘(Greedy Algorithm)

  • 공통점: 최적화 문제 해결
  • 차이점:
    • 그리디는 각 단계에서 지역적 최적해를 선택
    • DP는 모든 가능한 하위 문제를 계산하여 전역 최적해 보장

동적 계획법의 한계와 도전

  1. 상태 공간이 너무 큰 경우: 메모리 제한에 걸릴 수 있습니다.
  2. 점화식 도출이 어려운 복잡한 문제: 문제의 구조를 이해하기 어려울 수 있습니다.
  3. 최적 부분 구조가 없는 문제: DP로 해결할 수 없습니다.

실전 응용 분야

  • 컴퓨터 과학: 문자열 처리, 그래프 알고리즘, 자원 할당
  • 경제학: 최적 투자 전략, 자원 분배
  • 생물정보학: DNA 서열 정렬, 단백질 구조 예측
  • 로봇공학: 경로 계획, 모션 계획
  • 게임 이론: 최적 전략 계산

관련 항목

원본 주소 "https://technote.wiki/index.php?title=동적_계획법(Dynamic_Programming)&oldid=525"