DP 실전 문제 풀이: 1로 만들기·편집 거리·동전·LIS·배낭으로 점화식 연습
이 글의 핵심
개념을 알아도 실제 문제 앞에서 dp[i]를 어떻게 정의할지 막히는 경우가 많습니다. 같은 문제를 두 방식으로 풀어 전이 관계가 어떻게 드러나는지 비교하고, 배낭 문제의 공간 최적화, DP 문제 접근 5단계, 테이블을 출력해 점화식 오류를 찾는 디버깅 요령까지 정리합니다.
시리즈 안내
들어가며
DP 문제는 상태를 어떻게 정의할지와 점화식을 세우는 연습이 중요합니다. 아래 문제들은 같은 상황을 Bottom-Up(테이블을 앞에서부터 채움)과 Top-Down(재귀와 메모)으로 모두 풀어 보며, 전이 관계를 익히는 것을 목표로 합니다.
문제 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)로 갱신할 수 있습니다.
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)이 문제는 DP가 왜 필요한지를 보여 주는 대표적인 예입니다. 직관적으로는 “3으로 나눌 수 있으면 나누고, 아니면 2로, 아니면 1을 빼는” 그리디가 맞을 것 같지만, 10에서 그리디로 가면 10 → 5 → 4 → 2 → 1로 4번이 걸립니다. 정답은 먼저 1을 빼서 9로 만든 뒤 3으로 두 번 나누는 3번입니다. “지금 가장 좋아 보이는 선택”이 전체 최적을 보장하지 않을 때, 모든 선택지의 결과를 작은 수부터 기록해 두고 비교하는 것이 DP의 발상입니다.
Bottom-Up에서 dp[i] = dp[i - 1] + 1을 먼저 넣는 이유는 1을 빼는 연산이 항상 가능하기 때문입니다. 이 값을 기본으로 두고 2나 3으로 나누어떨어질 때만 더 작은 값으로 갱신하면 조건 분기가 단순해집니다. dp[1] = 0은 배열을 0으로 초기화한 덕분에 따로 쓰지 않아도 되며, 반복을 2부터 시작하는 것도 그 때문입니다. 시간과 공간 모두 O(N)이라 N이 백만이어도 충분히 빠릅니다.
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)) # 3Top-Down은 점화식을 그대로 재귀로 옮겨 쓰기 때문에 “n을 1로 만드는 방법은 세 가지 중 최솟값”이라는 생각의 흐름이 코드에 그대로 드러납니다. memo가 없다면 같은 수를 여러 경로에서 반복 계산해 호출 횟수가 폭발하는데, 한 번 계산한 결과를 저장하면 각 수는 한 번만 계산됩니다. 기본 인자를 memo={}로 쓰지 않고 None으로 받은 것도 의도된 선택입니다. 파이썬의 기본 인자는 함수 정의 시점에 한 번만 만들어져 모든 호출이 같은 딕셔너리를 공유하므로, 테스트 케이스마다 결과가 섞이는 버그의 원인이 됩니다(이 문제에서는 결과가 같아 드러나지 않지만, 입력에 따라 답이 달라지는 문제에서는 치명적입니다).
실제 코딩 테스트에서 이 재귀 버전을 제출하면 흔히 겪는 문제가 있습니다. make_one_recursive(n - 1)이 n번 중첩되므로 N이 1,000을 넘으면 파이썬 기본 재귀 한도에 걸려 RecursionError: maximum recursion depth exceeded가 납니다. sys.setrecursionlimit(10**6)으로 한도를 올릴 수는 있지만, 채점 환경에 따라 실제 스택 메모리가 부족해 프로세스가 그냥 종료되기도 합니다. 깊이가 입력 크기에 비례하는 DP는 Bottom-Up으로 쓰는 것이 안전하고, Top-Down은 상태 공간이 넓지만 실제로 방문하는 상태가 일부뿐인 문제(예: 큰 수를 반씩 줄여 가는 문제)에서 진가를 발휘합니다. functools.lru_cache(maxsize=None)를 쓰면 메모 딕셔너리를 직접 관리하지 않아도 됩니다.
문제 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")) # 52차원 DP에서 가장 중요한 것은 dp[i][j]의 의미를 접두사(prefix) 로 정의하는 것입니다. s1의 앞 i글자를 s2의 앞 j글자로 바꾸는 최소 비용이라고 두면, 마지막 글자끼리만 비교해서 문제를 한 칸 작은 문제로 줄일 수 있습니다. 마지막 글자가 같으면 비용 없이 dp[i-1][j-1]을 그대로 가져오고, 다르면 세 가지 중 하나를 합니다. s1의 마지막 글자를 삭제하면 dp[i-1][j], s2의 마지막 글자를 s1 끝에 삽입하면 dp[i][j-1], 교체하면 dp[i-1][j-1]에 각각 1을 더합니다. 초기값 dp[i][0] = i는 “빈 문자열로 만들려면 i글자를 모두 지워야 한다”, dp[0][j] = j는 “빈 문자열에서 j글자를 모두 삽입해야 한다”는 뜻입니다.
인덱스가 헷갈리는 부분은 dp가 (m+1) × (n+1) 크기이고 문자열은 0부터 시작한다는 점입니다. dp[i][j]를 계산할 때 비교하는 글자는 s1[i]가 아니라 s1[i-1]입니다. 여기서 한 칸 밀리면 에러 없이 틀린 답이 나오므로, “horse”/“ros”처럼 답을 아는 작은 예제로 테이블을 직접 출력해 보는 것이 가장 빠른 검증 방법입니다. 이 알고리즘은 맞춤법 검사기의 추천 단어, diff 도구, DNA 서열 비교에 쓰이는 레벤슈타인 거리와 같습니다.
문제 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)동전 문제도 그리디가 실패하는 대표적인 예입니다. 한국 화폐처럼 동전 단위가 서로 배수 관계라면 큰 동전부터 쓰는 그리디가 항상 최적이지만, 동전이 [1, 3, 4]이고 6원을 만들 때 그리디는 4+1+1로 3개를 쓰고 정답은 3+3으로 2개입니다. 코딩 테스트에서 동전 단위가 임의로 주어진다면 DP를 쓰는 것이 안전합니다.
dp를 float('inf')로 초기화하는 것은 “아직 만들 수 없음”을 표현하기 위해서입니다. 0으로 초기화하면 min이 항상 0을 고르게 되어 모든 답이 틀어집니다. 같은 동전을 여러 번 쓸 수 있으므로 금액 i를 바깥 루프로 두고 모든 동전을 시도하는 구조인데, 이것이 뒤에 나오는 0/1 배낭과 결정적으로 다른 점입니다. 시간 복잡도는 O(amount × 동전 수)입니다. 참고로 추천 문제의 백준 2293번 “동전 1”은 최소 개수가 아니라 경우의 수를 세는 문제라 점화식이 dp[i] += dp[i - coin]이고, 순서만 다른 조합을 중복으로 세지 않으려면 동전을 바깥 루프에 두어야 합니다. 최소 개수 문제는 2294번 “동전 2”입니다. 이름이 비슷한 두 문제를 같은 코드로 풀려다 틀리는 경우가 매우 흔합니다.
경로 추적
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, [1, 5, 5]역추적은 DP 문제에서 “최적값”뿐 아니라 “최적해 자체”를 요구할 때 쓰는 일반적인 기법입니다. dp[i]를 갱신할 때 어떤 선택으로 그 값이 나왔는지를 parent[i]에 함께 기록해 두고, 계산이 끝난 뒤 목표에서 거꾸로 따라갑니다. 11원은 마지막에 1원을 써서 10원에서 왔고, 10원은 5원을 써서 5원에서, 5원은 5원 하나로 0원에서 왔으므로 경로는 [1, 5, 5]입니다. 비교 조건이 <(엄격한 부등호)라서 같은 개수의 다른 조합이 있을 때 먼저 확인한 동전이 선택되며, 동전 순서를 바꾸면 [5, 5, 1]처럼 다른 순서의 답이 나올 수 있습니다. 문제에서 특정 순서나 사전순으로 가장 앞선 답을 요구한다면 동전 정렬 순서와 비교 조건을 그에 맞게 정해야 합니다.
문제 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])여기서 dp[i]의 정확한 의미는 “i번째까지의 LIS”가 아니라 “i번째 원소로 끝나는 LIS의 길이” 입니다. 이 차이가 중요한데, “i번째까지”로 정의하면 이전 수열의 마지막 값이 무엇인지 알 수 없어 다음 원소를 이어 붙일 수 있는지 판단할 수 없습니다. “i로 끝난다”고 정해 두면 arr[j] < arr[i]인 모든 j의 값에 1을 더한 것 중 최댓값이 되고, 전체 답은 dp 전체의 최댓값(max(dp))입니다. 마지막에 dp[-1]을 반환하는 실수를 하면 마지막 원소로 끝나는 LIS만 구하게 되어 틀립니다. 원소가 수천 개까지는 O(n²)으로 충분하지만, 10만 개가 넘으면 시간 초과가 나므로 아래의 O(n log n) 방법이 필요합니다.
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])) # 4tails[k]는 “길이가 k+1인 증가 수열들 중 가장 작은 마지막 값”을 저장합니다. 마지막 값이 작을수록 뒤에 더 많은 수를 이어 붙일 수 있으므로, 같은 길이라면 작은 값을 유지하는 것이 항상 유리합니다. 새 수가 들어오면 tails에서 그 수 이상인 첫 위치를 이진 탐색으로 찾아 교체하고, 모든 값보다 크면 끝에 붙여 길이를 늘립니다. tails는 항상 정렬된 상태이므로 이진 탐색이 가능합니다.
주의할 점은 tails 배열 자체가 실제 LIS가 아니라는 것입니다. 예제를 끝까지 돌리면 tails는 [2, 3, 7, 18]이 되는데, 길이는 맞지만 이는 교체 과정에서 남은 값일 뿐이고 입력에 따라서는 원래 순서상 존재하지 않는 조합이 되기도 합니다. 실제 수열이 필요하면 각 원소가 들어간 위치를 따로 기록한 뒤 역추적해야 합니다. 또 bisect_left는 “엄격하게 증가”하는 수열, bisect_right는 “같거나 증가(비감소)“하는 수열의 길이를 구하므로, 문제 조건에 같은 값이 허용되는지 확인해서 골라야 합니다.
문제 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 가치)0/1 배낭은 각 물건을 넣거나 넣지 않거나 둘 중 하나만 고를 수 있는 문제입니다. dp[i][w]를 “앞의 i개 물건만 고려하고 배낭 용량이 w일 때의 최대 가치”로 두면, i번째 물건을 넣지 않으면 dp[i-1][w], 넣으면 그 물건의 무게만큼 용량을 뺀 dp[i-1][w - weights[i-1]]에 가치를 더한 값이 됩니다. 두 경우 모두 이전 행(i-1)만 참조한다는 점이 “각 물건은 한 번만 쓴다”는 조건을 보장합니다. 가치당 무게가 좋은 물건부터 담는 그리디는 여기서도 실패합니다. 이 예제에서 가치/무게 비율이 가장 높은 것은 무게 5짜리(1.4)인데, 그것을 먼저 담으면 남은 용량 2에 무게 1짜리만 들어가 가치 8이 되어 정답 9보다 작습니다.
시간과 공간이 모두 O(n × W)라서 W가 수백만 이상이면 메모리가 부족해집니다. 이 복잡도는 입력 크기가 아니라 W라는 값에 비례하는 “의사 다항 시간”이라, 무게가 10억 단위로 주어지는 문제에서는 이 방법을 쓸 수 없고 가치를 기준으로 상태를 잡는 등 다른 정의가 필요합니다.
공간 최적화
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)) # 92차원 버전에서 dp[i]행은 dp[i-1]행만 참조하므로, 배열 하나를 계속 덮어쓰는 방식으로 공간을 O(W)로 줄일 수 있습니다. 여기서 가장 중요한 것은 용량을 큰 값에서 작은 값으로 거꾸로 순회한다는 점입니다. dp[w]를 갱신할 때 참조하는 dp[w - weights[i]]는 w보다 작은 인덱스이므로, 큰 쪽부터 갱신하면 그 값은 아직 이번 물건이 반영되지 않은 “이전 행”의 값으로 남아 있습니다. 반대로 작은 쪽부터 순회하면 방금 이번 물건을 넣어 갱신한 값을 다시 참조하게 되어 같은 물건을 여러 번 넣는 계산이 됩니다. 이 순회 방향 하나로 0/1 배낭과 “무한 배낭”(같은 물건 여러 번 사용 가능, 앞의 동전 문제와 같은 구조)이 갈립니다.
제가 처음 이 최적화를 배울 때 가장 많이 틀린 부분도 이 순회 방향이었습니다. 2차원 코드에서 1차원으로 옮기면서 range(weights[i], W + 1)로 정방향 루프를 쓰면, 작은 예제에서는 우연히 답이 맞다가 제출하면 틀리는 경우가 많아 원인을 찾기 어렵습니다. 공간 최적화 버전을 쓸 때는 2차원 버전과 결과를 몇 가지 입력으로 비교해 보는 습관이 도움이 됩니다. 또 1차원 버전은 어떤 물건을 골랐는지 역추적할 정보가 사라지므로, 선택한 물건 목록이 필요한 문제라면 2차원 테이블을 유지해야 합니다.
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. 최적화
# 공간 최적화, 불필요한 계산 스킵이 다섯 단계 중 실제로 가장 오래 걸리는 것은 1단계입니다. 상태를 정의할 때 스스로에게 던질 질문은 “이 문제를 한 단계 작은 문제로 줄이려면 무엇을 알아야 하는가”입니다. LIS에서 “i로 끝나는”이라는 조건이 필요했던 것처럼, 다음 결정을 내리는 데 필요한 정보가 상태에 모두 들어 있어야 합니다. 정보가 부족하면 점화식을 세울 수 없고, 반대로 필요 없는 정보까지 상태에 넣으면 테이블이 너무 커져 시간과 메모리가 초과됩니다. 점화식이 떠오르지 않는다면 대개 상태 정의를 바꿔야 한다는 신호입니다.
3단계의 초기값도 흔한 오답 원인입니다. 최솟값을 구하는 문제는 “불가능”을 무한대로, 최댓값 문제는 음의 무한대나 0으로, 경우의 수 문제는 dp[0] = 1(아무것도 고르지 않는 방법 한 가지)로 두는 것이 일반적이며, 어느 것을 쓰느냐에 따라 답이 완전히 달라집니다.
작은 입력으로 테이블 비교하기
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)DP 코드가 틀렸을 때 가장 효과적인 디버깅 방법은 답을 손으로 계산할 수 있는 아주 작은 입력에 대해 테이블 전체를 출력하고, 손으로 채운 표와 한 칸씩 비교하는 것입니다. 첫 번째로 어긋나는 칸이 점화식이나 초기값이 잘못된 지점을 정확히 가리킵니다. 예제에서 2차원 리스트를 [[0] * 5 for _ in range(3)]로 만든 것도 중요합니다. [[0] * 5] * 3처럼 쓰면 세 행이 같은 리스트 객체를 공유해서, 한 칸을 바꾸면 세 행의 같은 열이 모두 바뀌는 파이썬 초보자의 대표적인 버그가 생깁니다. 또 브루트 포스 풀이(모든 경우를 시도하는 느린 코드)를 따로 짜서 작은 무작위 입력들로 DP 결과와 비교하는 방법도 코딩 테스트 연습에서 매우 효과적입니다.
추천 문제와 동전 문제의 반복 순서
동전 1(2293번)처럼 “경우의 수”를 세는 문제는 이중 반복문의 순서가 곧 답의 의미입니다. 동전을 바깥 루프에 두면 1+2와 2+1을 같은 조합으로 한 번만 세고, 금액을 바깥 루프에 두면 순서가 다른 것을 서로 다른 경우로 세게 됩니다. 문제가 조합을 묻는지 순열을 묻는지 먼저 확인하고 루프 순서를 정하세요. 이 문제는 메모리 제한도 빡빡해서 2차원 표 대신 1차원 배열을 써야 통과합니다.
백준:
프로그래머스:
점화식 세우는 법이 아직 막막하다면 동적 프로그래밍 기초와 DP 패턴으로 돌아가 1차원·2차원 패턴을 먼저 익히는 것이 좋습니다.
같이 보면 좋은 글
- 그리디 알고리즘
- 백트래킹: 가지치기로 모든 경우의 수를 줄이는 방법과 N-Queen·순열·조합
- 알고리즘 시리즈 전체 보기
- 배열과 연결 리스트
- 스택과 큐: LIFO·FIFO 구현과 괄호 검사·BFS 같은 코딩 테스트 활용
- 해시 테이블
- 동적 프로그래밍(DP)
- DP 패턴 | 동적 프로그래밍 유형별 풀이 전략
- 정렬 문제 풀이
자주 묻는 질문 (FAQ)
Q. 동전 문제에서 최소 개수뿐 아니라 어떤 동전을 썼는지도 알 수 있나요?
A. dp 값을 갱신할 때마다 그 금액을 만든 마지막 동전을 parent 배열에 기록해 두면 됩니다. 계산이 끝난 뒤 목표 금액에서 parent에 적힌 동전을 빼 가며 0이 될 때까지 따라가면 실제 사용한 동전 목록이 나옵니다. dp[amount]가 무한대로 남아 있으면 만들 수 없는 금액이므로, 경로를 따라가기 전에 먼저 이 경우를 걸러야 합니다.