E-5: 2차원 DP — 배낭·LIS·LCS, 상태가 둘이면 표도 한 차원 는다

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간(E-4) 마지막에 제가 문을 하나 열어 두고 왔어요. 우리가 다룬 dp는 전부 숫자 하나였다고요. dp[n]은 몇 번째 칸, dp[a]는 남은 금액. 상태가 하나뿐이라 1차원 배열 하나면 충분했죠. 그러면서 이렇게 못 박았습니다. "상태가 하나면 1차원, 여럿이면 2차원." 오늘 그 여럿인 세계로 넘어갑니다.

배낭에 물건을 담는 문제를 떠올려 보세요. "몇 번째 물건까지 봤나"와 "남은 무게가 얼마인가"를 동시에 기억해야 합니다. 상태가 둘이죠. 그러면 dp도 dp[i][w]처럼 표가 한 차원 늘어납니다. 두 문자열이 얼마나 닮았는지 재는 문제도 마찬가지예요. 첫 문자열의 몇 번째, 둘째 문자열의 몇 번째를 함께 들고 가야 하니 dp[i][j] 2차원 표가 필요하죠.

오늘 만날 배낭(Knapsack), 최장 증가 부분 수열(LIS, Longest Increasing Subsequence), 최장 공통 부분 수열(LCS, Longest Common Subsequence), 편집 거리 — 이 넷은 코딩테스트 DP 문제에서 가장 자주 얼굴을 내미는 단골들입니다. 겁먹을 필요 없어요. E-4에서 잡은 "상태 정의 → 점화식" 감각이 그대로 한 차원 위로 올라갈 뿐이니까요. 표가 한 줄에서 판때기로 넓어질 뿐, 채우는 원리는 똑같습니다.

 오늘의 여정 — 상태가 둘이면 표도 한 차원 는다

   0/1 배낭 2D       물건 축 × 무게 축, dp[i][w] 판을 채운다
     │              담을까 말까 두 갈래 중 큰 값을 남긴다
     │
   배낭 1D 롤링      윗줄만 참조하니 한 줄로 접는다(역순 순회)
     │              공간 O(n×W) → O(W)
     ▼
   LIS 표 채우기     arr[i]로 끝나는 최장 증가 길이, 앞을 다 훑는다 O(n²)
     │
   LIS 이진 탐색     D-3을 회수해 tails를 갈아끼운다 O(n log n)
     ▼
   LCS · 편집 거리   두 문자열의 축, 닮음을 재고 실제 조각을 복원한다
     │
   구간 DP          구간을 어디서 가를까 — 행렬 곱셈 순서

💡 오늘 수업의 핵심 — "상태가 둘이면 표가 2차원이 된다 — 배낭은 물건×무게, LIS·LCS는 순서와 문자열의 축으로 dp[i][j]를 채우고, 롤링과 이진 탐색으로 시간·공간을 눌러 낸다"

🎯 학습 목표

• 상태가 둘이면 dp[i][j] 2차원 표가 필요하다는 것을 0/1 배낭에서 잡고, "담을까 말까" 두 갈래로 점화식을 세운다.
• 배낭·LIS·LCS 같은 2차원 DP 대표 유형을 익히고, 2차원 표를 한 줄로 접는 롤링과 이진 탐색으로 O(n log n)까지 내리는 최적화를 손에 붙인다.
• 직접 표를 채우는 원리 트랙과 bisect 같은 내장을 쓰는 실전 트랙을 대조하며, 입력 크기 n에 맞는 복잡도를 빅오로 고른다.

Step 1: "2차원 DP의 문을 열다 — 0/1 배낭" (~20분)

지난 시간에 만난 dp를 다시 눈앞에 놓아 볼게요. dp[n], dp[a] — 전부 숫자 하나로 상태를 표현했습니다. 계단은 "몇 번째 칸", 거스름돈은 "남은 금액". 상태가 하나라서 1차원 배열 하나로 다 풀렸죠. 그런데 오늘 첫 문제인 0/1 배낭은 상태를 하나로는 담을 수가 없습니다. E-4 마지막에 열어 둔 그 문을 지금 엽니다.

0/1 배낭 문제부터 정의할게요. 물건들이 저마다 무게와 가치를 갖고 있고, 배낭에는 담을 수 있는 무게 한도가 있습니다. 이 한도를 넘지 않으면서 담은 물건들의 가치 합을 최대로 만드는 게 목표예요. 여기서 "0/1"이 붙는 이유는, 각 물건을 통째로 담거나(1) 아예 안 담거나(0) 둘 중 하나이기 때문입니다. 물건을 반으로 쪼개 담을 수는 없어요.

이 문제가 왜 상태 둘을 요구할까요? 어떤 물건을 담을지 결정하려면 "지금 몇 번째 물건을 보고 있나(i)"를 알아야 하고, 동시에 "남은 무게 한도가 얼마나(w)" 남았는지도 알아야 합니다. 이 둘이 함께 정해져야 "이 물건을 담을 수 있나, 담으면 가치가 얼마가 되나"가 결정되죠. 그래서 dp[i][w], 두 축을 가진 표가 필요합니다.

# algorithms/dp.py
def knapsack_2d(items, capacity):
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]   # (물건 축 i) × (무게 축 w)
    for i in range(1, n + 1):
        wi, vi = items[i - 1]           # i번째 물건의 (무게, 가치)
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]     # 안 담는 갈래: 위 줄 그대로 물려받는다
            if w >= wi:                 # 담을 무게 여유가 있을 때만
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi)   # 담는 갈래와 비교
    return dp[n][capacity]

점화식을 한 줄로 읽어 볼게요. dp[i][w]는 "i번째 물건까지 보면서, 무게 한도 w 안에서 담을 수 있는 최대 가치"입니다. i번째 물건 앞에서 우리가 할 수 있는 선택은 딱 둘이에요. 안 담으면 바로 윗줄 dp[i-1][w]를 그대로 물려받고, 담으면 (무게가 w 이하일 때만) 그 물건 무게 wi를 뺀 칸의 최적 dp[i-1][w-wi]에 가치 vi를 더합니다. 이 두 갈래 중 큰 값이 dp[i][w]가 되죠.

작은 예로 표를 직접 채워 보면 눈에 확 들어옵니다. 물건 [(2,3), (3,4), (4,5), (5,6)](무게, 가치)에 한도 5로 풀어 볼게요.

 0/1 배낭 표 — 물건 [(2,3),(3,4),(4,5),(5,6)], 한도 5
 칸값 = 그 물건까지 보며 그 무게 한도에서 담을 수 있는 최대 가치

          w=0  w=1  w=2  w=3  w=4  w=5     (남은 무게 한도)
   i=0      0    0    0    0    0    0      물건 0개
   i=1      0    0    3    3    3    3      +물건(2,3)
   i=2      0    0    3    4    4    7      +물건(3,4)
   i=3      0    0    3    4    5    7      +물건(4,5)
   i=4      0    0    3    4    5    7      +물건(5,6)
                                    (답) dp[4][5] = 7

