6. DP 심화 (LIS / LCS / 배낭)

입문 DP에서 우리는 "마지막 선택으로 경우를 나눠 점화식을 세운다"는 사고법을 익혔습니다. 피보나치, 계단 오르기, 기초 배낭까지요. 여기서는 그 사고법을 실전 단골 유형 세 개에 적용합니다. LIS, LCS, 그리고 배낭의 제대로 된 최적화까지. 셋 다 코딩테스트에 정말 자주 나오고, 한 번 패턴을 익히면 변형 문제도 술술 풀립니다.

입문에서 다룬 피보나치·계단·기초 배낭은 여기서 반복하지 않아요. "큰 문제 = 작은 문제들의 조합, 겹치는 답은 표에 저장" 이 한 줄만 복습하고 바로 심화로 들어갑니다.

이 한 챕터에서 배우는 것:

LIS(최장 증가 부분 수열): O(n²) DP 기본과 이진탐색 O(n log n) 최적화
LCS(최장 공통 부분 수열): 2차원 DP 테이블 채우기
0/1 배낭: 2차원 표를 1차원으로 압축하는 공간 최적화
1차원 DP → 2차원 DP → 이진탐색 결합까지 이어지는 사고 확장

LIS: 최장 증가 부분 수열

부분 수열은 원래 순서를 유지하되 일부를 골라 만든 수열입니다(연속일 필요 없음). 그중 오른쪽으로 갈수록 값이 커지는(증가하는) 가장 긴 것의 길이를 구하는 게 LIS예요.

예를 들어 [10, 9, 2, 5, 3, 7, 101, 18]에서 가장 긴 증가 부분 수열은 [2, 3, 7, 18] 또는 [2, 5, 7, 101]로 길이가 4입니다.

1단계: O(n²) DP

DP의 단골 질문을 던집니다. "i번째 수로 끝나는 LIS의 길이는?" 이걸 dp[i]로 정의해요.

i번째 수 nums[i]로 끝나려면, 그 앞의 어떤 j(nums[j] < nums[i])로 끝나는 LIS 뒤에 nums[i]를 붙이면 됩니다. 그런 j 중 가장 긴 걸 골라 +1 하면 돼요.

def lis(nums):
    n = len(nums)
    dp = [1] * n                 # 자기 혼자로도 길이 1은 됨
    for i in range(n):
        for j in range(i):       # i 앞의 모든 j를 살펴봄
            if nums[j] < nums[i]:            # j 뒤에 i를 이어붙일 수 있으면
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)               # 어디서 끝나든 가장 긴 것

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4
print(lis([0, 1, 0, 3, 2, 3]))             # 4
print(lis([7, 7, 7, 7]))                   # 1  (증가하지 않으면 1)

이중 반복문이니 시간복잡도는 O(n²) 입니다. n이 1,000 정도면 100만 번이라 괜찮지만, n이 100,000이면 100억 번이라 시간 초과예요. 더 빠른 방법이 필요합니다.

💡 dp[i]를 "i에서 끝나는 답"으로 잡는 게 포인트입니다. "i까지의 답"으로 잡으면 이어붙일 기준이 애매해져요. LIS·LCS류는 "이 지점에서 끝나는/이 지점까지의" 정의를 정확히 잡는 게 절반입니다.

2단계: 이진탐색으로 O(n log n)

발상을 완전히 바꿉니다. "길이 k인 증가 수열의 마지막 값을 가능한 한 작게 유지" 하면 뒤에 수를 더 붙이기 쉬워집니다. 그래서 tails라는 리스트를 관리해요. tails[k] = 길이 k+1인 증가 부분 수열의 가능한 가장 작은 끝값.

새 수 x가 오면:

tails의 모든 값보다 크면 → 뒤에 붙여 수열을 길게 늘림
아니면 → x보다 크거나 같은 첫 자리를 x로 교체(끝값을 더 작게 갱신)

이 "교체 위치 찾기"가 바로 이진탐색입니다. 이진탐색 챕터(algorithm/07)에서 배운 bisect를 그대로 씁니다.

import bisect

def lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)   # x가 들어갈 위치(같은 값이면 왼쪽)
        if i == len(tails):
            tails.append(x)                # 제일 크면 길이 +1
        else:
            tails[i] = x                   # 아니면 그 자리를 x로 교체
    return len(tails)                      # tails 길이 = LIS 길이

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

각 수마다 이진탐색 O(log n)을 하니 전체 O(n log n) 입니다. n = 100,000도 순식간이에요.

💡 주의: tails는 LIS 그 자체가 아닙니다. 중간에 교체가 일어나 실제 부분 수열과 값이 다를 수 있어요. 하지만 길이만큼은 항상 정확합니다. 길이만 필요할 때 쓰는 트릭이에요. (bisect_left 대신 bisect_right를 쓰면 "증가"가 아니라 "감소하지 않는" 수열, 즉 같은 값 허용 LIS가 됩니다.)

x = 3은 2보다 크고 5보다 작으니 5 자리를 3으로 교체합니다. 길이 2짜리 수열의 끝값이 5에서 3으로 작아져, 앞으로 더 붙이기 쉬워졌죠.

LCS: 최장 공통 부분 수열

이번엔 두 문자열(또는 수열) 을 받아, 양쪽에 공통으로 들어있는 가장 긴 부분 수열의 길이를 구합니다. 예를 들어 "ABCBDAB"와 "BDCAB"의 LCS는 "BCAB"로 길이 4예요.

