동적 프로그래밍의 기초

5.1 동적 프로그래밍 정의.

동적 프로그래밍 (Dynamic Programming, DP) — 복잡한 문제를 더 간단한 하위 문제로 나눠서 해결하는 최적화 기법이야. 동적 프로그래밍은 최적의 하위 문제 구조로 나눌 수 있는 겹치는 하위 문제들에 효과적으로 사용돼.

작동 원리:

1. 최적의 하위 구조:

문제가 최적의 하위 구조를 가지고 있으면, 그 문제의 최적의 해결책을 하위 문제들의 최적의 해결책으로 구성할 수 있어. 즉, 더 큰 문제를 해결하기 위해 몇 개의 작은 하위 문제를 해결할 수 있다는 거지.

2. 겹치는 하위 문제:

문제에 겹치는 하위 문제가 있다면, 그 하위 문제들이 문제 해결 과정에서 여러 번 반복돼. 동적 프로그래밍은 이미 해결된 하위 문제의 결과를 기억(메모이제이션)해서 겹치는 하위 문제들을 효과적으로 해결해.

3. 메모이제이션과 테이블화:

메모이제이션 (탑다운): 하위 문제의 결과를 메모리에 저장해서 다시 계산하지 않도록 하는 재귀적 접근 방식이야.

테이블화 (바텀업): 하위 문제의 결과를 테이블(보통 배열)에 계산하고 저장해서 최종 결과를 계산하는 반복 접근 방식이야.

동적 프로그래밍으로 해결 가능한 문제 예제

5.2 배낭 문제.

문제:

각 아이템에는 무게와 가치가 있는 아이템 집합이 있어. 제한된 용량의 배낭에 아이템들을 선택해서 총 가치를 최대화해야 해.

중요! 탐욕 알고리즘으로 잘 해결되던 유사한 문제와 달리, 이 문제에서는 아이템을 나눌 수 없어.

해결책:

아이템을 행으로, 배낭의 가능한 용량을 열로 하는 표를 만들어. 셀의 값은 해당 아이템 수와 용량에 대한 최대 가치를 나타내.

시간 복잡도: O(n * W), 여기서 n은 아이템의 수이고, W는 배낭의 용량이야.

Python 코드 예제:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 최단 경로 찾기 문제

문제:

가중 그래프의 모든 쌍의 정점 사이의 최단 경로를 찾아.

해결책:

표는 그래프의 정점에 해당하는 행과 열로 구성돼. 셀의 값은 두 정점 간의 최단 거리를 나타내.

시간 복잡도: O(V^3), 여기서 V는 정점의 수야

Python 코드 예제:

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 동적 프로그래밍과 다른 방법들 비교.

완전 탐색 (brute force)와 비교:

시간 복잡도:

• 완전 탐색: 종종 지수 시간 복잡도를 가져(예: 피보나치 수열 문제의 O(2^n)).
• 동적 프로그래밍: 시간 복잡도를 다항식으로 줄여(예: 피보나치 수열 문제의 O(n)).

공간 복잡도:

• 완전 탐색: 메모리를 덜 사용할 수 있지만 시간 비용이 높아.
• 동적 프로그래밍: 중간 결과 저장을 위해 메모리를 더 사용할 수 있지만 (예: 메모이제이션을 사용하는 피보나치 문제의 O(n)), 시간상 이점을 가져.

탐욕 알고리즘 (greedy algorithms)과 비교:

최적성:

• 탐욕 알고리즘: 항상 전역 최적 해결책을 찾지는 않지만, 더 빠르고 구현이 쉬워.
• 동적 프로그래밍: 전역 최적 해결책을 찾고, 더 많은 계산 자원이 필요해.

문제의 예:

• 탐욕 알고리즘: 분수 배낭 문제 (fractional knapsack), 최소 스패닝 트리 (MST).
• 동적 프로그래밍: 배낭 문제 (정수형), 최장 공통 부분 수열 (LCS).