Python 코딩테스트 08: 다이나믹 프로그래밍 DP

Python 코딩테스트 08: 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어 푸는 방법론입니다.

이 방법론은 작은 문제들의 해답을 이용해 큰 문제의 해답을 찾는 과정에서 효율적인 메모리 사용과 계산 속도 향상을 목표로 합니다.

 

DP는 주로 두 가지 속성을 가지는 문제에 적합합니다:

최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)입니다.

---

다이나믹 프로그래밍의 기본 원리

최적 부분 구조 (Optimal Substructure)

문제를 작은 하위 문제들로 나누고, 이 하위 문제들의 해답을 이용하여 원래 문제의 해답을 도출할 수 있는 속성입니다.

예를 들어, 피보나치 수열의 경우, F(n) = F(n-1) + F(n-2)와 같이 작은 문제들의 해답을 이용해 큰 문제의 해답을 구할 수 있습니다.

 

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

문제를 풀기 위해 동일한 하위 문제를 여러 번 풀어야 하는 경우입니다.

예를 들어, 피보나치 수열에서는 F(n-1)과 F(n-2)를 계산하기 위해 F(n-2)와 F(n-3)을 반복적으로 계산해야 합니다.

---

다이나믹 프로그래밍의 구현 방식

1. 탑다운(메모이제이션, Memoization) 방식
   • 재귀 함수와 메모이제이션을 이용하여 구현합니다.
   • 이미 계산된 결과를 저장해 두고 필요할 때마다 재사용하여 중복 계산을 방지합니다.
2. 바텀업(Bottom-Up) 방식
   • 반복문을 이용하여 작은 문제부터 차근차근 해결해 나갑니다.
   • 메모이제이션 없이, 작은 문제의 해답을 순차적으로 계산하여 최종 해답에 도달합니다.

---

예시 문제 1: 피보나치 수열

1. 탑다운 방식

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

print(fib_memo(10))  # Output: 55

2. 바텀업 방식

def fib_bottom_up(n):
    if n <= 2:
        return 1
    dp = [0] * (n+1)
    dp[1], dp[2] = 1, 1
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_bottom_up(10))  # Output: 55

---

예시 문제 2: 최소 동전 거스름돈 문제

거스름돈을 만들기 위해 사용할 수 있는 동전의 최소 개수를 구하는 문제입니다.

예를 들어, 1원, 3원, 4원 동전으로 6원을 만들기 위해 최소 몇 개의 동전이 필요한지 구하는 문제입니다.

바텀업 방식

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 3, 4]
amount = 6
print(coin_change(coins, amount))  # Output: 2

---

다이나믹 프로그래밍의 활용

1. 경로 찾기 문제

미로 문제나 최단 경로 문제 등에서 DP를 활용하여 최적의 경로를 찾을 수 있습니다.

2. 문자열 처리 문제

편집 거리(Edit Distance) 문제나 가장 긴 공통 부분 수열(Longest Common Subsequence) 문제 등에서 DP를 사용하여 효율적으로 문제를 해결할 수 있습니다.

3. 배낭 문제

한정된 무게 안에서 최대 가치를 얻는 문제 등에서 DP를 사용하여 최적의 해답을 도출할 수 있습니다.

---

팁과 주의사항

1. 문제를 이해하고 작은 문제로 나누기
   • 문제를 작은 단위로 나누고, 이 작은 문제들이 어떻게 큰 문제를 해결하는지 파악합니다.
2. 메모이제이션과 바텀업 방식 선택
   • 문제의 특성과 요구 사항에 따라 메모이제이션(탑다운) 방식이나 바텀업 방식을 선택하여 구현합니다.
3. 적절한 자료 구조 사용
   • DP 테이블을 구현할 때, 문제에 따라 리스트, 딕셔너리 등 적절한 자료 구조를 선택하여 사용합니다.