상태가 두 개(두 문자열의 진행 위치)이니 자연스럽게 2차원 DP입니다. dp[i][j] = "첫 문자열의 앞 i글자, 둘째 문자열의 앞 j글자로 만든 LCS 길이"로 정의합니다.

마지막 글자를 비교해 경우를 나눕니다.

a[i-1] == b[j-1](마지막 글자가 같으면): 그 글자를 LCS에 넣고 dp[i-1][j-1] + 1
다르면: 한쪽 글자를 버려야 하니 max(dp[i-1][j], dp[i][j-1]) 중 큰 쪽

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]   # 0번째 줄/칸은 빈 문자열(0)

    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      # 대각선 + 1
            else:                                    # 다르면
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

print(lcs("ABCBDAB", "BDCAB"))   # 4
print(lcs("AGGTAB", "GXTXAYB"))  # 4   (GTAB)
print(lcs("ABC", "DEF"))         # 0   (공통 없음)

표가 (n+1) × (m+1) 크기이고 칸마다 O(1)이니 시간복잡도는 O(n × m) 입니다.

💡 LCS 표를 채우는 규칙은 딱 두 방향이에요. 글자가 같으면 대각선(↖)에서 +1, 다르면 위(↑)·왼쪽(←) 중 큰 값을 복사. 이 그림만 외우면 코드가 저절로 나옵니다. 편집 거리(Edit Distance) 같은 문제도 표 채우는 규칙만 바뀔 뿐 골격이 똑같아요.

0/1 배낭: 2차원에서 1차원으로

입문에서 배낭의 2차원 DP(dp[i][w])는 다뤘습니다. 여기서는 그걸 1차원 배열로 압축해 공간을 아끼는 실전 기술을 배웁니다.

2차원 점화식을 다시 보면, dp[i][w]는 dp[i-1][...](바로 윗줄)만 참조합니다. 즉 직전 물건까지의 결과만 있으면 현재 물건을 처리할 수 있어요. 그러니 줄을 통째로 저장할 필요 없이, 한 줄짜리 배열 dp[w]를 덮어쓰며 재사용하면 됩니다.

여기 함정이 하나 있습니다. 1차원에서 무게 w를 작은 쪽부터 갱신하면, 방금 갱신한 dp[w-weight](현재 물건이 이미 반영된 값)를 다시 써서 같은 물건을 두 번 담는 사고가 납니다. 그래서 무게를 큰 쪽에서 작은 쪽으로(역순) 돌아, dp[w-weight]가 아직 "직전 물건까지의 값"으로 남아있게 합니다.

def knapsack(items, W):
    # items: (무게, 가치) 리스트
    dp = [0] * (W + 1)                     # dp[w] = 무게 한도 w에서의 최대 가치
    for weight, value in items:
        for w in range(W, weight - 1, -1): # 역순! (W → weight)
            dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[W]

items = [(6, 60), (3, 40), (3, 40)]
print(knapsack(items, 6))    # 80   (B+C, 그리디의 60을 이김)

items2 = [(1, 6), (2, 10), (3, 12)]
print(knapsack(items2, 5))   # 22

시간복잡도는 2차원과 똑같은 O(n × W) 이지만, 공간이 O(n × W)에서 O(W) 로 줄었습니다. 표 한 줄만 들고 다니는 거죠.

💡 배낭 1차원 최적화의 핵심은 딱 하나, 역순 반복입니다. 만약 range(weight, W + 1)처럼 정방향으로 돌면 "물건을 여러 번 담아도 되는" 완전 배낭(unbounded knapsack) 이 됩니다. 방향 하나로 0/1이냐 무제한이냐가 갈리니, 여기서 자주 실수가 나옵니다.

정리

문제	정의	시간복잡도	핵심 도구
LIS 기본	`dp[i]` = i에서 끝나는 LIS	O(n²)	이중 반복
LIS 최적화	`tails` = 길이별 최소 끝값	O(n log n)	이진탐색(bisect)
LCS	`dp[i][j]` = 앞 i·j글자 공통 길이	O(n × m)	2차원 표
0/1 배낭(1차원)	`dp[w]` = 한도 w의 최대 가치	O(n × W)	역순 갱신

💡 세 문제 모두 입문 DP와 같은 흐름입니다. ① 상태를 뭘로 잡을지 정하고 → ② 마지막 선택으로 경우를 나눠 점화식을 세우고 → ③ 표/배열로 중복을 없앤다. 달라진 건 상태가 2차원으로 커지거나(LCS·배낭), 이진탐색으로 한 단계를 빠르게 만든 것(LIS)뿐이에요. 새 기법이 아니라 아는 기법의 조합입니다.

직접 풀어보기

O(n²) LIS를 고쳐 LIS의 길이뿐 아니라 실제 수열까지 출력해보세요. (힌트: dp[i]를 갱신할 때 "어느 j에서 왔는지"를 따로 기록해두면 역추적할 수 있어요.)
LCS 코드로 "CODELAB"과 "OLDGABLE"의 LCS 길이를 구해보세요. (정답: 4, 예: "OLAB")
완전 배낭(물건을 여러 번 담을 수 있음) 버전을 만들어보세요. (무게, 가치)가 (2, 3), (3, 4), (4, 5)이고 한도 W=7일 때 최대 가치는? (힌트: 안쪽 반복을 정방향 range(weight, W + 1)로 바꾸면 됩니다. 정답: 10 — (2,3)을 두 번 + (3,4)를 한 번, 무게 7·가치 10)