[오늘의 파이썬] 2. Dynamic Programming / 동적 계획법!

1. Dynamic Programming 이란?

동적 계획법(Dynamic Programming)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법으로 문제의 효율적인 해결을 가능하게 해줍니다. DP는 큰 문제를 해결하기 위해 작은 문제의 해결 방법을 활용하는 것이 핵심 아이디어입니다. 또한, 부분 문제의 해결 결과를 저장하고 재사용하여 중복 계산을 피하는 특징도 가지고 있습니다.

 

2. Dynamic Programming 을 쓰는 이유?

DP를 사용하는 이유는 큰 문제를 작은 문제로 분할하여 효율적으로 해결할 수 있기 때문입니다. 일반적으로 동적 계획법을 사용하면 지수적인 시간 복잡도를 가지는 재귀적 해결 방법에 비해 훨씬 빠른 시간에 문제를 해결할 수 있습니다. 또한, DP는 부분 문제의 해결 결과를 저장하여 중복 계산을 피할 수 있기 때문에, 같은 문제를 반복적으로 해결해야 하는 경우에도 효율적입니다.

 

3. Dynamic Programming 사용 조건 2가지

DP를 적용하기 위해서는 다음 두 가지 조건을 만족해야 합니다.

 

1. 겹치는 부분 문제 (Overlapping Subproblems): 큰 문제를 작은 문제로 나누었을 때, 작은 문제들 간에 중복되는 부분 문제들이 존재해야 합니다. 이렇게 중복되는 부분 문제들이 발생하는 경우, 중복 계산을 피하기 위해 한 번 계산한 작은 문제의 해결 결과를 저장하고 재사용합니다.
2. 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적 해결 방법이 작은 문제의 최적 해결 방법으로 구성되어야 합니다. 다시 말해, 큰 문제의 최적해를 작은 문제의 최적해를 이용하여 구할 수 있어야 합니다. 이러한 구조를 가지는 경우에 DP를 사용하여 문제를 해결할 수 있습니다.

 

4. Dynamic Programming 예시 코드

 

1. 예시코드 1 : 최대 부분 배열 합 계산

# DP를 활용한 최대 부분 배열 합 계산!

def max_subarray_sum(arr):
    len_arr = len(arr)
    # 각 위치에서의 최대 부분 배열 합 저장
    dp = [0] * n
    dp[0] = arr[0]
    max_sum = arr[0]
    
    for i in range(1, len_arr):
        # 이전 부분 배열 합과 현재 위치의 원소를 더한 값 비교
        dp[i] = max(arr[i], dp[i-1] + arr[i])
        # 최대 부분 배열 합 갱신
        max_sum = max(max_sum, dp[i])
    
    return max_sum

arr = [-10, 5, -3, 2, -1, 7, 1, -5, 4]
result = max_subarray_sum(arr)
print(result)

위의 예제는 최대 부분 배열 합을 계산하는 문제를 DP로 해결하고 있습니다. 각 위치마다의 최대 부분 배열 합을 저장하면서 문제를 작은 부분 문제로 분할하여 해결합니다. 이전 위치의 최대 부분 배열 합과 현재 위치의 원소를 더한 값 비교를 통해 부분 문제의 해결 결과를 도출하고, 전체 배열에 대한 최대 부분 배열 합을 구합니다.

 

아래는 Dynamic Programming를 활용한 배낭 문제 예시입니다.

 

2. 예시 코드 2 : 배낭 문제 (Knapsack Problem)

 

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 j in range(1, capacity+1):
            if weights[i-1] > j:
                # 현재 아이템의 무게가 배낭의 용량보다 큰 경우
                dp[i][j] = dp[i-1][j]
            else:
                # 현재 아이템을 포함할지 여부를 결정하여 최대 가치 갱신
                dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])
    
    return dp[n][capacity]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
result = knapsack(weights, values, capacity)
print(result)

이 문제에서는 주어진 용량(capacity)을 가지고 아이템을 선택하여 가치의 합을 최대화하는 문제입니다. DP를 사용하여 각 아이템까지의 최대 가치 합을 저장하면서 문제를 작은 부분 문제로 분할하여 해결합니다. 현재 아이템을 선택할지 여부를 결정하고, 이전 아이템까지의 최대 가치 합과 현재 아이템의 가치를 더한 값 비교를 통해 부분 문제의 해결 결과를 도출하고, 전체 아이템에 대한 최대 가치 합을 구합니다.

 

5. Dynamic Programming 의 장단점

1. Dynamic Programming의 장점

 

• 중복 계산을 피할 수 있다 : DP는 작은 부분 문제의 해결 결과를 저장하여 중복 계산을 피합니다. 이를 통해 시간 복잡도를 크게 개선할 수 있습니다.
• 효율적인 문제 해결이 가능하다 :  DP를 사용하면 지수적인 시간 복잡도를 갖는 문제도 효율적으로 해결할 수 있습니다. 큰 문제를 작은 부분 문제로 분할하여 해결하므로 전체 문제를 한 번에 해결하는 것보다 훨씬 빠르게 정답에 도달할 수 있습니다.
• 최적해를 보장한다 : DP는 최적 부분 구조를 가지는 문제에 대해 최적해를 보장합니다. 작은 문제의 최적해를 이용하여 큰 문제의 최적해를 구할 수 있습니다.

2. Dynamic Programming의 단점

 

• 메모리 사용량이 크다 : DP는 부분 문제의 해결 결과를 저장해야 하므로, 메모리 사용량이 크게 증가할 수 있습니다. 특히, 부분 문제의 개수가 많은 경우에는 메모리 부담이 커질 수 있습니다.
• 모든 문제에 적용하기 어렵다 : DP는 겹치는 부분 문제와 최적 부분 구조가 존재하는 문제에 적용할 수 있습니다. 이러한 조건이 충족되지 않는 경우에는 DP를 사용할 수 없거나, 다른 알고리즘 설계 기법을 고려해야 할 수도 있습니다.

3. 주의 사항

 

• 문제의 크기에 따른 적절한 구현 방식을 선택해야 한다: DP는 재귀적인 접근 방식, 반복적인 접근 방식 두 가지로 구현할 수 있습니다. 작은 크기의 문제에는 재귀적인 방식이 유리하고, 큰 크기의 문제에는 반복적인 방식이 효율적입니다.
• 올바른 부분 문제의 정의가 중요하다 : DP를 적용하기 위해서는 문제를 작은 부분 문제로 분할하여 해결해야 합니다. 따라서, 올바른 부분 문제의 정의를 세우는 것이 중요합니다. 부분 문제의 정의를 잘못하면 잘못된 해결 방법이 도출될 수 있습니다.