dp[2][5]가 어떻게 7이 됐는지 딱 한 칸만 뜯어볼게요. 지금 보는 건 물건2, 무게 3에 가치 4짜리입니다.

 dp[2][5]은 어떻게 7이 됐나 (물건2 = 무게3·가치4)

   안 담기 → 윗칸 dp[1][5] = 3
   담  기 → dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 = 7
   두 갈래 중 큰 값을 골라 dp[2][5] = 7

   위 칸에서 '안 담기'가, 왼쪽 위 대각선 칸에서 '담기'가 흘러온다

무게 2짜리와 무게 3짜리를 함께 담으면 무게 합이 5, 가치 합이 3+4=7. 한도 5에 딱 맞으면서 가치가 제일 크죠. 표의 오른쪽 아래 끝 칸 dp[4][5]가 바로 그 답 7입니다. 코드로 확인해 볼게요. knapsack_2d([(2,3),(3,4),(4,5),(5,6)], 5)는 7을 냅니다. 반대로 knapsack_2d([(6,13)], 5)는 0이에요. 무게 6짜리 하나뿐인데 한도가 5라 아예 담을 수가 없거든요.

빅오를 따져 봅시다. 표의 칸 수가 곧 일의 양이에요. 물건 축이 n+1개, 무게 축이 capacity+1개니까 표 전체를 채우는 데 시간 O(n×capacity), 표를 통째로 들고 있으니 공간 O(n×capacity)입니다. "1초에 약 1억 연산" 잣대로 보면, n×capacity가 1억 언저리 — 물건 1000개에 한도 10만 정도까지가 안전선이에요. 무게 한도가 너무 크면 표가 메모리를 넘칠 수 있는데, 그 걱정은 다음 Step에서 풀겠습니다.

두 트랙 이야기도 짚고 갈게요. 정렬이나 탐색과 달리, 배낭은 파이썬 표준 라이브러리에 "배낭 함수" 같은 게 따로 없습니다. 그래서 이 유형은 직접 표를 채우는 게 곧 실전이에요. 대신 "표를 어떻게 더 효율적으로 채우느냐"에서 최적화 트랙이 갈리는데, 그게 바로 다음 Step의 롤링 배열입니다.

💡 한 줄 정리

0/1 배낭은 "몇 번째 물건까지(i)"와 "남은 무게(w)" 두 상태를 함께 들어야 해서 dp[i][w] 2차원 표가 필요하다. 각 칸은 "안 담기(윗칸)"와 "담기(왼쪽 위 대각선 + 가치)" 두 갈래 중 큰 값이고, 시간·공간 모두 O(n×capacity)다.

Step 2: "배낭을 한 줄로 접기 — 역순 순회의 비밀" (~20분)

Step 1의 배낭 표를 다시 떠올려 보세요. 공간이 O(n×capacity)라 무게 한도가 크면 메모리가 부담이었죠. 그런데 지난 시간에 우리가 비슷한 상황을 이미 한 번 풀었어요. 피보나치와 계단에서 dp 전체를 남기지 않고 직전 두 값만 변수로 굴려 공간을 O(1)까지 줄였던 롤링 기억나시나요? 2차원 배낭에도 같은 수법을 쓸 수 있습니다.

핵심은 Step 1 코드의 이 한 줄에 있어요. dp[i][w]를 구할 때 우리가 참조한 건 dp[i-1][w]와 dp[i-1][w-wi], 즉 오직 바로 윗줄(i-1)뿐이었습니다. 두 줄 위, 세 줄 위는 한 번도 안 봤죠. 그렇다면 표를 통째로 남길 필요가 없어요. 윗줄 하나만 있으면 되니까, 한 줄짜리 배열을 계속 덮어쓰며 굴리면 됩니다.

def knapsack_1d(items, capacity):
    dp = [0] * (capacity + 1)           # 무게 축 한 줄만 유지(윗줄을 덮어쓰며 굴린다)
    for wi, vi in items:
        for w in range(capacity, wi - 1, -1):   # 역순: dp[w-wi]가 '이 물건 안 쓴 값'이게
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return dp[capacity]

여기서 절대 놓치면 안 되는 게 있어요. 안쪽 무게 루프가 range(capacity, wi-1, -1), 즉 큰 무게에서 작은 무게로 거꾸로 돕니다. 이 역순이 이 코드의 생명이에요. 왜 거꾸로 돌아야 하는지, 이유를 정확히 잡고 갑시다.

한 줄짜리 dp를 덮어쓰며 쓰다 보니, dp[w]를 갱신할 때 참조하는 dp[w-wi]가 "이번 물건을 아직 안 쓴 값(윗줄)"이어야 각 물건을 정확히 한 번만 담게 됩니다. 무게를 역순으로 돌면, dp[w](큰 쪽)를 먼저 건드리는 시점에 dp[w-wi](작은 쪽)는 아직 이번 물건이 반영되지 않은 상태로 남아 있어요. 그런데 정순(작은 무게 → 큰 무게)으로 돌면 정반대가 됩니다. dp[w-wi]를 먼저 이번 물건으로 갱신해 버린 뒤에 그 값을 다시 참조하게 되고, 결국 같은 물건을 여러 번 담는 꼴이 돼요.

 물건 (무게2·가치3) 하나를 dp에 반영 — 정순 vs 역순

 정순 w=2→5 (틀림·같은 물건이 두 번 담긴다)
   w=2 : dp[2] = dp[0]+3 = 3
   w=4 : dp[4] = dp[2]+3 = 6   ← dp[2]가 방금 갱신된 값! 무게2 물건을 또 담았다

 역순 w=5→2 (맞음·각 물건 최대 한 번)
   w=4 : dp[4] = dp[2]+3 = 3   ← dp[2]는 아직 '이 물건 안 쓴 0'
   w=2 : dp[2] = dp[0]+3 = 3

정순에서 dp[4]가 6이 된 게 보이시죠? 무게 2짜리 하나로 무게 4를 채웠다는 건, 같은 물건을 두 번 담았다는 뜻이에요. 0/1 배낭에선 있을 수 없는 일입니다. 역순으로 돌면 이 사고가 안 나요. 참고로 정순으로 도는 그 "실수"가, 사실은 각 물건을 무한정 여러 번 담을 수 있는 다른 문제(무한 개수 배낭)의 정답 풀이입니다. 루프 방향 하나가 완전히 다른 두 문제를 가른다는 게 재밌죠.

답이 2차원 버전과 정말 같은지 확인해 볼게요. 모든 입력에서 knapsack_1d와 knapsack_2d는 같은 값을 냅니다. 예를 들어 knapsack_1d([(6,13),(4,8),(3,6),(5,12)], 10)은 21이에요. 무게 6짜리(가치 13)와 무게 4짜리(가치 8)를 담으면 무게 합 10에 가치 합 21로 최대가 되죠.

