컴퓨터공학 300 주제 시리즈의 073번째 글이다. 전체 지도는 여기.

한 줄 요약

0/1 배낭은 “앞 i 개 물건, 남은 용량 w” 를 상태로, 최장 공통 부분수열(LCS)은 “두 문자열의 앞 i 글자와 앞 j 글자” 를 상태로 하는 2차원 DP 다. 표를 채운 뒤 거꾸로 따라가면 최적값뿐 아니라 최적해 자체도 복원된다.

왜 필요한가

앞 글에서 DP 의 뼈대(상태, 점화식, 기저, 순서)를 봤다. 이번 두 문제는 그 뼈대를 2차원으로 넓히는 대표 예제다. 그리고 둘 다 실무와 바로 닿는다.

  • 배낭 문제는 “제한된 예산(시간, 메모리, 돈) 안에서 가치 합을 최대로” 라는 모든 자원 배분 문제의 원형이다.
  • LCS 는 diff 의 원형이다. 두 버전의 파일에서 공통으로 남은 줄을 최대한 많이 찾으면, 나머지가 추가·삭제된 줄이다.

핵심 개념

0/1 배낭

물건 n 개에 각각 무게 wᵢ, 가치 vᵢ 가 있다. 용량 W 인 배낭에 넣을 물건을 골라 가치 합을 최대로 한다. 각 물건은 넣거나 안 넣거나 둘 중 하나다.

상태: dp[i][w] = 앞의 i 개 물건만 고려하고 용량이 w 일 때 얻을 수 있는 최대 가치.

점화식: i 번째 물건에 대해 두 갈래만 있다.

dp[i][w] = max( dp[i-1][w],                    ← i번째를 안 넣는다
                dp[i-1][w - wᵢ] + vᵢ )         ← 넣는다 (wᵢ ≤ w 일 때만)

기저: dp[0][w] = 0 (물건이 없으면 가치 0).

복잡도: 상태 (n+1)(W+1) 개 × 전이 2 = Θ(nW).

여기서 주의할 점이 있다. Θ(nW) 는 다항식처럼 보이지만 W 는 입력의 값 이지 입력의 길이 가 아니다. W 를 이진수로 적으면 log W 비트이므로, 입력 길이에 대해서는 지수 시간이다. 이런 알고리즘을 의사 다항 시간(pseudo-polynomial)이라고 한다. 실제로 0/1 배낭의 판정 버전은 NP-완전이다(마지막 글에서 다룬다).

배낭에서 탐욕이 틀리는 예

무게 10·20·30, 가치 60·100·120, 용량 50. 무게당 가치는 6, 5, 4 다.

  • 탐욕(무게당 가치 순): 10 + 20 을 넣고 나면 남은 20 에 30 이 안 들어간다. 가치 160.
  • 최적: 20 + 30, 가치 220.

최장 공통 부분수열(LCS)

부분수열은 순서는 유지하되 연속일 필요는 없다. “ABCBDAB” 와 “BDCABA” 의 LCS 길이는 4 다(예: BCBA).

상태: dp[i][j] = a 의 앞 i 글자와 b 의 앞 j 글자의 LCS 길이.

점화식:

a[i-1] == b[j-1] 이면  dp[i][j] = dp[i-1][j-1] + 1
아니면                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

마지막 글자가 같으면 그 글자를 LCS 에 넣어도 손해가 없다. 다르면 둘 중 하나는 LCS 의 끝이 될 수 없으니 하나씩 빼 본 두 경우 중 큰 것을 택한다.

기저: dp[0][j] = dp[i][0] = 0. 복잡도: Θ(mn) 시간, Θ(mn) 공간.

역추적으로 해 복원하기

표의 오른쪽 아래 끝에서 출발해 “이 값이 어느 갈래에서 왔는가” 를 거꾸로 따라간다.

  • 배낭: dp[i][w] ≠ dp[i−1][w] 이면 i번째 물건을 넣은 것이다. w 에서 wᵢ 를 빼고 위로 간다.
  • LCS: 글자가 같으면 대각선으로, 아니면 더 큰 쪽(위 또는 왼쪽)으로 간다.

공간 줄이기

길이만 필요하면 LCS 는 행 두 개, 배낭은 행 하나(용량을 큰 쪽부터 갱신)로 충분하다. 해까지 필요하면서 공간도 줄이고 싶을 때는 Hirschberg 가 1975년에 낸 분할 정복 방법으로 Θ(min(m,n)) 공간에 LCS 를 복원할 수 있다.

직접 해 보기

배낭(DP vs 탐욕), LCS, 그리고 LCS 로 만든 아주 작은 줄 단위 diff 다. python3 로 실행해 확인했다.

def knapsack(items, W):
    """items: (이름, 무게, 가치). dp[i][w] = 앞 i 개로 용량 w 에서 최대 가치."""
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        _, wt, val = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                       # i번째를 안 넣음
            if wt <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)   # 넣음
    picked, w = [], W                                     # 역추적
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            picked.append(items[i - 1][0]); w -= items[i - 1][1]
    return dp[n][W], picked[::-1]

