동적 계획법 2 - 배낭·LCS·구간
이 장에서 배우는 것
앞 장에서 상태를 정하고 점화식으로 연결하는 방법을 익혔다. 이번에는 선택한 물건의 무게, 두 기록을 읽은 위치, 처리할 구간의 양 끝처럼 여러 조건이 함께 필요한 문제를 다룬다. 계산식을 외우기보다 각 칸이 무엇을 뜻하는지 정하고, 그 뜻이 유지되는 순서로 표를 채우는 데 집중한다.
같은 점화식도 모든 표를 보관할 때와 일부 행만 보관할 때 구현 방법이 달라진다. 정답의 값만 필요한지, 실제 선택까지 출력해야 하는지도 구분한다. 작은 입력에서는 가능한 선택을 모두 만들어 빠른 풀이와 비교한다.
- 각 물건을 한 번만 고르는 0/1 배낭 문제의 상태와 갱신 방향을 설명한다.
- 최장 공통 부분 수열(longest common subsequence, LCS)의 길이를 구하고 실제 수열을 복원한다.
- 표의 의존 관계를 살펴 공간을 줄이고, 줄인 정보 때문에 생기는 제약을 이해한다.
- 선택 개수와 구간의 양 끝처럼 필요한 조건에 따라 상태 차원을 늘린다.
- 배낭과 LCS를 작은 입력의 전수 탐색 결과와 대조한다.
문제 상황
작은 작업장에서 출장용 공구 가방을 꾸린다. 공구마다 무게와 현장에서의 활용 점수가 있다. 같은 공구는 하나씩만 준비되어 있고, 가방에는 정해진 무게까지만 넣을 수 있다. 목표는 허용 무게 안에서 활용 점수의 합을 가장 크게 만드는 것이다. 공구를 쪼개서 넣을 수 없으므로 무게당 점수만 보고 고르는 방법으로는 답을 보장할 수 없다.
예시 공구의 무게와 점수는 차례대로 (2, 6), (3, 7), (4, 9)이고 허용 무게는 5다. 세 번째 공구 하나를 넣으면 점수는 9지만, 첫 번째와 두 번째 공구를 함께 넣으면 무게 5에 점수 13을 얻는다. 여기서 무게는 정수 단위이고, 점수는 0 이상이라고 정한다.
다른 업무에서는 두 작업 기록의 공통 흐름을 확인한다. 기록에 등장한 작업 종류를 한 글자로 나타냈다고 하자. 두 기록이 ABAC와 BABC일 때, 일부 글자를 지워 양쪽에 남길 수 있는 가장 긴 기록을 찾는다. 지우고 남은 글자의 순서는 바꿀 수 없다. ABC는 두 기록에 모두 남길 수 있으며 길이는 3이다.
마지막으로 인접한 포장 묶음을 합치는 상황을 살펴본다. 한 번에 이웃한 두 묶음만 합칠 수 있고, 합칠 때마다 두 묶음의 크기 합만큼 작업량이 든다. 이 문제는 앞에서부터 몇 개를 보았는지만으로 부족하다. 어느 구간을 하나로 만들고 있는지까지 상태에 넣어야 한다.
한 번씩 고르는 배낭과 공간 줄이기
물건을 넣지 않는 경우와 넣는 경우
0/1 배낭에서 0과 1은 각 물건을 고르지 않거나 한 번 고른다는 뜻이다. 물건 수를 n, 허용 무게를 C라 하자. 상태 D[i][c]를 앞의 i개 물건만 고려하고 허용 무게가 c일 때 얻는 최대 점수로 정의한다. 정확히 c를 채울 필요는 없다. 아무것도 고르지 않아도 되므로 D[0][c]는 모두 0이다.
i번째 물건의 무게가 w, 점수가 v라면 선택은 두 가지다. 넣지 않으면 D[i-1][c]이고, 넣으려면 c가 w 이상이어야 하며 D[i-1][c-w] + v가 된다. 두 값 중 큰 값을 택한다. 두 후보 모두 앞의 i-1개 물건에서 출발하므로 현재 물건을 중복 사용하지 않는다.
c < w일 때:
D[i][c] = D[i-1][c]
c >= w일 때:
D[i][c] = max(D[i-1][c], D[i-1][c-w] + v)| 고려한 물건 | 무게 0, 1 | 무게 2, 3 | 무게 4, 5 |
|---|---|---|---|
| 없음 | 0, 0 | 0, 0 | 0, 0 |
| (2, 6) | 0, 0 | 6, 6 | 6, 6 |
| (2, 6), (3, 7) | 0, 0 | 6, 7 | 7, 13 |
| 세 물건 모두 | 0, 0 | 6, 7 | 9, 13 |
두 번째 물건까지 고려한 무게 5의 칸을 손으로 계산해 보자. 두 번째 물건을 빼면 이전 행의 무게 5에서 6점을 얻는다. 넣으면 이전 행의 무게 2에서 얻은 6점에 현재 점수 7점을 더한다. 따라서 이 칸은 13이다. 마지막 물건까지 본 뒤에도 13보다 좋은 후보는 없다.
정확성은 물건 수에 대한 귀납으로 설명할 수 있다. 물건이 없으면 최대 점수는 0이다. 앞의 i-1개에 대한 표가 맞다고 가정하면, 앞의 i개에서 가능한 모든 선택은 i번째 물건을 포함하거나 포함하지 않는 두 부류로 나뉜다. 각 부류의 최댓값을 올바른 이전 상태에서 얻으므로 둘 중 큰 값도 올바르다.
한 줄로 줄이면 갱신 순서가 조건이 된다
현재 행은 바로 이전 행만 읽는다. 따라서 점수만 필요하다면 길이 C+1의 리스트 하나로 줄일 수 있다. 다만 같은 리스트에 쓰면서 읽으므로 허용 무게를 큰 쪽에서 작은 쪽으로 순회해야 한다. 무게가 양수일 때 c-w는 c보다 작다. 큰 쪽부터 갱신하면 그 작은 칸에는 아직 이전 물건까지만 고려한 값이 남아 있다.
예를 들어 물건이 (2, 6) 하나이고 허용 무게가 4일 때 작은 쪽부터 갱신하면 dp[2]가 먼저 6이 된다. 이어 dp[4]를 계산할 때 그 6을 다시 읽어 12를 만든다. 물건 하나를 두 번 쓴 셈이다. 내림차순에서는 dp[4]가 아직 0인 dp[2]를 읽으므로 6이 된다.
이 구현의 반복 불변식은 현재 물건을 처리하는 도중, 이미 지나온 큰 용량 칸은 현재 물건까지의 답이고 아직 방문하지 않은 작은 용량 칸은 이전 물건까지의 답이라는 것이다. 계산에 필요한 작은 칸이 이전 행의 의미를 유지하므로 두 차원 표와 같은 답을 얻는다.
표를 모두 보관하면 시간은 O(nC), 공간도 O(nC)다. 한 줄로 줄이면 시간은 같고 보조 공간은 O(C)다. 이 시간은 C의 수치에 비례한다. 무게 한도의 자릿수가 짧더라도 그 값 자체가 매우 크면 계산량이 커질 수 있다. 완성 코드에서는 양의 정수 무게와 0 이상인 정수 점수를 입력 조건으로 사용한다.
두 기록을 맞추는 LCS와 복원
부분 수열은 중간을 건너뛸 수 있다
부분 수열은 원래 순서를 유지하면서 일부 원소를 지운 결과다. 연속해서 붙어 있을 필요는 없다. ABAC에서 첫 번째 A, 두 번째 B, 마지막 C를 남기면 ABC가 된다. 반면 CBA처럼 순서를 뒤집을 수는 없다. 두 기록의 길이를 각각 n, m이라 하자.
L[i][j]를 첫 기록의 앞 i글자와 두 번째 기록의 앞 j글자의 LCS 길이로 정의한다. 어느 한쪽이 빈 기록이면 공통으로 남길 글자가 없으므로 첫 행과 첫 열은 0이다. 마지막 글자가 같으면 두 글자를 함께 남겨 L[i-1][j-1] + 1을 얻는다. 다르면 한쪽 마지막 글자를 제외한 두 상태 중 큰 값을 고른다.
a[i-1] == b[j-1]일 때:
L[i][j] = L[i-1][j-1] + 1
그렇지 않을 때:
L[i][j] = max(L[i-1][j], L[i][j-1])| 첫 기록의 접두부 | 빈 기록, B | BA, BAB | BABC |
|---|---|---|---|
| 빈 기록 | 0, 0 | 0, 0 | 0 |
| A | 0, 0 | 1, 1 | 1 |
| AB | 0, 1 | 1, 2 | 2 |
| ABA | 0, 1 | 2, 2 | 2 |
| ABAC | 0, 1 | 2, 2 | 3 |
마지막 칸에서는 C가 같으므로 왼쪽 위의 2에 1을 더한다. ABA와 BAB를 비교하는 칸에서는 A와 B가 다르다. 첫 기록의 A를 제외한 AB와 BAB, 두 번째 기록의 B를 제외한 ABA와 BA의 답이 모두 2이므로 이 칸도 2다.
정확성은 접두부 길이의 합에 대한 귀납으로 보인다. 마지막 글자가 다르면 공통 부분 수열의 대응에서 양쪽 마지막 위치를 함께 사용할 수 없다. 따라서 적어도 한쪽 마지막 위치를 제외한 상태에 답이 들어 있다. 마지막 글자가 같으면 양쪽 끝을 함께 쓰는 최적해를 잡을 수 있다. 최적해가 끝 위치를 쓰지 않았다면 마지막 대응을 같은 글자인 끝 위치로 옮길 수 있고, 양쪽 끝을 모두 쓰지 않은 채 더 붙일 수 있다면 기존 해는 최적이 아니다. 끝의 대응을 제거한 나머지는 왼쪽 위 상태의 최적 길이를 넘을 수 없다.
표를 거슬러 올라가 실제 기록을 만든다
길이만 출력하면 어떤 글자를 남겼는지 알 수 없다. 전체 표를 보관했다면 오른쪽 아래에서 시작해 선택을 되짚을 수 있다. 두 글자가 같으면 그 글자를 모으고 양쪽 위치를 하나씩 줄인다. 다르면 값이 큰 이웃으로 이동한다. 두 값이 같을 때는 위쪽으로 이동하기로 정해 결과를 일정하게 만든다.
예시에서는 C를 모은 뒤 ABA와 BAB 상태에 도착한다. 이웃의 값이 같으므로 위로 이동해 AB와 BAB를 비교한다. 이제 B를 모으고, 이어 A를 모은다. 수집 순서는 C, B, A이므로 마지막에 뒤집어 ABC를 만든다. 동점 처리 규칙은 가능한 답 하나를 고를 뿐, 사전순으로 가장 작은 답을 보장하지는 않는다.
복원 중에는 이미 모은 글자 수와 현재 칸의 LCS 길이의 합이 처음 구한 최적 길이와 같다. 같은 글자를 모으면 현재 길이가 1 줄고, 값이 같은 이웃으로만 이동할 때는 길이가 유지된다. 경계에 도착하면 남은 길이는 0이므로 모은 글자들이 최적 길이를 이룬다. 이동할 때 두 기록의 위치가 함께 뒤로 가므로 뒤집은 결과는 양쪽의 부분 수열이다.
전체 표의 시간과 공간은 O(nm)이며, 복원 자체는 O(n+m) 시간이다. 길이만 필요하다면 이전 행과 현재 행 두 개를 사용하고, 짧은 기록을 열에 놓아 보조 공간을 O(min(n, m)+1)로 줄인다. 현재 칸은 이전 행의 위쪽과 왼쪽 위, 현재 행의 왼쪽만 읽는다. 이 경우 왼쪽 값이 먼저 계산되어야 하므로 열은 왼쪽에서 오른쪽으로 진행한다.
공간을 줄인 표에는 과거 행이 남지 않는다. 따라서 아래의 두 행 구현만으로 같은 방식의 복원을 할 수는 없다. 완성 코드에서는 실제 기록을 구하는 함수와 길이만 구하는 함수를 따로 둔다. 두 함수의 결과도 전수 대조에서 함께 확인한다.
선택 조건과 구간에 맞춰 상태 늘리기
정확히 몇 개를 골랐는지도 기억한다
가방에 공구를 정확히 K개 넣어야 한다면 무게만으로는 부족하다. 같은 무게와 점수라도 지금까지 고른 개수가 다르면 남은 선택이 달라진다. 상태를 D[i][c][k], 즉 앞의 i개 물건에서 허용 무게 c 안으로 정확히 k개를 골랐을 때의 최대 점수로 늘린다.
선택하지 않는 후보는 D[i-1][c][k]이고, 선택하는 후보는 D[i-1][c-w][k-1] + v다. 이때 불가능한 상태를 0으로 놓으면 안 된다. 물건이 없는데 하나를 고른 상태까지 점수 0으로 가능하다고 오해하기 때문이다. k가 0인 상태만 0으로 두고 나머지는 None처럼 도달 불가를 구분하는 값으로 시작한다. 후보를 더하기 전에도 도달 가능한지 확인한다.
공간을 줄여 D[c][k]만 남긴다면 c와 k를 모두 큰 쪽부터 순회할 수 있다. 시간은 O(nCK), 공간은 O(CK)다. 상태 하나를 늘리면 저장량과 연산량도 그 범위만큼 늘어난다. 조건이 하나 추가될 때마다 무조건 차원을 늘리기보다, 그 조건을 기억하지 않고도 다음 선택을 올바르게 판단할 수 있는지 먼저 살핀다.
구간은 짧은 것부터 완성한다
포장 묶음의 크기가 [4, 2, 3]이라고 하자. 먼저 4와 2를 합치면 작업량은 6이고, 만들어진 6과 3을 합치면 9가 더 들어 총 15다. 먼저 2와 3을 합치면 5와 9가 들어 총 14다. 이웃한 묶음만 합친다는 조건 때문에 원래의 구간을 유지해야 한다.
F[l][r]를 l번부터 r번까지의 묶음을 하나로 만드는 최소 작업량으로 둔다. 마지막 합치기 직전에는 어느 경계 k를 사이에 둔 두 묶음이 남는다. 왼쪽 구간과 오른쪽 구간을 각각 만드는 작업량에 마지막 합치기 작업량을 더하면 된다. S(l, r)는 해당 구간의 원래 크기 합이다.
F[l][l] = 0
F[l][r] = min(
F[l][k] + F[k+1][r] + S(l, r)
for k in range(l, r)
)세 묶음의 경우 k=0이면 0+5+9=14이고, k=1이면 6+0+9=15다. 가능한 마지막 경계를 모두 고려하므로 더 작은 14를 고른다. 각 부분 구간이 최적으로 처리되지 않았다면 그 부분만 더 나은 방법으로 바꿀 수 있다. 따라서 전체 최적해의 마지막 경계도 이 점화식의 후보에 포함된다.
이 표는 행 번호 순서보다 구간 길이 순서로 채우기 쉽다. 길이 1을 먼저 정하고 2, 3으로 늘리면 모든 후보가 이미 계산한 짧은 구간을 읽는다. 구간 합을 누적 합으로 O(1)에 구한다고 할 때 상태 수는 O(n²), 상태마다 경계를 O(n)개 조사하므로 시간은 O(n³), 공간은 O(n²)다. 앞의 배낭처럼 최근 행만 읽는 구조가 아니므로 같은 방식으로 한 행만 남길 수는 없다.
완성 코드
다음 프로그램을 main.py로 저장한다. 입력 대기는 없으며 문자열을 io.StringIO에 담아 코딩 테스트식 읽기를 흉내 낸다. 배낭은 최대 점수를, LCS는 실제 수열과 길이를 구한다. 검증은 난수 없이 정해진 작은 입력 전체를 순회하므로 출력이 일정하다.
import io
from itertools import product
# 01. 각 물건을 한 번만 고르는 배낭
def knapsack(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)
return dp[capacity]
# 02. 전체 표를 보관하고 LCS 하나를 복원
def lcs_restore(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i, j = n, m
result = []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
result.append(a[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(result))
# 03. 두 행만 보관하는 LCS 길이 계산
def lcs_length(a, b):
if len(a) < len(b):
a, b = b, a
previous = [0] * (len(b) + 1)
for char in a:
current = [0] * (len(b) + 1)
for j in range(1, len(b) + 1):
if char == b[j - 1]:
current[j] = previous[j - 1] + 1
else:
current[j] = max(previous[j], current[j - 1])
previous = current
return previous[-1]
# 04. 모든 선택을 조사하는 배낭의 느린 정답
def brute_knapsack(items, capacity):
best = 0
for mask in range(1 << len(items)):
weight_sum = 0
value_sum = 0
for i, (weight, value) in enumerate(items):
if mask & (1 << i):
weight_sum += weight
value_sum += value
if weight_sum <= capacity:
best = max(best, value_sum)
return best
# 05. 주어진 문자열이 부분 수열인지 확인
def is_subsequence(candidate, text):
pos = 0
for char in text:
if pos < len(candidate) and candidate[pos] == char:
pos += 1
return pos == len(candidate)
# 06. 한쪽의 모든 부분 수열을 만드는 느린 정답
def brute_lcs_length(a, b):
best = 0
for mask in range(1 << len(a)):
candidate = "".join(
a[i] for i in range(len(a)) if mask & (1 << i)
)
if is_subsequence(candidate, b):
best = max(best, len(candidate))
return best
# 07. 정해진 작은 입력 전체를 대조
def verify():
item_types = ((1, 1), (1, 3), (2, 1), (2, 3))
knapsack_cases = 0
for size in range(4):
for items in product(item_types, repeat=size):
for capacity in range(5):
fast = knapsack(items, capacity)
slow = brute_knapsack(items, capacity)
if fast != slow:
raise AssertionError((items, capacity, fast, slow))
knapsack_cases += 1
words = [
"".join(chars)
for size in range(5)
for chars in product("AB", repeat=size)
]
lcs_cases = 0
for a in words:
for b in words:
restored = lcs_restore(a, b)
slow = brute_lcs_length(a, b)
valid = (
len(restored) == slow
and lcs_length(a, b) == slow
and is_subsequence(restored, a)
and is_subsequence(restored, b)
)
if not valid:
raise AssertionError((a, b, restored, slow))
lcs_cases += 1
return knapsack_cases, lcs_cases
# 08. 예시 입력과 결정적인 출력
def main():
source = io.StringIO(
"3 5\n"
"2 6\n"
"3 7\n"
"4 9\n"
"ABAC\n"
"BABC\n"
)
count, capacity = map(int, source.readline().split())
items = [
tuple(map(int, source.readline().split()))
for _ in range(count)
]
a = source.readline().rstrip("\n")
b = source.readline().rstrip("\n")
print("배낭 최대 점수:", knapsack(items, capacity))
restored = lcs_restore(a, b)
print("LCS 길이:", len(restored))
print("LCS 복원:", restored)
print("두 행 LCS 길이:", lcs_length(a, b))
knapsack_cases, lcs_cases = verify()
print(f"배낭 전수 대조: {knapsack_cases}건 통과")
print(f"LCS 전수 대조: {lcs_cases}건 통과")
if __name__ == "__main__":
main()
줄별 해설
주석 01에서 dp의 인덱스는 사용한 무게가 아니라 허용 무게다. 따라서 모든 칸을 0으로 시작해도 된다. range의 끝값은 포함되지 않으므로 weight - 1을 써서 정확히 weight인 용량까지 갱신한다. 물건이 허용 무게보다 무거우면 반복 범위가 비어 자연스럽게 건너뛴다.
주석 02의 표는 리스트 내포로 행을 각각 만든다. 첫 행과 첫 열을 비워 두어 i-1, j-1을 읽는 점화식을 그대로 옮긴다. 복원 반복문의 조건은 두 인덱스가 모두 양수인 동안이다. 어느 한쪽이 빈 접두부가 되면 더 모을 글자가 없다. 동점에서 위쪽을 고르는 규칙도 코드에 명시했다.
주석 03은 짧은 문자열이 b가 되도록 두 참조를 바꾼다. 각 행을 계산하기 전에 current를 새로 만들기 때문에 previous와 서로 다른 리스트다. 행이 끝난 뒤 previous = current로 방금 계산한 행을 다음 반복의 기준으로 삼는다. 빈 문자열에서도 길이 1인 초기 행이 남아 0을 반환한다.
주석 04의 mask는 물건을 고르는 모든 경우를 정수로 표현한다. 1 << i는 i번째 위치만 1인 값이고, 비트 단위 AND 연산 &로 해당 물건의 선택 여부를 검사한다. 물건이 n개면 각 위치의 선택이 두 가지이므로 2의 n제곱 가지가 생긴다. 각 경우에 모든 물건을 확인하여 시간은 O(n·2ⁿ)이다. 빠른 풀이의 점화식을 사용하지 않아 비교 기준으로 삼기 좋다.
주석 05는 text를 왼쪽부터 읽으며 candidate에서 다음에 필요한 글자를 찾는다. 같은 글자를 만나면 pos를 하나 늘린다. 가능한 가장 이른 위치에 대응시킬수록 뒤에 사용할 위치가 많이 남으므로 이 검사가 성립한다. 빈 candidate는 처음부터 끝까지 읽은 상태이므로 어떤 text에도 포함된 것으로 판단한다.
주석 06은 첫 기록에서 남길 위치를 모두 선택한다. 첫 기록의 부분 수열이라는 조건은 생성 과정에서 만족하고, 두 번째 기록의 부분 수열인지 별도로 검사한다. 각 후보를 만드는 데 O(n), 확인하는 데 O(m)이 들어 시간은 O(2ⁿ(n+m))이다. 후보 문자열과 검사에 필요한 보조 공간은 O(n)이다.
주석 07의 배낭 검증은 네 종류의 물건으로 길이 0부터 3까지 모든 나열을 만든다. 나열 수는 1+4+16+64=85개이고, 각각 허용 무게 0부터 4까지 검사하므로 425건이다. 같은 종류가 여러 번 등장해도 서로 다른 물건이다. 이런 입력은 내림차순 갱신이 각 물건의 사용 횟수를 지키는지도 확인한다.
LCS 검증은 A와 B로 만든 길이 0부터 4까지의 문자열을 사용한다. 문자열은 1+2+4+8+16=31개이고 순서 있는 쌍은 961개다. 복원한 결과의 길이가 느린 정답과 같은지, 양쪽의 부분 수열인지, 공간을 줄인 함수의 길이도 같은지 확인한다. 최적 수열이 여러 개일 수 있으므로 특정 정답 문자열과의 일치는 요구하지 않는다.
주석 08은 첫 줄에서 물건 수와 허용 무게를 읽고, 정해진 수만큼 물건을 읽는다. 문자열 기록에서는 줄바꿈만 제거한다. 검증 불일치 시 입력과 결과를 담은 AssertionError를 발생시킨다. 작은 범위에서 모든 검사가 통과해도 큰 입력까지 증명된 것은 아니다. 점화식의 정확성 근거와 구현 검증을 함께 사용한다.
실행 결과
macOS나 Linux에서 Python 3.12 이상의 실행 파일로 다음 명령을 사용한다. 외부 패키지 설치나 추가 입력은 필요하지 않다.
python3 main.py예상 출력은 다음과 같다.
배낭 최대 점수: 13
LCS 길이: 3
LCS 복원: ABC
두 행 LCS 길이: 3
배낭 전수 대조: 425건 통과
LCS 전수 대조: 961건 통과실무에서 자주 틀리는 것
배낭을 작은 용량부터 갱신한다
한 줄 표에서 오름차순으로 갱신하면 같은 물건으로 방금 만든 값을 다시 읽을 수 있다. 물건 (2, 6) 하나와 허용 무게 4가 작은 반례다. 아래의 첫 코드는 12를 만들지만 올바른 답은 6이다.
# 틀린 코드
for c in range(weight, capacity + 1):
dp[c] = max(dp[c], dp[c - weight] + value)
# 고친 코드
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)두 차원 표의 행을 함께 공유한다
리스트에 곱셈을 적용하면 내부 리스트가 복사되는 것이 아니라 같은 행을 여러 번 참조한다. 한 칸을 바꿨는데 다른 행도 바뀌면 점화식이 전제로 삼은 이전 상태가 사라진다. 행마다 새 리스트를 만들어야 한다.
# 틀린 코드
dp = [[0] * (m + 1)] * (n + 1)
# 고친 코드
dp = [[0] * (m + 1) for _ in range(n + 1)]LCS 복원에서 모은 순서를 그대로 반환한다
복원은 기록의 끝에서 시작한다. 따라서 모은 순서는 실제 수열의 뒤에서 앞 방향이다. 예시에서 CBA를 그대로 반환하면 두 기록의 부분 수열이 아니다. 마지막에 한 번 뒤집는다.
# 틀린 코드
return "".join(result)
# 고친 코드
return "".join(reversed(result))정확히 고른 개수의 불가능한 상태를 0으로 둔다
정확히 K개를 고르는 확장에서는 빈 선택과 불가능한 선택을 구분해야 한다. 물건을 보기도 전에 한 개를 고른 상태가 0이면, 실제로는 개수가 부족한 선택이 정답 후보에 섞인다. 다음은 이전 행에서 선택 후보를 만드는 부분이다.
# 틀린 초기화
previous = [[0] * (K + 1) for _ in range(C + 1)]
# 고친 초기화
previous = [[None] * (K + 1) for _ in range(C + 1)]
for c in range(C + 1):
previous[c][0] = 0
# 선택 후보는 이전 상태가 가능할 때만 만든다.
base = previous[c - weight][k - 1]
if base is not None:
candidate = base + value한눈에 보기
| 문제와 상태 | 계산 순서 | 시간 | 보조 공간 |
|---|---|---|---|
| 0/1 배낭: 허용 무게별 최대 점수 | 물건별, 용량 내림차순 | O(nC) | O(C) |
| LCS 복원: 두 접두부의 최적 길이 | 위 행부터, 왼쪽 열부터 | O(nm) | O(nm) |
| LCS 길이만 계산 | 두 행 교대, 열 오름차순 | O(nm) | O(min(n, m)+1) |
| 정확히 K개 배낭 | 용량과 개수 내림차순 | O(nCK) | O(CK) |
| 인접 묶음 합치기: 양 끝 구간 | 구간 길이 오름차순 | O(n³) | O(n²) |
배낭의 n은 물건 수, LCS의 n과 m은 두 기록의 길이, 구간 문제의 n은 묶음 수다. 같은 기호라도 문제마다 뜻을 다시 정한다. 공간을 줄일 때는 없애려는 행을 이후에 다시 읽는지 확인하고, 복원이 필요하면 어떤 선택 정보가 남는지도 함께 살핀다.
연습 문제
- 점검 가방에 넣을 도구가 (무게, 점수) 순서로 [(1, 2), (3, 6), (4, 7)]이다. 허용 무게는 4다. 최대 점수와 선택한 도구 번호를 구하라. 이어 도구가 (2, 5) 하나뿐일 때 용량을 오름차순으로 갱신하면 허용 무게 4의 답이 어떻게 잘못되는지 설명하라.
- 두 업무 기록이 CAB와 ACB다. LCS 길이와 가능한 최적 수열 두 개를 구하라. 완성 코드의 복원 규칙은 어느 수열을 반환하는지 표를 거슬러 확인하라. 길이가 같은 임의의 문자열만 출력하는 것으로는 왜 검증이 부족한지도 설명하라.
- 공구가 [(1, 4), (2, 5), (3, 8)]이고 허용 무게는 3이다. 정확히 두 개를 고르는 최대 점수를 구하라. 정확히 세 개를 고르는 상태는 어떻게 표현해야 하는가. 선택 개수를 저장하지 않는 배낭 함수의 반환값만으로 두 조건을 구별할 수 있는지도 설명하라.
- 인접 포장 묶음의 크기가 [3, 1, 2, 4]다. 길이 2, 길이 3, 길이 4의 구간 순서로 최소 작업량을 구하라. 검증용 느린 풀이가 매 단계에서 조사해야 할 선택을 설명하고, 작은 양의 크기 배열을 만들어 구간 풀이와 비교하는 방법을 제안하라.
정답과 해설
첫 번째 문제의 최대 점수는 8이고 도구 번호는 1번과 2번이다. 무게는 1+3=4, 점수는 2+6=8이다. 3번 하나의 점수 7보다 크다. (2, 5) 하나를 오름차순으로 처리하면 dp[2]가 5가 된 다음 dp[4]가 그 값을 읽어 10이 된다. 실제로는 한 번만 고를 수 있으므로 답은 5다.
두 번째 문제의 LCS 길이는 2이며 AB와 CB가 모두 가능하다. 마지막 B를 모은 뒤 CA와 AC를 비교하는 상태에서 위쪽과 왼쪽의 값이 모두 1이다. 완성 코드는 위쪽으로 가므로 C와 AC를 비교하고 C를 모은다. 뒤집은 결과는 CB다. 길이만 맞아도 원래 순서를 어겼거나 한쪽에 없는 글자가 포함될 수 있으므로 양쪽의 부분 수열인지도 검사해야 한다.
세 번째 문제에서는 1번과 2번을 골라 무게 3, 점수 9를 얻는다. 다른 두 개 조합은 무게 한도를 넘는다. 세 개를 고르면 무게가 6이므로 도달 불가 상태다. 이를 점수 0과 구별해 None으로 표현한다. 일반 배낭 함수는 개수 조건을 저장하지 않는다. 이 예시에서 반환값 9가 두 개 선택의 답과 우연히 같더라도, 그 값만으로 정확히 세 개를 고르는 상태의 가능 여부를 알 수는 없다.
네 번째 문제에서 길이 2의 구간 비용은 차례로 4, 3, 6이다. 길이 3인 [3, 1, 2]의 크기 합은 6이며 후보 비용은 0+3+6=9와 4+0+6=10이므로 9다. [1, 2, 4]의 합은 7이고 후보는 0+6+7=13과 3+0+7=10이므로 10이다.
전체 크기 합은 10이다. 마지막 경계를 왼쪽부터 잡으면 비용은 0+10+10=20, 4+6+10=20, 9+0+10=19다. 따라서 최소 작업량은 19다. 실제로 1과 2를 합쳐 3을 만들고, 왼쪽의 3과 합쳐 6을 만든 뒤 마지막 4와 합치면 3+6+10=19가 든다.
느린 풀이는 현재 배열에서 이웃한 두 묶음을 합치는 모든 위치를 선택한다. 합친 배열로 다시 모든 선택을 조사하고, 묶음이 하나가 되면 비용 0을 반환한다. 각 선택의 즉시 비용과 이후 최소 비용을 더한 값 중 최솟값이 정답이다. 크기를 1 또는 2로 제한하고 길이 1부터 5까지 모든 배열을 만들면 검증 입력은 62개다. 각 배열에서 이 느린 결과와 구간 표의 결과를 비교할 수 있다. 빈 배열까지 검사하려면 그 답을 0으로 정하고 별도로 처리한다.
상태를 정할 때는 다음 선택에 영향을 주는 정보가 모두 들어 있는지 확인한다. 구현할 때는 이전 값과 현재 값의 구분을 갱신 순서로 지킨다. 마지막으로 작은 입력에서 다른 방식으로 구한 답과 비교하면, 설명한 논리가 코드에서도 유지되는지 구체적으로 확인할 수 있다.