빅오를 비교하면 이 최적화의 값어치가 분명해집니다. 채우는 칸 수는 2차원과 똑같아서 시간은 O(n×capacity)로 동일해요. 달라진 건 공간입니다. 표를 한 줄로 접었으니 공간이 O(capacity)로 줄었어요. 물건 수 n이 아무리 많아져도 배열 길이는 capacity+1로 고정입니다. 실전 코딩테스트에서 무게 한도가 커서 2차원 표가 메모리 제한을 넘길 때, 이 1차원 롤링이 바로 표준 최적화예요. 원리를 2차원으로 이해한 뒤, 실전에선 이렇게 한 줄로 접어 쓰는 겁니다.

💡 한 줄 정리

dp[i][w]가 바로 윗줄만 참조하므로, 2차원 배낭 표를 한 줄짜리 dp[w]로 접어 공간을 O(n×capacity)에서 O(capacity)로 줄인다. 이때 무게를 역순으로 돌아야 dp[w-wi]가 "이번 물건 안 쓴 값"으로 남아 각 물건을 한 번만 담는다.

Step 3: "최장 증가 부분 수열(LIS) ① — O(n²)" (~20분)

배낭에서 잠깐 나와, 결이 다른 2차원 DP 유형으로 가볼게요. 최장 증가 부분 수열, 줄여서 LIS입니다. 이름이 길지만 하나씩 풀면 어렵지 않아요. 먼저 "부분 수열(subsequence)"이라는 말부터 정확히 잡고 갑시다.

부분 수열은 원래 수열에서 순서를 지키되, 사이를 건너뛰어 골라낸 수열입니다. 여기서 "연속일 필요가 없다"는 게 핵심이에요. 예를 들어 [3, 10, 2, 1, 20]에서 [3, 10, 20]은 부분 수열입니다. 원래 순서(3이 10보다 앞, 10이 20보다 앞)를 지키면서 사이의 2와 1을 건너뛴 거죠. 연속으로 붙어 있는 조각만 골라야 하는 "부분 배열(subarray)"과는 다릅니다. LIS는 이런 부분 수열 중에서 값이 계속 커지는(엄격 증가) 가장 긴 것의 길이를 구하는 문제예요.

이걸 DP로 어떻게 풀까요? E-4에서 배운 대로, 첫 단추는 상태 정의입니다. 그런데 여기서 정의를 살짝 비틀어야 해요. "가장 긴 증가 수열의 길이"를 바로 dp로 두면, 앞뒤 관계를 이어 붙일 고리가 안 잡힙니다. 대신 이렇게 정의합니다. dp[i] = "arr[i]로 끝나는 증가 수열 중 가장 긴 것의 길이." "끝을 arr[i]로 고정"한 게 열쇠예요.

def lis_n2(arr):
    n = len(arr)
    if n == 0:
        return 0
    dp = [1] * n                        # dp[i]: arr[i]로 끝나는 LIS 길이(최소 나 혼자=1)
    for i in range(n):
        for j in range(i):              # 내 앞의 모든 원소를 훑어
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:   # 나보다 작으면 이어붙일 후보
                dp[i] = dp[j] + 1       # 가장 긴 앞 수열에 나를 하나 얹는다
    return max(dp)

점화식을 말로 풀어 볼게요. arr[i]로 끝나는 증가 수열을 만들려면, 내 앞의 원소들 중 나보다 작은 것 뒤에 나를 이어 붙이면 됩니다. 그래서 j를 0부터 i-1까지 훑으면서, arr[j] < arr[i]인(내 앞에 있으면서 나보다 작은) 것들 중 가장 긴 dp[j]를 찾아 거기에 1을 더해요. 만약 나보다 작은 앞 원소가 하나도 없으면? 이어 붙일 게 없으니 나 혼자 수열이라 길이 1입니다. 그래서 dp를 처음에 전부 1로 채워 두고 시작하죠.

[3, 10, 2, 1, 20]으로 표를 채워 볼게요.

 LIS O(n²) 표 채우기 — arr = [3, 10, 2, 1, 20]
 dp[i] = arr[i]로 끝나는 가장 긴 증가 수열의 길이

   i         0    1    2    3    4
   arr[i]    3   10    2    1   20
   dp[i]     1    2    1    1    3
             │    │              │
             │    └ [3,10]       └ [3,10,20] → 길이 3
             └ 나 혼자

   답 = max(dp) = 3   (어디서 끝날지 모르니 전부 보고 고른다)

dp[4](값 20으로 끝나는 경우)가 어떻게 3이 됐는지 볼까요? 앞의 원소 3, 10, 2, 1이 전부 20보다 작으니 다 후보예요. 그중 dp가 가장 큰 건 dp[1]=2(수열 [3,10])입니다. 거기에 20을 얹으니 [3,10,20], 길이 3이 되죠. 마지막에 max(dp)로 전체에서 가장 큰 값을 고르는 이유도 여기 있어요. 가장 긴 수열이 어느 원소에서 끝날지 미리 알 수 없으니, 모든 dp[i]를 다 구해 놓고 그중 최댓값을 답으로 삼는 겁니다.

코드로 확인해 볼게요. lis_n2([10,20,10,30,20,50])은 4([10,20,30,50]), lis_n2([3,10,2,1,20])은 3([3,10,20]), lis_n2([5,4,3,2,1])은 1입니다. 마지막 예는 내림차순이라 어떤 두 원소도 증가 관계가 아니에요. 그래서 각자 혼자, 최장 길이가 1이죠.

빅오를 보면, 각 i마다 그 앞의 j를 전부 훑는 이중 루프라 시간 O(n²), dp 배열 하나라 공간 O(n)입니다. "1초 1억 연산" 잣대로 n² ≈ 1억이면 n이 1만 언저리까지가 안전선이에요. 원소가 그보다 많아지면 O(n²)로는 시간 초과가 납니다. 그럴 땐 어떻게 할까요? 바로 그 이야기가 다음 Step입니다. 같은 답을 훨씬 빠르게 구하는 길이 있거든요.

💡 한 줄 정리

LIS는 dp[i]를 "arr[i]로 끝나는 가장 긴 증가 수열의 길이"로 정의하는 게 열쇠다. 앞의 모든 j 중 나보다 작은 것의 최대 dp[j]에 1을 얹고, 답은 max(dp)다. 이중 루프라 시간 O(n²)·공간 O(n)이며, n이 1만을 넘으면 더 빠른 풀이가 필요하다.

Step 4: "LIS ② — 이진 탐색으로 O(n log n)" (~20분)

Step 3의 O(n²)를 이제 눌러 낼 차례입니다. 원소가 수십만 개면 O(n²)는 손도 못 대죠. 그런데 우리에겐 무기가 하나 있어요. D-3에서 배운 이진 탐색입니다. 정렬된 배열에서 값이 들어갈 위치를 O(log n)에 찾던 그 기술을, LIS에 그대로 끌어와 O(n log n)으로 내립니다.

아이디어의 중심에 tails라는 배열이 있어요. tails[k]는 "길이 k+1인 증가 수열의 끝값 중 가능한 가장 작은 값"입니다. 왜 하필 "가장 작은 끝값"이냐면, 끝이 작을수록 그 뒤에 더 많은 원소를 이어 붙일 여지가 생기기 때문이에요. 같은 길이라면 끝이 낮은 게 유리하죠. 그리고 이 tails는 신기하게도 항상 오름차순으로 유지됩니다.

