[2026] DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
![[2026] DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략](/og/s/algorithm-series-14-dp-problems.webp)
이 글의 핵심
DP 실전 문제: 코딩 테스트 DP 문제 풀이 전략. 1로 만들기·편집 거리 (Edit Distance).
들어가며
DP 문제는 상태를 어떻게 정의할지와 점화식을 세우는 연습이 중요합니다. 아래 문제들은 같은 상황을 Bottom-Up(테이블을 앞에서부터 채움)과 Top-Down(재귀와 메모)으로 모두 풀어 보며, 전이 관계를 익히는 것을 목표로 합니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 문제 1: 1로 만들기
문제 설명
정수 N을 1로 만들려고 합니다. 다음 세 연산을 사용할 수 있습니다:
- N이 3으로 나누어떨어지면 3으로 나눔
- N이 2로 나누어떨어지면 2로 나눔
- 1을 뺌 최소 연산 횟수를 구하세요.
Bottom-Up 풀이
dp[i]를 “정수 i를 1로 만드는 최소 연산 횟수”로 두면, i에 도달하는 방법은 i-1에서 1을 빼거나, 나누어떨어질 때는 i/2 또는 i/3에서 한 번에 오는 세 가지입니다. 작은 수부터 채워 올리면 각 dp[i]를 O(1)로 갱신할 수 있습니다.
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 풀이
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)) # 32. 문제 2: 편집 거리 (Edit Distance)
문제 설명
문자열 s1을 s2로 만드는 최소 연산 수를 구하세요.
- 삽입, 삭제, 교체 가능
풀이
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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")) # 53. 문제 3: 동전 문제
문제 설명
주어진 동전으로 amount를 만드는 최소 동전 개수를 구하세요.
풀이
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)경로 추적
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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²) 풀이
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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) 풀이
다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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])) # 45. 문제 5: 배낭 문제 (Knapsack)
문제 설명
무게 제한이 W인 배낭에 최대 가치를 담으세요.
풀이
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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 가치)공간 최적화
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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단계
아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 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. 최적화
# 공간 최적화, 불필요한 계산 스킵디버깅 팁
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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)정리
핵심 요약
- 접근법: 부분 문제 → 점화식 → 초기값 → 구현
- 패턴: 1D DP, 2D DP, 배낭, LCS, LIS
- 최적화: 공간(1D 배열), 시간(이진 탐색)
- 연습: 많이 풀어보기
추천 문제
백준: