DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략

들어가며

DP 문제는 상태를 어떻게 정의할지와 점화식을 세우는 연습이 중요합니다. 아래 문제들은 같은 상황을 Bottom-Up(테이블을 앞에서부터 채움)과 Top-Down(재귀와 메모)으로 모두 풀어 보며, 전이 관계를 익히는 것을 목표로 합니다.

---

1. 문제 1: 1로 만들기

문제 설명

정수 N을 1로 만들려고 합니다. 다음 세 연산을 사용할 수 있습니다:

1. N이 3으로 나누어떨어지면 3으로 나눔
2. N이 2로 나누어떨어지면 2로 나눔
3. 1을 뺌

최소 연산 횟수를 구하세요.

Bottom-Up 풀이

dp[i]를 “정수 i를 1로 만드는 최소 연산 횟수”로 두면, i에 도달하는 방법은 i-1에서 1을 빼거나, 나누어떨어질 때는 i/2 또는 i/3에서 한 번에 오는 세 가지입니다. 작은 수부터 채워 올리면 각 dp[i]를 O(1)로 갱신할 수 있습니다.

def make_one(n):
    """
    dp[i] = i를 1로 만드는 최소 연산 횟수
    """
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + 1
        
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
        
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
    
    return dp[n]

print(make_one(10))  # 3 (10 → 9 → 3 → 1)

Top-Down 풀이

def make_one_recursive(n, memo=None):
    if memo is None:
        memo = {}
    
    if n == 1:
        return 0
    
    if n in memo:
        return memo[n]
    
    result = make_one_recursive(n - 1, memo) + 1
    
    if n % 2 == 0:
        result = min(result, make_one_recursive(n // 2, memo) + 1)
    
    if n % 3 == 0:
        result = min(result, make_one_recursive(n // 3, memo) + 1)
    
    memo[n] = result
    return result

print(make_one_recursive(10))  # 3

---

2. 문제 2: 편집 거리 (Edit Distance)

문제 설명

문자열 s1을 s2로 만드는 최소 연산 수를 구하세요.

• 삽입, 삭제, 교체 가능

풀이

def edit_distance(s1, s2):
    """
    dp[i][j] = s1[:i]를 s2[:j]로 만드는 최소 연산 수
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 초기값
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    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]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # 삭제
                    dp[i][j-1] + 1,    # 삽입
                    dp[i-1][j-1] + 1   # 교체
                )
    
    return dp[m][n]

print(edit_distance("horse", "ros"))  # 3
print(edit_distance("intention", "execution"))  # 5

---

3. 문제 3: 동전 문제

문제 설명

주어진 동전으로 amount를 만드는 최소 동전 개수를 구하세요.

풀이

def coin_change(coins, amount):
    """
    dp[i] = i원을 만드는 최소 동전 개수
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
print(coin_change(coins, 11))  # 3 (5+5+1)
print(coin_change(coins, 3))   # 2 (2+1)

경로 추적

def coin_change_with_path(coins, amount):
    dp = [float('inf')] * (amount + 1)
    parent = [-1] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                parent[i] = coin
    
    if dp[amount] == float('inf'):
        return -1, []
    
    path = []
    current = amount
    while current > 0:
        path.append(parent[current])
        current -= parent[current]
    
    return dp[amount], path

count, path = coin_change_with_path([1, 2, 5], 11)
print(f"최소 개수: {count}, 동전: {path}")  # 3, [5, 5, 1]

---

4. 문제 4: 최장 증가 부분 수열 (LIS)

문제 설명

배열에서 증가하는 부분 수열의 최대 길이를 구하세요.

O(n²) 풀이

def lis(arr):
    """
    dp[i] = i번째까지의 LIS 길이
    """
    n = len(arr)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 ([2, 3, 7, 101])

O(n log n) 풀이

from bisect import bisect_left

def lis_optimized(arr):
    """
    이진 탐색으로 최적화
    """
    tails = []
    
    for num in arr:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

print(lis_optimized([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

---

5. 문제 5: 배낭 문제 (Knapsack)

문제 설명

무게 제한이 W인 배낭에 최대 가치를 담으세요.

풀이

def knapsack(weights, values, W):
    """
    dp[i][w] = i번째까지 고려, 무게 w일 때 최대 가치
    """
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
W = 7
print(knapsack(weights, values, W))  # 9 (3+4 무게, 4+5 가치)

공간 최적화

def knapsack_optimized(weights, values, W):
    """
    1D 배열로 공간 최적화
    """
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

print(knapsack_optimized(weights, values, W))  # 9

---

실전 팁

DP 문제 접근 5단계

# 1. 부분 문제 정의
# dp[i] = "i번째까지의 최적해"

# 2. 점화식 세우기
# dp[i] = f(dp[i-1], dp[i-2], ...)

# 3. 초기값 설정
# dp[0] = ..., dp[1] = ...

# 4. 구현 선택
# Top-Down (재귀) vs Bottom-Up (반복)

# 5. 최적화
# 공간 최적화, 불필요한 계산 스킵

디버깅 팁

def debug_dp(dp):
    """DP 테이블 출력"""
    for i, row in enumerate(dp):
        print(f"dp[{i}]: {row}")

# 사용
dp = [[0] * 5 for _ in range(3)]
debug_dp(dp)

---

정리

핵심 요약

1. 접근법: 부분 문제 → 점화식 → 초기값 → 구현
2. 패턴: 1D DP, 2D DP, 배낭, LCS, LIS
3. 최적화: 공간(1D 배열), 시간(이진 탐색)
4. 연습: 많이 풀어보기

추천 문제

백준:

• 1463번: 1로 만들기
• 2293번: 동전 1
• 9251번: LCS
• 12865번: 평범한 배낭

프로그래머스:

• N으로 표현
• 정수 삼각형

다음 단계

• 동적 프로그래밍 기초
• DP 패턴
• 정렬 문제

---

관련 글

• 그리디 알고리즘 |
• 백트래킹 | 모든 경우의 수 탐색 알고리즘 완벽 정리
• 알고리즘 시리즈 전체 보기
• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
• 해시 테이블 | O(1) 탐색 자료구조 완벽 정리