def lis_nlogn(arr):
    tails = []                          # tails[k]: 길이 k+1 증가 수열의 최소 끝값(오름차순)
    for x in arr:
        k = bisect.bisect_left(tails, x)    # D-3 이진 탐색: x가 들어갈 왼쪽 자리
        if k == len(tails):             # 기존 어떤 끝보다 커 새 길이를 연다
            tails.append(x)
        else:                           # 같은 길이를 더 작은 끝(x)으로 갈아끼운다
            tails[k] = x
    return len(tails)

원소 x를 하나씩 볼 때마다 이렇게 처리해요. bisect_left(tails, x)로 x가 들어갈 가장 왼쪽 자리 k를 이진 탐색으로 찾습니다. 그런 다음 두 갈래로 갈려요. k가 tails의 끝이면(기존 어떤 끝값보다 x가 크다는 뜻), 더 긴 수열을 새로 만든 것이라 tails 뒤에 x를 붙입니다. 끝이 아니면, tails[k]를 x로 갈아끼워요. 같은 길이의 수열을 더 작은 끝값 x로 낮춰 두는 거죠. 이렇게 계속하면 tails의 길이 자체가 곧 LIS의 길이가 됩니다.

[10, 20, 10, 30, 20, 50]을 하나씩 넣으며 tails가 어떻게 변하는지 따라가 볼게요.

 LIS O(n log n) — tails 추적, arr = [10, 20, 10, 30, 20, 50]
 tails[k] = 길이 k+1 증가 수열의 '최소 끝값'(늘 오름차순)

   x=10 → 새 길이 열기        → tails = [10]
   x=20 → 새 길이 열기        → tails = [10, 20]
   x=10 → 자리 0을 10으로 교체 → tails = [10, 20]
   x=30 → 새 길이 열기        → tails = [10, 20, 30]
   x=20 → 자리 1을 20으로 교체 → tails = [10, 20, 30]
   x=50 → 새 길이 열기        → tails = [10, 20, 30, 50]

   len(tails) = 4 = LIS 길이

세 번째 x=10을 보세요. 이미 tails=[10,20]인데 또 10이 들어오죠. bisect_left가 자리 0을 찾아 주고, tails[0]을 (원래 10인데) 10으로 갈아끼웁니다. 값은 안 바뀌지만, "길이 1짜리 수열의 최소 끝값은 10"이라는 사실이 유지돼요. 다섯 번째 x=20도 마찬가지예요. tails[1]을 20으로 갈아끼워, "길이 2짜리의 최소 끝값을 20으로" 낮춥니다. 원래도 20이라 표는 그대로지만, 이 갈아끼우기 덕분에 뒤에 더 작은 값이 와도 대응할 수 있게 되는 거죠.

여기서 ⚠️ 딱 하나 주의할 게 있어요. tails 배열은 실제 LIS 수열이 아닙니다. 최종 tails=[10,20,30,50]이 마침 실제 LIS와 같아 보이지만, 이건 우연이에요. 중간에 값을 갈아끼우다 보면 tails에 담긴 값들의 조합이 실제로는 존재하지 않는 수열일 수도 있습니다. 확실한 건 오직 하나, len(tails)(길이)만은 정확히 LIS 길이와 같다는 거예요. "길이는 맞지만 내용물은 실제 수열이 아니다" — 이 미묘한 지점은 잠시 뒤 더 깊이 파 볼 거리로 남겨 둘게요.

두 트랙을 나란히 놓아 봅시다. Step 3의 lis_n2는 직접 표를 채우는 원리 트랙이라 O(n²), 오늘의 lis_nlogn은 bisect 내장을 쓰는 실전 트랙이라 O(n log n)입니다. D-3에서 정렬된 배열에 bisect로 자리를 찾던 그 감각이 그대로 회수됐죠. 두 함수는 모든 입력에서 같은 길이를 냅니다. lis_nlogn([10,20,10,30,20,50])은 O(n²)와 똑같이 4, lis_nlogn([5,4,3,2,1])은 1이에요.

빅오로 마무리할게요. 원소 n개 각각에 대해 tails(길이 최대 n)를 이진 탐색하니 시간 O(n log n), tails 배열 하나라 공간 O(n)입니다. O(n²)가 n 1만에서 벽에 부딪혔다면, O(n log n)은 n이 수십만에서 백만이어도 여유롭게 돌아요. "원소가 많으면 O(n²)는 버리고 bisect로 간다" — 이게 LIS를 만났을 때의 실전 판단입니다.

💡 한 줄 정리

LIS는 tails[k]("길이 k+1 수열의 최소 끝값")를 bisect_left로 관리하면 O(n²)에서 O(n log n)으로 내려간다. 끝이면 append, 아니면 갈아끼우기. len(tails)가 곧 LIS 길이이며, tails 자체는 실제 LIS 수열이 아니라 길이만 정확하다.

Step 5: "최장 공통 부분 수열(LCS) — 2차원 표" (~20분)

지난 시간 마지막에 제가 이런 말을 흘려 뒀습니다. "두 문자열이 얼마나 닮았는지 재는 문제는 첫 문자열의 몇 번째, 둘째 문자열의 몇 번째를 함께 들고 가야 해서 dp[i][j] 2차원 표가 필요하다"고요. 이번에 그 문제를 정면으로 풀어 봅니다. 이름은 최장 공통 부분 수열(LCS, Longest Common Subsequence)입니다.

문제는 이래요. 두 문자열이 있을 때, 양쪽 모두에서 순서를 지키며 골라낼 수 있는 가장 긴 공통 부분 수열의 길이를 구합니다. Step 3에서 잡은 "부분 수열"의 정의를 그대로 씁니다. 연속으로 붙어 있을 필요는 없고, 사이를 건너뛰어도 됩니다. 예를 들어 "ACAYKP"와 "CAPCAK"에서 A → C → A → K는 양쪽 순서를 모두 지키는 공통 부분 수열이에요.

상태 정의부터 세웁시다. dp[i][j]를 "a의 앞 i글자와 b의 앞 j글자 사이 LCS 길이"로 둡니다. 두 문자열의 "몇 번째까지 봤나"가 각각 하나의 축이 되니, 배낭의 물건 축·무게 축과 똑같이 표가 2차원으로 펼쳐지죠.

# algorithms/dp.py
def lcs_length(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]      # (a 축 i) × (b 축 j) 표
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:    # 끝 글자가 같다 — 공통으로 채택하고 대각선 +1
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:                       # 다르다 — 한쪽 끝을 버린 두 경우 중 큰 값
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

점화식을 말로 풀어 볼게요. dp[i][j]를 채울 때 우리가 보는 건 a의 i번째 글자와 b의 j번째 글자, 두 끝 글자예요. 이 둘이 같으면 그 글자를 공통으로 채택하고, 양쪽에서 한 칸씩 물러난 대각선 dp[i-1][j-1]에 1을 더합니다. 다르면 둘 중 하나는 답에 못 들어가니, a의 끝을 버린 dp[i-1][j](위)와 b의 끝을 버린 dp[i][j-1](왼쪽) 두 경우 중 큰 값을 물려받아요.

