동적 계획법 - 5. DP 마스터하기

5. DP 마스터하기

동적 계획법(DP)을 충분히 연습했다면, 이제 고급 문제를 해결하는 전략과 코딩 테스트에서 효율적으로 활용하는 방법을 익혀야 합니다.
이번 장에서는 DP 문제의 고급 접근법, 최적화 기법, 면접 및 코딩 테스트 대비 전략을 다룹니다.

---

5-1. DP를 활용한 고급 문제 접근법

📌 1️⃣ 상태(State) 정의 방법 학습

DP 문제를 풀기 위해서는 문제에서 변하는 값(상태)을 정의하는 것이 가장 중요합니다.

💡 예제 1: 계단 오르기 (Climbing Stairs)

• 상태 정의:
  • dp[i]: i번째 계단까지 오르는 방법의 수
• 점화식: dp[i]=dp[i−1]+dp[i−2]

💡 예제 2: 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

• 상태 정의:
  • dp[i]: nums[i]를 마지막 원소로 하는 가장 긴 증가 부분 수열의 길이
• 점화식: dp[i]=max⁡(dp[j]+1)  (if nums[j]<nums[i] for all j<i)

---

📌 2️⃣ 점화식(Recurrence Relation) 도출하기

점화식은 DP 문제를 해결하기 위한 수학적 관계식입니다.

💡 예제 1: 배낭 문제 (0/1 Knapsack Problem)

• 점화식: dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weighti]+valuei)

💡 예제 2: 행렬 곱셈 순서 (Matrix Chain Multiplication)

• 점화식: dp[i][j]=min⁡(dp[i][k]+dp[k+1][j]+pi−1pkpj)

---

📌 3️⃣ 공간 복잡도 최적화 (1D DP로 변환)

💡 예제 1: 피보나치 수열 (Fibonacci Numbers)

• 기본 DP (O(n) 공간 사용)

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]

• 공간 최적화 (O(1) 공간 사용)

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

---

5-2. 면접 및 코딩 테스트 대비

📌 1️⃣ DP 문제를 빠르게 해결하는 연습

💡 연습 예제: "n을 1, 2, 3의 합으로 표현하는 방법 수 구하기"

• 점화식: dp[i]=dp[i−1]+dp[i−2]+dp[i−3]

def ways_to_sum(n):
    if not isinstance(n, int):
        raise TypeError("Input must be an integer")
    if n < 0:
        raise ValueError("Input must be non-negative")

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

print(ways_to_sum(4))  # 출력: 7

---

📌 2️⃣ 코딩 인터뷰에서 DP 문제를 접근하는 사고 방식 익히기

코딩 테스트 및 인터뷰에서는 시간 내에 DP 문제를 풀어야 합니다.

• 빠르게 접근하는 연습이 필요
• 가능한 한 1D DP 최적화

💡 면접 질문 예제

Q1: "계단 오르기 문제를 O(1) 공간으로 해결할 수 있나요?"
A: 네, dp[i] = dp[i-1] + dp[i-2] 관계식을 활용하면 두 개의 변수만 사용하여 해결 가능합니다.

---

📌 3️⃣ 제한 시간이 짧을 때 메모이제이션 vs 바텀업 선택하기

🔹 선택 기준

방식	장점	단점	메모리 사용량	추천 상황
메모이제이션 (탑다운)	코드가 직관적, 재귀 기반	콜스택 부담, 오버헤드 있음	O(n)	부분 문제 개수가 적을 때
바텀업 (반복문)	성능이 빠름, O(1) 공간 가능	코드가 직관적이지 않음	O(1) 또는 O(n)	부분 문제가 많을 때

💡 예제: 피보나치 수열

• 메모이제이션 (Top-Down)

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}  # 안전한 초기화

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

• 바텀업 (Bottom-Up)

def fib_bottom_up(n):
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

---

📌 4️⃣ 면접 대비 DP 연습 사이트 추천

백준(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/