[Python] 알고리즘 개념5 - 동적 프로그래밍 (DP)

 

 

🚀 1. 동적 프로그래밍(DP)이란?

**동적 프로그래밍(Dynamic Programming, DP)**은 큰 문제를 작은 문제로 나누어 해결하는 최적화 기법입니다. 쉽게 말해, 같은 계산을 여러 번 반복하지 않고, 한 번 계산한 결과를 저장하여 다시 활용하는 기법입니다.
 
💡 DP의 특징:

• 부분 문제 최적화: 작은 문제를 먼저 해결한 후, 큰 문제를 해결합니다.
• 중복 계산 방지: 이미 해결한 문제는 저장하여 다시 계산하지 않습니다.
• 재귀(Top-Down) 또는 반복(Bottom-Up) 방식 사용

 
➡ 대표적인 DP 문제

• 피보나치 수열
• 최단 경로 문제
• 배낭 문제 (Knapsack Problem)
• LIS (최장 증가 부분 수열)

---

 

 

🚀 2. DP의 핵심 개념

DP를 이해하기 위해 가장 중요한 개념 두 가지:

 

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

큰 문제의 해결 방법이 작은 문제들의 해결 방법을 결합하여 최적의 결과를 만들 수 있을 때, 최적 부분 구조를 가진다고 합니다.
예를 들어, 피보나치 수열을 계산할 때 F(n) = F(n-1) + F(n-2) 와 같이 작은 문제들을 조합하여 큰 문제를 해결할 수 있습니다.

 

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

동일한 작은 문제가 여러 번 반복해서 나타날 때, 중복되는 부분 문제를 가진다고 합니다.
예를 들어, 피보나치 수열을 단순 재귀로 계산하면 같은 값을 여러 번 계산하게 됩니다. 이를 방지하기 위해 계산된 값을 저장하여 재사용하는 것이 DP의 핵심입니다.
 
➡ 이 두 가지 조건을 만족하면 DP를 사용할 수 있습니다.

---

 

 

🚀 3. DP의 유형 (탑다운 vs 바텀업)

DP는 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식으로 구현할 수 있습니다. 두 방식의 차이를 알아보겠습니다.

 

🔹 탑다운(Top-Down) 방식 (재귀 + 메모이제이션)

탑다운 방식은 큰 문제를 먼저 해결하려고 시도하면서, 하위 문제를 해결할 때마다 결과를 저장하는 방식입니다.

# 피보나치 수열 - Top-Down 방식
memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

 
➡ 특징:

• 재귀를 사용하여 큰 문제를 먼저 해결하면서, 작은 문제를 저장(메모이제이션)하여 중복 계산을 방지
• 직관적인 코드지만, 재귀 호출이 많아지면 스택 오버플로우가 발생할 가능성이 있음

 
💡 **메모이제이션(Memoization)**이란?

• 한 번 계산한 값을 배열이나 딕셔너리에 저장하여 다시 같은 문제를 만나면 바로 값을 반환하는 기법입니다.

---

 

 

🔹 바텀업(Bottom-Up) 방식 (반복문 + DP 테이블)

바텀업 방식은 작은 문제부터 해결하여 차근차근 쌓아가면서 최종 문제를 해결하는 방식입니다.

# 피보나치 수열 - Bottom-Up 방식
def fib(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

 
➡ 특징:

• 반복문을 사용하여 스택 오버플로우 위험 없이 안전하게 계산
• 작은 문제부터 해결하여 큰 문제로 확장하는 방식
• DP 테이블을 활용하여 중복 계산을 방지

 
💡 바텀업 방식이 유리한 경우

• 재귀 호출이 너무 많아지는 문제에서는 바텀업 방식이 스택 오버플로우를 방지할 수 있어 유리합니다.

 
💡 탑다운 vs 바텀업 비교
방식 구현 방식 장점 단점

탑다운(Top-Down)	재귀 + 메모이제이션	코드가 직관적	재귀 호출이 많으면 스택 오버플로우 발생 가능
바텀업(Bottom-Up)	반복문 + DP 테이블	스택 오버플로우 없음	DP 테이블을 사용하므로 공간이 더 필요할 수 있음

---

 

 

🚀 4. DP 문제 해결 패턴

1. 문제를 작은 하위 문제로 나눌 수 있는지 확인한다.
2. 하위 문제의 해결 방법을 저장하고 재사용할 수 있는지 확인한다.
3. 탑다운(재귀+메모이제이션) 또는 바텀업(반복문+DP 테이블) 방식을 선택한다.
4. 중복 계산을 최소화하여 최적화한다.

 
➡ 이 패턴을 따르면 대부분의 DP 문제를 해결할 수 있습니다.

---

 

 

🚀 5. DP 활용 예제

 

✅ 예제 1: 동전 교환 문제 (Coin Change)

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

 
💡 설명:

• dp[i]: i원을 만들기 위한 최소 동전 개수
• 각 동전 단위를 반복하면서 최적의 경우를 갱신함
• 시간복잡도: O(nm) (n=동전 개수, m=목표 금액)

---

 

 

✅ 마무리 정리

• **동적 프로그래밍(DP)**은 작은 문제를 해결한 결과를 저장하여 중복 계산을 줄이는 최적화 기법
• 탑다운(재귀+메모이제이션)과 바텀업(반복문+DP 테이블) 방식이 있음
• 문제를 최적 부분 구조와 중복되는 부분 문제로 나눌 수 있다면 DP를 적용할 수 있음