표를 실제로 채워 보면 흐름이 눈에 들어옵니다. "ACAYKP"(세로 축)와 "CAPCAK"(가로 축)로 채운 표예요.

 LCS 표 — a="ACAYKP"(세로) × b="CAPCAK"(가로)
 dp[i][j] = a 앞 i글자와 b 앞 j글자의 LCS 길이

         j:  ""  C   A   P   C   A   K
   i ""       0   0   0   0   0   0   0
     A        0   0   1   1   1   1   1
     C        0   1   1   1   2   2   2
     A        0   1   2   2   2   3   3
     Y        0   1   2   2   2   3   3
     K        0   1   2   2   2   3   4
     P        0   1   2   2   3   3  [4]
                                     └ dp[6][6] = 4 (ACAK)

칸 두 개만 뜯어보면 두 갈래가 확실해져요. 하나는 끝 글자가 같은 경우, 하나는 다른 경우입니다.

 끝 글자가 같을 때 vs 다를 때 (칸 하나 뜯어보기)

 dp[3][5]: a 3번째 'A' == b 5번째 'A' (같다)
   → 대각선 dp[2][4] + 1 = 2 + 1 = 3   (공통 글자 하나 채택)

 dp[6][6]: a 6번째 'P' != b 6번째 'K' (다르다)
   → max(위 dp[5][6]=4, 왼쪽 dp[6][5]=3) = 4   (한쪽 끝 버림)

표의 오른쪽 아래 끝 칸 dp[6][6]이 전체 답 4입니다. 코드로 확인하면 lcs_length("ACAYKP","CAPCAK")는 4(ACAK)를 냅니다. 겹치는 글자가 하나도 없는 lcs_length("abc","xyz")는 0, 두 문자열이 완전히 같은 lcs_length("abc","abc")는 당연히 3이에요.

빅오를 따져 봅시다. (m+1)×(n+1) 표를 한 번씩 채우니 시간 O(m×n), 표를 통째로 들고 있으니 공간 O(m×n)입니다. "1초에 약 1억 연산" 잣대로 두 문자열 길이의 곱이 1억 언저리까지 안전선이에요. 코딩테스트 앵글로 보면 이 골격이 DNA 서열 비교, 파일 차이를 보여 주는 diff, 문서 유사도 측정에 그대로 쓰입니다. "두 데이터가 얼마나 겹치나"를 물으면 LCS를 먼저 떠올리면 됩니다.

두 트랙 이야기도 짚을게요. 배낭과 마찬가지로 LCS도 파이썬 표준 라이브러리에 함수가 따로 없어서, 이 유형은 직접 표를 채우는 게 곧 실전입니다. 대신 다음 Step에서 볼 것처럼, 같은 표를 어떻게 활용하느냐(길이만 구하나, 실제 문자열까지 뽑나)에서 갈래가 나뉩니다.

💡 한 줄 정리

LCS는 dp[i][j]를 "a 앞 i글자와 b 앞 j글자의 공통 부분 수열 길이"로 두는 2차원 DP다. 두 끝 글자가 같으면 대각선 dp[i-1][j-1]+1, 다르면 위·왼쪽 중 큰 값을 물려받는다. 시간·공간 모두 O(m×n)이며, dp[m][n]이 전체 답이다.

Step 6: "LCS 문자열 복원 — 역추적" (~20분)

Step 5에서 우리는 두 문자열이 "얼마나" 닮았는지(길이 4)를 구했습니다. 그런데 실무나 코딩테스트에서는 한 걸음 더 나아가 "무엇이 닮았나", 즉 실제 공통 조각(ACAK) 자체를 뽑아야 할 때가 많아요. 길이라는 숫자를 넘어 답의 내용물을 복원하는 겁니다.

이건 우리가 이미 한 번 해 본 발상이에요. 지난 시간(E-4) 과제에서 make_1을 풀 때, 연산 횟수만 담긴 DP 표를 끝에서 되짚어 "실제로 어떤 연산을 거쳤는지" 경로를 복원해 봤죠. 그때는 1차원 표를 되짚었는데, 이번엔 그 되짚기를 2차원으로 확장합니다.

방법은 이래요. 표는 Step 5와 똑같이 채운 뒤, 오른쪽 아래 끝 칸 (i=m, j=n)에서 출발해 화살표를 거꾸로 되짚어 올라옵니다. 끝 글자가 같아서 대각선으로 내려온 칸이면, 그 글자가 답에 채택된 것이니 주워 담아요.

# algorithms/dp.py  (lcs_reconstruct — 표를 lcs_length처럼 채운 뒤)
    i, j = m, n                         # 오른쪽 아래 끝에서 시작해 화살표를 되짚는다
    chosen = []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:        # 공통 글자다 — 채택하고 대각선으로
            chosen.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:  # 같으면 위 우선 — 결정적 하나를 고른다
            i -= 1
        else:
            j -= 1
    chosen.reverse()                    # 끝→앞으로 모았으니 뒤집으면 원래 순서
    return "".join(chosen)

되짚는 규칙을 정리하면 세 갈래예요. 끝 글자가 같으면 그 글자를 채택하고 대각선으로 물러납니다. 다르면 이 칸의 값이 어느 이웃에서 왔는지를 봐야 하는데, dp[i-1][j] >= dp[i][j-1]이면 위로, 아니면 왼쪽으로 갑니다. 여기서 "같으면 위 우선(>=)"이라는 규칙이 중요해요. 값이 같은 이웃이 여럿일 때 늘 같은 선택을 하게 만들어, 여러 정답 후보 중 딱 하나를 결정적으로 뽑게 해 줍니다.

"ACAYKP"와 "CAPCAK"의 표를 끝에서 되짚어 가는 경로를 따라가 볼게요.

 역추적 경로 (6,6) → (0,0), 대각선 이동 = 글자 채택

 (6,6) P!=K  위로↑
 (5,6) K==K  대각선↖ 채택 → K
 (4,5) Y!=A  위로↑
 (3,5) A==A  대각선↖ 채택 → A
 (2,4) C==C  대각선↖ 채택 → C
 (1,3) A!=P  왼쪽←
 (1,2) A==A  대각선↖ 채택 → A
 (0,1) 끝

 채택 순서 K, A, C, A → 뒤집으면 "ACAK"

글자를 끝에서 앞 방향으로 모았으니, 마지막에 chosen.reverse()로 뒤집어야 원래 순서인 ACAK가 됩니다. 코드로 확인하면 lcs_reconstruct("ACAYKP","CAPCAK")는 "ACAK", lcs_reconstruct("ABCBDAB","BDCAB")는 "BCAB"를 냅니다. 두 결과 모두 길이는 Step 5가 구한 길이와 정확히 같으면서, a와 b 양쪽의 부분 수열이라는 조건을 만족해요.

