[알고리즘] 다이나믹 프로그래밍과 최적화 문제

다이나믹 프로그래밍(Dynamic Programming) 개요

다이나믹 프로그래밍은 복잡한 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 기법입니다. 중복되는 하위 문제들을 한 번씩만 계산하여 중복 계산을 피하고, 계산 결과를 테이블에 저장하여 효율적으로 문제를 해결합니다. 다이나믹 프로그래밍은 큰 문제를 작은 하위 문제로 쪼개고, 하위 문제의 결과를 결합하여 원래 문제의 해를 찾는 접근법을 사용합니다.

---

다이나믹 프로그래밍의 특징

다이나믹 프로그래밍을 사용하는 문제는 다음과 같은 특징을 가집니다.

• 중복된 하위 문제: 문제를 작은 하위 문제로 나누었을 때, 중복되는 하위 문제들이 발생합니다.
• 최적 부분 구조: 문제의 최적해가 작은 하위 문제들의 최적해를 결합하여 얻어지는 경우가 있습니다.
• 메모이제이션: 중복 계산을 피하기 위해 계산한 결과를 저장하고 재사용하는 기술입니다.

---

다이나믹 프로그래밍의 예시

다이나믹 프로그래밍을 이해하기 위해 두 가지 예시를 살펴보겠습니다.

 

피보나치 수열

피보나치 수열은 다이나믹 프로그래밍의 대표적인 예시입니다. 피보나치 수열의 n번째 항을 구할 때, n-1번째와 n-2번째 항의 값을 이용하여 계산합니다. 중복 계산을 피하고자 계산 결과를 테이블에 저장하는 방식으로 다이나믹 프로그래밍을 적용할 수 있습니다.

def fibonacci(n):
    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]

 

배낭 문제

배낭 문제는 무게와 가치가 각각 주어진 물건들 중에서 정해진 무게의 배낭에 최대한 가치를 담는 문제입니다. 다이나믹 프로그래밍을 사용하여 각 물건별로 선택 여부를 결정하고 최적해를 찾을 수 있습니다.

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]

 

이와 같이 다이나믹 프로그래밍은 중복 계산을 피하고 최적해를 찾는데 사용되며, 여러 최적화 문제에 적용될 수 있습니다.