items = [("A", 10, 60), ("B", 20, 100), ("C", 30, 120)]
print("DP  :", knapsack(items, 50))

greedy, cap, val = [], 50, 0                              # 무게당 가치 탐욕
for name, wt, v in sorted(items, key=lambda t: t[2] / t[1], reverse=True):
    if wt <= cap:
        greedy.append(name); cap -= wt; val += v
print("탐욕:", val, greedy)

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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])
    out, i, j = [], m, n                                  # 역추적
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

print(lcs("ABCBDAB", "BDCABA"))

# 줄 단위 diff: LCS 에 속한 줄은 유지, 나머지는 삭제(-)/추가(+)
old = ["replicas: 2", "image: app:1.0", "port: 8080", "debug: false"]
new = ["replicas: 3", "image: app:1.0", "port: 8080", "debug: true", "timeout: 30"]
m, n = len(old), len(new)
dp = [[0] * (n + 1) for _ in range(m + 1)]       # dp[i][j] = old[i:], new[j:] 의 LCS
for i in range(m - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        dp[i][j] = dp[i + 1][j + 1] + 1 if old[i] == new[j] else max(dp[i + 1][j], dp[i][j + 1])
i = j = 0
while i < m or j < n:
    if i < m and j < n and old[i] == new[j]:
        print("  " + old[i]); i += 1; j += 1
    elif i < m and (j == n or dp[i + 1][j] >= dp[i][j + 1]):
        print("- " + old[i]); i += 1      # 지우는 줄을 먼저 보여 준다
    else:
        print("+ " + new[j]); j += 1

출력:

DP  : (220, ['B', 'C'])
탐욕: 160 ['A', 'B']
(4, 'BCBA')
- replicas: 2
+ replicas: 3
  image: app:1.0
  port: 8080
- debug: false
+ debug: true
+ timeout: 30

마지막 diff 는 접미사 기준 표(dp[i][j] = old[i:] 와 new[j:] 의 LCS)를 써서 앞에서부터 출력하도록 했다. 공통 줄 두 개가 유지되고 나머지가 삭제·추가로 표시된다. 매니페스트 변경을 리뷰할 때 보는 화면과 같은 모양이다.

현업에서는

  • diff 도구. git diff 의 기본 알고리즘은 Myers 의 O(ND) 알고리즘이다(N 은 두 입력 길이 합, D 는 편집 거리). 두 파일이 비슷할수록(D 가 작을수록) 빠르다. 근본 문제는 LCS 와 같고, 공식 문서에서 --diff-algorithm 으로 patience, histogram 등 다른 변형을 고를 수 있다.
  • Python difflib. 표준 라이브러리 difflib.SequenceMatcher 는 LCS 가 아니라 Ratcliff/Obershelp 계열의 “가장 긴 연속 일치 블록” 을 재귀로 찾는 방식을 쓴다고 공식 문서에 적혀 있다. 결과가 사람 눈에 자연스러운 쪽을 택한 설계다. “diff = LCS” 는 출발점일 뿐 도구마다 다르다.
  • 자원 배분. 정해진 노드 자원에 어떤 작업들을 올릴지, 정해진 예산으로 어떤 기능을 이번 분기에 할지 같은 결정은 배낭 문제 꼴이다. 항목이 수십 개이고 용량이 작은 정수면 DP 로 정확히 풀 수 있다. 크면 근사나 휴리스틱으로 간다.
  • 편집 거리. 맞춤법 교정, 퍼지 검색, 명령어 오타 제안(“did you mean”)은 LCS 와 거의 같은 표로 계산하는 레벤슈타인 거리를 쓴다.

확인 문제

  1. 배낭 DP 를 1차원 배열 하나로 줄일 때 용량 w 를 큰 쪽부터 갱신해야 하는 이유는?
  2. 배낭 문제의 Θ(nW) 가 다항 시간이 아닌 이유는?
  3. LCS 와 “최장 공통 부분 문자열(연속)” 의 점화식은 어떻게 다른가?
  4. 두 문자열 길이가 각각 m, n 일 때 LCS 표를 채우는 시간은?

풀이

  1. dp[w] 를 갱신할 때 dp[w − wᵢ] 는 “i번째 물건을 아직 고려하지 않은” 값이어야 한다. 작은 쪽부터 갱신하면 이미 i번째를 넣은 값을 다시 써서 같은 물건을 여러 번 넣는 셈이 된다(그건 무한 배낭 문제다).
  2. W 는 입력 크기가 아니라 값이다. W 를 표현하는 비트 수 b 에 대해 W = 2^b 수준이므로 입력 길이에 대해 지수적이다.
  3. 연속 부분 문자열은 글자가 다르면 dp[i][j] = 0 으로 끊고, 같으면 dp[i−1][j−1] + 1. 답은 표 전체의 최댓값이다.
  4. Θ(mn).

더 읽을거리 (References)