⚠️ 여기서 트레이드오프를 하나 못 박고 갑시다. 이렇게 역추적을 하려면 2차원 표 전체가 메모리에 남아 있어야 합니다. 끝 칸에서 시작해 위·왼쪽·대각선 이웃을 계속 되짚어야 하니, 표를 한 줄로 접으면 되짚을 이웃이 사라지거든요. Step 2에서 배낭 표를 1차원으로 접었을 때를 떠올려 보세요. 그때는 공간을 O(capacity)까지 줄여 최대 가치(값)를 잘 구했지만, "무엇을 담았는지"(경로)는 되짚을 수 없었습니다. 값만 필요하면 공간을 접고, 경로까지 필요하면 표를 남긴다 — 이 저울질은 잠시 뒤 더 깊이 파 볼 거리로 남겨 둘게요.

빅오를 보면, 표를 채우는 데 시간 O(m×n)이 들고 여기가 지배적입니다. 끝 칸에서 한 칸씩 물러나는 복원은 최대 m+n걸음이라 O(m+n) 추가에 그쳐요. 표를 들고 있어야 하니 공간 O(m×n)입니다. 길이만 구하는 Step 5와 시간·공간 빅오가 같은데, "값 대신 경로"를 얻기 위해 표를 접는 최적화를 포기했다는 게 차이예요.

💡 한 줄 정리

LCS 문자열 복원은 채운 표의 끝 칸에서 화살표를 거꾸로 되짚어, 대각선으로 내려온(끝 글자가 같은) 칸의 글자를 모은 뒤 뒤집는다. "같으면 위 우선(>=)" 규칙으로 결정적 하나를 고른다. 되짚으려면 2차원 표 전체가 남아 있어야 해서, 값만 필요할 때처럼 공간을 접을 수 없다.

Step 7: "편집 거리 — 두 문자열의 거리" (~20분)

LCS에는 아주 가까운 사촌이 하나 있어요. 바로 편집 거리(edit distance, Levenshtein distance)입니다. 두 문자열이 얼마나 닮았는지를 "공통 조각의 길이"가 아니라 "하나를 다른 하나로 바꾸는 데 드는 최소 연산 수"로 재는 방법이에요. 쓸 수 있는 연산은 글자 하나 삽입, 삭제, 교체 세 가지이고 각각 비용 1입니다.

구조는 LCS와 놀랍도록 닮았습니다. 같은 크기의 2차원 표를 쓰고, dp[i][j]를 "a의 앞 i글자를 b의 앞 j글자로 바꾸는 최소 연산 수"로 둬요. 다른 점은 최댓값을 찾던 LCS와 달리, 편집 거리는 최솟값을 찾는다는 것입니다. E-4에서 거스름돈을 min형 점화식으로 풀던 감각이 여기서 되살아나죠.

# algorithms/dp.py
def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                    # a의 i글자 → 빈 문자열: 전부 삭제(i번)
    for j in range(n + 1):
        dp[0][j] = j                    # 빈 문자열 → b의 j글자: 전부 삽입(j번)
    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]
            else:                       # 삭제·삽입·교체 세 갈래 중 최소 + 1
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

점화식을 뜯어볼게요. 두 끝 글자가 같으면 손댈 필요가 없으니 대각선 dp[i-1][j-1]을 그대로 물려받습니다(연산 0). 다르면 세 갈래 중 가장 싼 방법에 연산 1을 더해요. a의 끝 글자를 지우거나(위 dp[i-1][j], 삭제), b의 끝 글자를 새로 끼워 넣거나(왼쪽 dp[i][j-1], 삽입), a의 끝을 b의 끝으로 바꿔치기(대각선 dp[i-1][j-1], 교체)입니다.

경계 줄도 짚고 가야 해요. dp[i][0]=i는 "a의 i글자를 빈 문자열로 만들려면 전부 삭제(i번)", dp[0][j]=j는 "빈 문자열에서 b의 j글자를 만들려면 전부 삽입(j번)"이라는 뜻입니다. 한쪽이 비었을 때의 거리를 미리 채워 둬야 나머지 칸들이 그 위에 쌓입니다.

세 갈래가 각각 어떤 연산인지 그림으로 정리하면 이래요.

 편집 거리 — 끝 글자가 다를 때 세 갈래(칸 하나 뜯어보기)

   대각선 dp[i-1][j-1]  -- 교체(a의 끝을 b의 끝으로 바꿔치기)
   위     dp[i-1][j]    -- 삭제(a의 끝 글자 지우기)
   왼쪽   dp[i][j-1]    -- 삽입(b의 끝 글자 끼워 넣기)

   dp[i][j] = 1 + min(세 갈래)
   끝 글자가 같으면? 연산 0 — 대각선 값을 그대로 물려받는다

코드로 확인해 볼게요. edit_distance("kitten","sitting")은 3입니다(k→s 교체, e→i 교체, 끝에 g 삽입). edit_distance("sunday","saturday")도 3, 한쪽이 빈 edit_distance("","abc")는 세 글자를 전부 삽입해야 하니 3이에요.

빅오는 LCS와 판박이입니다. (m+1)×(n+1) 표를 채우니 시간 O(m×n)·공간 O(m×n), "1초 1억 연산" 잣대로 길이 곱 1억 언저리까지 안전선이에요. 둘이 같은 크기·같은 복잡도인 건 우연이 아니라, 편집 거리와 LCS가 사실상 같은 2차원 DP의 두 얼굴이기 때문입니다. 코딩테스트·실무 앵글로 보면 이 알고리즘이 맞춤법 교정, 검색어 오타 보정("이거 찾으셨나요?"), 자동완성의 거리 계산에서 그대로 돌아갑니다.

💡 한 줄 정리

편집 거리는 a를 b로 바꾸는 삽입·삭제·교체의 최소 횟수를 LCS와 같은 크기의 2차원 표로 구한다. 끝 글자가 같으면 대각선을 그대로, 다르면 1 + min(위 삭제, 왼쪽 삽입, 대각선 교체)다. 경계는 dp[i][0]=i, dp[0][j]=j이며 시간·공간 모두 O(m×n)이다.

Step 8: "구간 DP 맛보기 — 행렬 곱셈 순서" (~25분)

오늘 우리가 본 2차원 표는 두 종류였어요. 배낭은 "물건 × 무게" 축, LCS·편집 거리는 "문자열 × 문자열" 축이었습니다. 이번엔 조금 다른 종류의 2차원을 맛봅니다. 두 축이 "구간의 시작 × 구간의 끝"인 DP예요. 이런 유형을 구간 DP(interval DP)라고 부릅니다.

문제는 행렬 연쇄 곱셈입니다. 행렬 여러 개를 곱할 때, 곱셈은 결합법칙이 성립해서 (AB)C든 A(BC)든 최종 결과는 똑같아요. 그런데 중간에 드는 곱셈 횟수는 괄호를 어디에 치느냐에 따라 크게 달라집니다. 우리는 그 곱셈 횟수를 최소로 만드는 괄호 배치의 비용을 구합니다.

