동적 계획법(DP) 쉽게 이해하기: 파이썬1으로 풀어보는 예제

안녕하세요! 김코딩입니다
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누고, 한 번 해결한 문제의 결과를 저장하여 중복 계산을 피하는 알고리즘 기법입니다.

---

1. 동적 계획법이란?

DP는 **분할 정복(Divide and Conquer)과 메모이제이션(Memoization)**을 활용하여 문제를 효율적으로 해결하는 기법입니다.

🔹 분할 정복: 문제를 작은 하위 문제로 나누어 해결
🔹 메모이제이션: 한 번 계산한 값을 저장하여 중복 연산 방지

💡 적용 가능한 문제 특징:
✅ 최적 부분 구조 (Optimal Substructure): 문제를 작은 문제로 나눌 수 있어야 함
✅ 중복되는 부분 문제 (Overlapping Subproblems): 동일한 부분 문제가 반복되어 등장

---

2. 피보나치 수열을 활용한 DP 개념 이해

❌ 비효율적인 재귀(단순 분할 정복)

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 결과: 55

🚨 위 코드의 문제점: 같은 값을 여러 번 계산하여 **시간 복잡도가 O(2ⁿ)**으로 증가

---

3. 동적 계획법 적용 (메모이제이션 사용)

방법 1: Top-Down 방식 (재귀 + 메모이제이션)

dp = {}

def fib_memo(n):
    if n <= 1:
        return n
    if n not in dp:
        dp[n] = fib_memo(n - 1) + fib_memo(n - 2)  # 저장하여 중복 연산 방지
    return dp[n]

print(fib_memo(10))  # 결과: 55

✅ 장점: 불필요한 연산을 제거하여 성능 향상 (시간 복잡도 O(N))

---

방법 2: Bottom-Up 방식 (반복문 + DP 테이블)

def fib_tabulation(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]

print(fib_tabulation(10))  # 결과: 55

✅ 장점: 메모이제이션보다 더 효율적인 O(N) 시간 복잡도
✅ 단점: O(N) 크기의 추가 메모리 필요

---

4. 동적 계획법 문제 예제: 최소 동전 개수 문제

💡 문제: N원을 만들기 위한 최소 동전 개수 구하기

• 사용할 수 있는 동전: {1, 3, 4}

🔹 예제 입력: N = 6
🔹 예제 출력: 2 (4원 + 2원)

DP를 활용한 풀이 (Bottom-Up)

def min_coins(n, coins):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # 0원을 만드는 데 필요한 동전 개수는 0
    
    for i in range(1, n + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)  # 최소 개수 갱신
                
    return dp[n] if dp[n] != float('inf') else -1

print(min_coins(6, [1, 3, 4]))  # 결과: 2

✅ 시간 복잡도: O(N * len(coins))
✅ 공간 복잡도: O(N)

---

5. 동적 계획법 활용 분야

✔ 피보나치 수열
✔ 최소 비용 경로 문제 (Dijkstra 알고리즘)
✔ 배낭 문제 (Knapsack Problem)
✔ 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
✔ 행렬 곱셈 순서 최적화 (Matrix Chain Multiplication)

---

6. 결론

✅ DP는 중복 계산을 줄여 알고리즘을 최적화하는 강력한 기법
✅ Top-Down (재귀 + 메모이제이션) vs Bottom-Up (반복문 + DP 테이블) 선택 가능
✅ 실전 문제 풀이에서 최적 부분 구조와 중복되는 부분 문제를 확인하는 것이 핵심

🎯 연습 추천 문제:

1. 백준 1003번: 피보나치 함수
2. 백준 1463번: 1로 만들기
3. 백준 2579번: 계단 오르기
4. 프로그래머스: 등굣길

🔥 다양한 DP 문제를 연습하며 실력을 키워보세요!