동적 계획법 - 4. DP 실전 연습 (문제 풀이)

4. DP 실전 연습 (문제 풀이)

동적 계획법(DP)의 개념을 이해했다면, 직접 문제를 풀어보는 것이 중요합니다.
이번 장에서는 단계별 난이도의 문제를 통해 DP를 연습하고, 알고리즘 문제 풀이 사이트에서 추천 문제를 선정하여 실력을 향상시키는 방법을 소개합니다.

---

4-1. 단계별 난이도 문제 풀이

📌 기초 문제 (Basic)

1️⃣ 피보나치 수열 (Fibonacci Numbers)

• 시간 제한: 1초
• 메모리 제한: 128MB
• 공간 복잡도: O(1)
• 문제: n번째 피보나치 수를 구하는 문제
• 접근 방법:
  • 재귀 (O(2^n)) → 비효율적
  • 메모이제이션 (O(n)) → 최적화
  • 바텀업 (O(n), O(1) 메모리) → 최적화

def fib(n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("n must be a non-negative integer")
    
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 테스트 케이스
print(fib(10))  # 출력: 55
print(fib(0))   # 출력: 0
print(fib(1))   # 출력: 1

# 예외 처리 테스트
try:
    fib(-1)
except ValueError as e:
    print(f"Error: {e}")  # 출력: ValueError (음수 입력)

---

2️⃣ 계단 오르기 (Climbing Stairs)

• 시간 제한: 1초
• 메모리 제한: 128MB
• 공간 복잡도: O(1)
• 문제: 한 번에 1칸 또는 2칸씩 올라갈 수 있을 때, n개의 계단을 오르는 방법의 수
• 점화식: dp(n)=dp(n−1)+dp(n−2)

def climb_stairs(n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("n must be a non-negative integer")

    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

print(climb_stairs(5))  # 출력: 8
print(climb_stairs(10))  # 출력: 89

---

📌 중급 문제 (Intermediate)

3️⃣ 배낭 문제 (0/1 Knapsack Problem)

• 시간 제한: 2초
• 메모리 제한: 256MB
• 공간 복잡도: O(W) (1D 최적화 적용 가능)

def knapsack(weights, values, W):
    if len(weights) != len(values):
        raise ValueError("Weights and values must have the same length")
    if not all(isinstance(w, int) and w >= 0 for w in weights):
        raise ValueError("All weights must be non-negative integers")
    if not all(isinstance(v, int) and v >= 0 for v in values):
        raise ValueError("All values must be non-negative integers")
    if not isinstance(W, int) or W < 0:
        raise ValueError("Weight capacity must be a non-negative integer")

    n = len(weights)
    dp = [0] * (W + 1)

    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

# 테스트 케이스
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W))  # 출력: 7

---

4️⃣ 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

• 시간 제한: 2초
• 메모리 제한: 256MB
• 공간 복잡도: O(n×m)

def lcs(s1, s2):
    if not isinstance(s1, str) or not isinstance(s2, str):
        raise TypeError("Input must be strings")
    
    if not s1 or not s2:
        return 0

    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# 테스트 케이스
print(lcs("abcde", "ace"))  # 출력: 3 ("ace")
print(lcs("abc", "def"))    # 출력: 0 (공통 부분 수열 없음)

# 예외 처리 테스트
try:
    lcs(123, "abc")
except TypeError as e:
    print(f"Error: {e}")  # 출력: TypeError (문자열이 아님)

---

4-2. 알고리즘 사이트에서 추천 문제 풀기

📌 백준(Baekjoon) - DP 관련 문제

• 기초: 1003(피보나치 함수), 9095(1, 2, 3 더하기)
• 중급: 12865(평범한 배낭), 11053(가장 긴 증가하는 부분 수열)
• 고급: 9251(LCS), 11049(행렬 곱셈 순서)

👉 사이트: https://www.acmicpc.net/problemset

---

📌 LeetCode - DP 문제

• Easy: Climbing Stairs (70), House Robber (198)
• Medium: Longest Palindromic Substring (5), Decode Ways (91)
• Hard: Regular Expression Matching (10), Edit Distance (72)

👉 사이트: https://leetcode.com/problemset/dynamic-programming/

---

📌 프로그래머스 - 코딩테스트 대비 DP 문제

• Level 2: N으로 표현, 타일 장식물
• Level 3: 정수 삼각형, 등굣길

👉 사이트: https://programmers.co.kr/learn/challenges