# algorithms/dp.py
def matrix_chain_order(dims):
    n = len(dims) - 1                   # 행렬 개수
    if n <= 1:                          # 행렬이 0개·1개면 곱할 게 없다
        return 0
    dp = [[0] * (n + 1) for _ in range(n + 1)]      # dp[i][j]: i..j 구간 최소 비용
    for length in range(2, n + 1):      # 구간 길이를 2부터 늘려 간다(작은 구간 먼저)
        for i in range(1, n - length + 2):
            j = i + length - 1          # 길이 length인 구간 [i, j]
            dp[i][j] = float("inf")
            for k in range(i, j):       # 마지막에 [i,k] | [k+1,j]로 가르는 지점을 전부
                cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost     # 가장 싸게 가르는 방법을 채택
    return dp[1][n]

dims가 행렬들의 크기를 잇대어 담은 목록이에요. 길이가 n+1이면 행렬은 n개고, i번째 행렬 크기는 dims[i-1] × dims[i]입니다. dp[i][j]는 "i번째부터 j번째 행렬까지 곱하는 최소 비용"이고요. 핵심은 그 구간을 마지막에 어디서 둘로 가를지(k)를 전부 시도하는 거예요. 왼쪽 덩어리 dp[i][k], 오른쪽 덩어리 dp[k+1][j], 그리고 둘을 합칠 때 드는 dims[i-1]*dims[k]*dims[j]의 합 중 가장 작은 값을 채택합니다.

여기서 구간 DP의 특징이 하나 드러나요. 큰 구간을 채우려면 그 안의 작은 구간 값들이 먼저 준비돼 있어야 합니다. 그래서 구간 길이를 2부터 늘려 가며 짧은 구간부터 채웁니다.

 구간 DP 채우기 순서 — 짧은 구간부터

 length=2 : dp[1][2], dp[2][3]   (이웃 두 행렬)
 length=3 : dp[1][3]             (앞의 작은 구간 값들이 준비돼야 채워진다)
             └ k=1: dp[1][1] + dp[2][3] + ... = 27000
               k=2: dp[1][2] + dp[3][3] + ... =  4500  ← 채택

괄호 위치가 비용을 얼마나 가르는지, 세 행렬 A(10×30) · B(30×5) · C(5×60)로 눈으로 보겠습니다.

 A(10×30) · B(30×5) · C(5×60) — 괄호 위치로 곱셈 횟수가 갈린다

 (A B) C :  A·B = 10*30*5 = 1500,  그 결과(10×5)·C = 10*5*60 = 3000
            합 1500 + 3000 = 4500   ← 최소

 A (B C) :  B·C = 30*5*60 = 9000,  A·그 결과(30×60) = 10*30*60 = 18000
            합 9000 + 18000 = 27000

 결과 행렬은 같지만 비용은 6배 차이 — dp[1][3] = 4500

코드로 확인하면 matrix_chain_order([10,30,5,60])은 4500((AB)C), matrix_chain_order([40,20,30,10,30])은 26000, 행렬이 두 개뿐이라 곱하는 순서가 하나밖에 없는 matrix_chain_order([5,10,3])은 150입니다.

빅오를 봅시다. 구간 (i, j) 쌍이 O(n²)개이고, 각 구간마다 가르는 지점 k를 O(n)번 훑으니 시간 O(n³), 표 하나라 공간 O(n²)입니다. "1초 1억 연산" 잣대로 n³이 1억이면 행렬 수 n이 400~500 언저리까지가 안전선이에요. 구간을 쪼개 최적으로 합치는 이 골격은 팰린드롬 분할, 돌 합치기 같은 다른 구간 DP 유형으로 그대로 이어집니다.

마지막으로 다음 여정을 살짝 열어 둘게요. DP에는 상태를 "방문한 집합"처럼 비트로 압축해서 표현하는 비트마스크 DP도 있습니다. 상태를 어떻게 정의하고 압축하느냐가 DP의 절반이라는 감각, 그 감각이 앞으로 만날 고급 그래프에서 집합과 순서를 다루는 알고리즘(F-2)으로 자연스럽게 이어집니다.

💡 한 줄 정리

구간 DP는 두 축이 "구간의 시작 × 끝"인 2차원 DP다. 행렬 연쇄 곱셈은 구간을 마지막에 가르는 지점 k를 전부 시도해 dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]의 최소를 고른다. 짧은 구간부터 채워야(길이 2→n) 큰 구간이 참조할 값이 준비되며, 시간 O(n³)·공간 O(n²)이다.

마무리

오늘은 상태가 하나 늘어 표가 2차원으로 넓어진 세계를 죽 훑었습니다. 배낭, LIS, LCS, 편집 거리, 구간 DP까지 — 겉모습은 저마다 달라 보여도, 전부 "상태 정의 → 점화식 → 표 채우기"라는 같은 뼈대 위에 서 있었죠. 핵심 세 가지로 정리하겠습니다.

오늘 배운 핵심 세 가지

💡 하나 — 상태가 둘이면 표가 2차원이다. 배낭은 "물건 × 무게", LCS·편집 거리는 "두 문자열의 위치", 구간 DP는 "구간의 시작 × 끝"을 두 축으로 삼았습니다. E-4에서 못 박은 "상태 정의가 점화식을 결정한다"는 원칙이, 축이 하나 늘었을 뿐 그대로 한 차원 위로 올라온 거예요. 처음 보는 문제에서 "상태를 숫자 하나로 못 담겠다" 싶으면 2차원 표를 의심하면 됩니다.

💡 둘 — 2차원도 공간을 접고 시간을 줄인다. 배낭 표는 바로 윗줄만 참조하니 한 줄로 접어 공간을 O(W)까지 낮췄고(단, 값만 남기면 경로 역추적을 잃습니다), LIS는 이진 탐색으로 O(n²)를 O(n log n)까지 눌렀습니다. "표가 크면 못 푼다"에서 멈추지 말고, 무엇을 참조하는지 들여다보면 접거나 빠르게 할 여지가 보여요.

💡 셋 — 값 너머 "무엇이 답인지"는 역추적으로 복원한다. 편집 거리나 LCS의 길이(값)를 넘어 실제 공통 문자열(내용물)이 필요할 때는, 채운 표의 끝 칸에서 화살표를 거꾸로 되짚습니다. 이 LCS 문자열 복원이 지난 시간 make_1 경로 복원을 2차원으로 확장한 것이었죠. 값이냐 경로냐에 따라 공간을 접을지 남길지가 갈립니다.

다음 시간 예고

다음 시간(F-1)부터는 지금까지 쌓아 온 자료구조와 패러다임이 한데 모이는 고급 그래프로 넘어갑니다. 분량이 커서 두 번에 나눠 다뤄요. 먼저 최단 경로편에서는 가중치 그래프에서 가장 짧은 길을 찾는 다익스트라(C-2에서 배운 힙을 우선순위 큐로 회수합니다)와, 실제로 어느 길로 갔는지 되짚는 경로 복원, 그리고 음수 간선이나 모든 쌍의 거리를 다루는 벨만-포드·플로이드-워셜을 만납니다. 이어지는 집합·순서편(F-2)에서는 원소들이 같은 집합인지 빠르게 판별하는 유니온 파인드, 순서 제약이 있는 작업을 나열하는 위상 정렬, 그래프를 최소 비용으로 잇는 최소 신장 트리(MST)를 다뤄요.

오늘 Step 8 끝에서 흘린 "상태 압축"의 감각, 그리고 지금까지 다진 힙·큐·재귀·그리디·DP가 F에서 종합됩니다. 알고리즘 본격 구현은 다음 시간에 만나요.

과제

오늘 배운 2차원 DP를 직접 손으로 짜 보며 굳히는 과제입니다. 각 문제는 스스로 상태를 정의하고 점화식을 세우는 게 핵심이에요. 답을 내는 데 그치지 말고, 자신이 짠 풀이의 시간·공간 빅오를 반드시 함께 따져 보세요.

[기초] 격자에서 최소 비용으로 내려가기

grid_min_path_sum(grid)를 구현하세요. grid는 음이 아닌 정수로 채워진 m×n 격자입니다. 좌상단 (0,0)에서 출발해 우하단 (m-1,n-1)까지, 오른쪽 또는 아래로만 이동하면서 지나온 칸의 값을 모두 더할 때, 그 합의 최솟값을 구합니다.

예를 들어 grid_min_path_sum([[1,3,1],[1,5,1],[4,2,1]])은 7이에요(1 → 1 → 4 → 2 → ... 가 아니라, 1 → 3 → 1 → 1 → 1 경로가 합 7로 최소).

• 힌트 1: dp[i][j]를 "(0,0)에서 (i,j)까지의 최소 합"으로 정의해 보세요. 어느 방향에서 이 칸에 도착할 수 있나요?
• 힌트 2: 점화식은 dp[i][j] = grid[i][j] + min(위 dp[i-1][j], 왼쪽 dp[i][j-1]) 꼴이 됩니다. 첫 행과 첫 열은 올 수 있는 방향이 하나뿐이니 따로 처리하세요.
• 힌트 3: 배낭처럼 이 표도 바로 윗줄만 참조합니다. 공간을 한 줄로 접어 O(n)까지 줄일 수 있을지 생각해 보세요. 시간 빅오는 얼마인가요?

[응용] 이번엔 "연속"으로 붙은 공통 조각

longest_common_substring(a, b)를 구현하세요. Step 5의 LCS는 사이를 건너뛴 부분 수열의 최장 길이였습니다. 이번엔 대조적으로, 두 문자열에서 연속으로 붙어 있는 공통 부분 문자열(substring)의 최장 길이를 구합니다.

예를 들어 longest_common_substring("ABABC","BABCA")는 4예요(BABC가 양쪽에 연속으로 들어 있음).

• 힌트 1: dp[i][j]를 "a의 i번째, b의 j번째 글자로 끝나는 공통 연속 부분 문자열의 길이"로 정의해 보세요. LIS에서 "끝을 고정"하던 발상과 닮았습니다.
• 힌트 2: 끝 글자가 같으면 dp[i][j] = dp[i-1][j-1] + 1입니다. 그런데 다를 때가 LCS와 결정적으로 달라요. 연속이 끊겼으니 max가 아니라 0으로 리셋해야 합니다. 왜 0인지 곱씹어 보세요.
• 힌트 3: 답은 dp[m][n] 한 칸이 아니라 표 전체의 최댓값입니다(공통 조각이 어디서 끝날지 모르니까요). 시간·공간 빅오는 LCS와 같을까요, 다를까요?

[심화] 올라갔다 내려오는 가장 긴 봉우리

longest_bitonic_subsequence(arr)를 구현하세요. 바이토닉(bitonic) 부분 수열은 어느 지점까지 증가하다가 그 뒤로 감소하는 수열입니다(한쪽만 있어도 됩니다). 그중 가장 긴 것의 길이를 구합니다.

예를 들어 longest_bitonic_subsequence([1,2,5,3,2])는 5(전체가 1→2→5→3→2로 봉우리), longest_bitonic_subsequence([1,11,2,10,4,5,2,1])은 6이에요.

• 힌트 1: 각 정점 i를 "봉우리의 꼭대기"라고 상상해 보세요. 꼭대기 왼쪽은 증가, 오른쪽은 감소여야 합니다.
• 힌트 2: 왼쪽에서 오른쪽으로 훑어 "i에서 끝나는 증가 LIS 길이" inc[i]를, 오른쪽에서 왼쪽으로 훑어 "i에서 시작하는 감소 수열 길이" dec[i]를 각각 구하세요. Step 3의 LIS를 양방향으로 두 번 돌리는 셈입니다.
• 힌트 3: 정점 i를 꼭대기로 하는 바이토닉 길이는 inc[i] + dec[i] - 1입니다(꼭대기 i가 양쪽에서 한 번씩 세어져 1을 뺍니다). 답은 이 값의 최댓값이에요. 각 방향이 O(n²)이면 전체 시간 빅오는 얼마인가요?

생각해볼 주제

정답 코드를 짜는 것을 넘어, "왜 이렇게 되는가"를 파고드는 질문들입니다. 혼자 곰곰이 생각해도 좋고, 스터디에서 서로의 논리를 부딪쳐 봐도 좋아요. 이런 질문에 스스로 답할 수 있으면 DP를 정말 이해한 겁니다.

1. 배낭 1차원 롤링은 왜 하필 "역순"이어야 할까

Step 2에서 배낭을 한 줄로 접을 때, 무게 루프를 큰 쪽에서 작은 쪽으로 역순으로 돌았습니다. 만약 이걸 정순(작은 무게 → 큰 무게)으로 바꾸면 답이 어떻게 달라질까요? 그리고 그 "달라진 답"이 사실은 각 물건을 개수 제한 없이 담을 수 있는 다른 문제(무한 개수 배낭)의 정답이 되는 이유는 무엇일까요? 루프 방향 한 글자가 "각 물건을 한 번만"이라는 0/1 조건과 어떻게 연결되는지, 표를 손으로 그려 가며 따져 보세요.

2. 공간을 접으면 잃는 것 — 값과 경로의 트레이드오프

배낭 표를 1차원으로 접으면 최대 가치(값)는 구하지만, "무엇을 담았는지"(경로)는 되짚지 못합니다. 반대로 Step 6의 LCS 문자열 복원은 2차원 표 전체가 남아 있어야 했죠. 값만 필요할 때와 경로까지 필요할 때, 공간을 어디까지 줄여도 되는지를 어떻게 판단할까요? 실무에서 메모리가 빠듯한 상황이라면 이 저울질을 어떤 기준으로 내릴지 생각해 보세요.

3. 처음 보는 문제가 "2차원 DP"인지 어떻게 알아챌까

똑같이 DP 문제여도, 어떤 건 1차원 배열로 풀리고 어떤 건 2차원 표가 필요합니다. 상태를 숫자 하나로 못 담고 둘이 필요하다는 신호(두 대상의 위치를 함께 들어야 함, "물건 + 남은 자원 한도"처럼 값 두 개가 얽힘)를 어떻게 감지할 수 있을까요? E-4에서 잡은 "상태 하나면 1차원, 여럿이면 2차원"과 A-1의 입력 크기 잣대를 엮어, 문제를 처음 봤을 때 차원을 판별하는 자신만의 감각을 정리해 보세요.