← --library
이과 · 18이과

알고리즘 및 고급 자료구조

단계1단계2단계3단계4단계5

2단계: 고급 자료구조와 알고리즘 — 진짜 세계의 문제를 푸는 법

이론적 기초 — 왜 우리는 이것을 배우는가?

1단계에서 우리는 Big-O 표기법으로 알고리즘의 속도를 수학적으로 분석했고, 그래프·트리·DP가 어떻게 최적 결정을 내리는지 배웠다. 그 지식을 머릿속에 꺼내놓고 지금부터 던질 질문을 들어라.

배열 A = [1, 3, 5, 2, 8, 4, 7, 6]이 있다. "인덱스 2번부터 6번까지의 합은?" 쉽다, 다 더하면 된다. O(n)이다. 그런데 이 질문이 1초에 100만 번 들어오고, 동시에 배열의 값도 계속 바뀐다면? 단순 합산으로는 절대 감당이 안 된다. 이것이 세그먼트 트리가 탄생한 이유다. 수백만 줄의 서버 로그에서 "ERROR"라는 단어를 찾아야 한다고 상상해보라. 텍스트가 1억 글자이고 패턴이 100글자면, 한 글자씩 비교하는 Naive 방법은 최악의 경우 100억 번 비교가 필요하다. KMP와 Aho-Corasick은 이것을 O(텍스트 길이 + 패턴 길이)로 줄여버린다. 마지막으로, 10명의 작업자와 10대의 기계가 있고 각 작업자는 특정 기계만 다룰 수 있을 때 가장 많은 쌍을 만들려면? 이것은 그래프 위의 물의 흐름, 즉 네트워크 플로우로 변환되어 우아하게 풀린다.

이 세 주제 — 구간 쿼리, 문자열 매칭, 네트워크 플로우 — 는 실전 알고리즘의 핵심 삼각형을 이룬다. 이 삼각형을 완전히 이해하면 대부분의 경쟁 프로그래밍 문제를 풀 수 있고, 현업에서도 즉시 써먹을 수 있다. 지금 이 순간부터 이 세 문제를 머릿속 한쪽에 항상 걸어두고 읽어나가라.

Part 1: 구간 쿼리 — 트리로 배열을 정복하다

근본 충돌: 조회 vs. 갱신

배열을 다루다 보면 항상 두 연산이 충돌한다: **조회(Query)**와 갱신(Update). 단순 배열에서 조회는 O(n)이고 갱신은 O(1)이다. 1단계에서 배운 **누적 합(Prefix Sum)**은 조회를 O(1)으로 만들어주지만 갱신이 O(n)이 된다. 왜냐하면 배열의 한 값이 바뀌면 그 뒤의 모든 누적 합을 다시 계산해야 하기 때문이다. "조회도 빠르고 갱신도 빠른" 것이 불가능해 보이지 않는가? 실제로 둘 다 O(1)으로 만드는 것은 불가능함이 알려져 있다. 하지만 O(log n)은 가능하다. 그 비결은 바로 '분할'이다.

[노트 기록] 방법별 성능 비교표 — 이 표가 이번 Part의 지도다:

방법 구간 조회 점 갱신 구간 갱신
단순 배열 O(n) O(1) O(n)
누적 합 O(1) O(n) O(n)
세그먼트 트리 O(log n) O(log n) O(log n) — Lazy 필요
펜윅 트리 O(log n) O(log n) 제한적
희소 테이블 O(1) — RMQ만 없음(정적) 없음(정적)

세그먼트 트리 (Segment Tree)

7살짜리 동생에게 설명한다고 상상해보자. 100개의 사탕 더미가 있는데, 선생님이 "10번째부터 50번째 더미를 모두 더하면?"이라고 물었다. 매번 41개 더미를 일일이 세는 대신, 미리 "1번50번 합", "1번25번 합", "1번~12번 합" 같은 중간 결과를 종이에 적어두면 어떨까? 이 중간 결과들을 트리 형태로 계층화한 것이 세그먼트 트리다.

배열 A = [1, 3, 5, 2, 8, 4, 7, 6]로 구체적으로 들어가보자. 루트 노드는 전체 배열의 합(36)을 저장한다. 루트의 왼쪽 자식은 인덱스 03의 합(11)을, 오른쪽 자식은 인덱스 47의 합(25)을 저장한다. 이 분할이 재귀적으로 계속되어 리프 노드가 각 원소 자체가 될 때까지 이어진다. 크기 n인 배열에 대해 세그먼트 트리는 약 4n개의 노드를 사용하며, 트리의 깊이는 log₂n이다. 어떤 구간 [l, r]에 대한 쿼리도 최대 O(log n)번의 노드 방문으로 해결된다. 왜 그럴까? 각 깊이 수준에서 쿼리 구간과 겹치는 노드는 최대 4개뿐이다. 이 "최대 4개"가 왜 성립하는지 직접 종이에 그려서 확인해보라 — 이것이 스스로 이해하는 방식이다.

[노트 기록] 세그먼트 트리 구현의 세 핵심 함수:

def build(node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build(2*node, start, mid)
        build(2*node+1, mid+1, end)
        tree[node] = tree[2*node] + tree[2*node+1]

def query(node, start, end, l, r):
    if r < start or end < l:  # 완전히 벗어남
        return 0
    if l <= start and end <= r:  # 완전히 포함됨
        return tree[node]
    mid = (start + end) // 2  # 부분 겹침 → 분할
    return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r)

def update(node, start, end, idx, val):
    if start == end:
        arr[idx] = val
        tree[node] = val
    else:
        mid = (start + end) // 2
        if idx <= mid:
            update(2*node, start, mid, idx, val)
        else:
            update(2*node+1, mid+1, end, idx, val)
        tree[node] = tree[2*node] + tree[2*node+1]

이 코드에서 2*node와 2*node+1은 왼쪽/오른쪽 자식 노드다. 이진 트리를 배열로 표현하는 고전적 방법이다. query 함수의 세 경우 — 완전 벗어남, 완전 포함, 부분 겹침 — 를 완전히 이해하면 세그먼트 트리의 80%는 이해한 것이다.

Lazy Propagation (지연 전파) — 이것은 진짜 프로급 기술이다. "인덱스 2~6의 모든 값에 10을 더하라"는 구간 갱신 쿼리가 들어오면 어떻게 할까? 원소 하나씩 update를 호출하면 O(n log n)이 된다. Lazy Propagation의 아이디어는 **"갱신 정보를 노드에 기록해두고, 실제로 그 자식을 방문해야 할 때만 아래로 전파한다"**는 것이다. 즉, 할 일을 미루다가 꼭 필요할 때 한다. 이렇게 하면 구간 갱신도 O(log n)이 된다. 구현은 약간 복잡하지만 아이디어는 이것이 전부다.

펜윅 트리 (Fenwick Tree / Binary Indexed Tree, BIT)

세그먼트 트리는 강력하지만 코드가 복잡하다. 1994년 Peter Fenwick이 발표한 펜윅 트리는 같은 O(log n) 성능을 훨씬 간단한 코드로 달성한다. 비결은 비트 연산이다.

핵심 개념: 펜윅 트리에서 인덱스 i의 노드는 i에서 i - (i & -i) + 1까지의 구간 합을 저장한다. 여기서 i & -i는 i를 이진수로 표현했을 때 **가장 낮은 비트(Lowest Set Bit)**를 의미한다. 예를 들어 i = 6 = 110₂이면, 6 & -6 = 010₂ = 2이므로, 인덱스 6은 인덱스 56의 합을 저장한다. 처음에는 마법처럼 보일 것이다. 인덱스 18까지 각각 어떤 구간을 커버하는지 직접 이진수로 써가며 계산해보라 — 패턴이 보이기 시작할 것이다.

[노트 기록] 펜윅 트리 핵심 연산 (1-indexed):

def update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & (-i)   # 부모 방향으로 이동

def query(i):            # 1~i 까지의 합
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & (-i)   # 이전 구간으로 이동
    return s

def range_query(l, r):   # l~r 구간 합
    return query(r) - query(l - 1)

세그먼트 트리와 비교했을 때, 펜윅 트리는 코드가 극도로 짧고 상수 factor가 작아서 실제 실행 속도도 빠른 경우가 많다. 단, 구간 최솟값/최댓값 쿼리나 Lazy Propagation이 필요한 복잡한 연산에서는 세그먼트 트리를 써야 한다. 도구는 목적에 맞게 선택하는 것이 전문가의 방식이다.

희소 테이블 (Sparse Table)

배열이 절대 바뀌지 않는다면, 훨씬 강력한 도구를 쓸 수 있다. 희소 테이블은 전처리 시간 O(n log n)을 투자해서, 이후 어떤 구간 쿼리도 **O(1)**에 답하는 구조다. 비결은 2의 거듭제곱으로 구간을 미리 계산하는 것이다. sparse[j][i]에 인덱스 i부터 시작하는 길이 2^j인 구간의 최솟값을 저장한다. 임의의 구간 [l, r]에 대해 적절한 j = floor(log₂(r-l+1))를 선택하면, [l, l+2^j-1]과 [r-2^j+1, r] 두 구간의 최솟값 비교만으로 답을 얻는다. 이 두 구간이 겹쳐도 괜찮다 — 최솟값은 같은 원소를 두 번 봐도 결과가 바뀌지 않는 **멱등성(idempotent property)**이 있기 때문이다. 합 쿼리는 이 방법으로 O(1)에 하기 어렵다. 겹치는 부분이 두 번 더해지기 때문이다. 희소 테이블은 주로 RMQ (Range Minimum/Maximum Query) 에 사용된다.

[노트 기록]

import math

def build_sparse(arr):
    n = len(arr)
    LOG = int(math.log2(n)) + 1
    sparse = [[float('inf')] * n for _ in range(LOG)]
    sparse[0] = arr[:]
    for j in range(1, LOG):
        for i in range(n - (1 << j) + 1):
            sparse[j][i] = min(sparse[j-1][i], sparse[j-1][i + (1 << (j-1))])
    return sparse

def query_rmq(sparse, l, r):
    j = int(math.log2(r - l + 1))
    return min(sparse[j][l], sparse[j][r - (1 << j) + 1])

Part 2: 문자열 알고리즘 — 텍스트를 해부하는 기술

문자열 매칭의 본질적 어려움

우리가 Ctrl+F로 쓰는 찾기 기능은 어떻게 작동할까? 가장 단순한 구현인 Naive 알고리즘은 텍스트의 각 위치에서 패턴과 한 글자씩 비교한다. 텍스트 길이 n, 패턴 길이 m이면 최악의 경우 O(nm)이다. 텍스트가 "AAAA...A" (n개의 A)이고 패턴이 "AAA...AB" (m-1개의 A와 B 하나)라면, 매번 m-1개의 A를 비교하다가 마지막에 실패하는 것을 n번 반복한다. n = 10⁶, m = 100이면 10⁸번 비교 — 현대 컴퓨터에서도 수초가 걸린다. KMP 알고리즘은 이 비효율의 근본 원인을 파고든다. 비교에 실패했을 때, 우리는 지금까지 비교한 정보를 완전히 버리고 다시 시작한다는 것이 문제다. 이미 "AAA...A"를 읽었다는 사실을 활용할 수 있지 않을까?

KMP (Knuth-Morris-Pratt) 알고리즘

KMP의 핵심은 **실패 함수(Failure Function, 또는 Pi 배열)**다. 패턴 자체를 분석하여, 각 위치에서 매칭이 실패했을 때 얼마나 뒤로 돌아가야 하는지를 미리 계산한다. 패턴 P에 대해, pi[i]는 P[0..i]의 진부분문자열(proper prefix) 중 접두사이면서 동시에 접미사인 것의 최대 길이다. 예를 들어 P = "ABCABD"라면 pi = [0, 0, 0, 1, 2, 0]이다. pi[4] = 2인 이유는 "ABCAB"에서 "AB"가 접두사이면서 접미사이기 때문이다. 이것을 직접 손으로 계산해보라 — 어떤 규칙이 있는가를 스스로 발견해보라.

[노트 기록] KMP 구현:

def compute_pi(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j-1]   # 이미 알려진 정보로 되돌아감
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    pi = compute_pi(pattern)
    results = []
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            results.append(i - m + 1)   # 매칭 위치
            j = pi[j-1]
    return results

while j > 0 and ... 부분이 핵심이다. 매칭 실패 시 pi 배열을 따라 거슬러 올라가는 이 과정이 전체 알고리즘의 O(n+m) 시간을 보장한다. 왜냐하면 j는 증가할 때 최대 n번 증가하고, 감소할 때는 증가한 만큼만 감소할 수 있기 때문이다. 이것을 **상각 분석(Amortized Analysis)**이라 하는데, 1단계의 복잡도 분석과 정확히 같은 사고방식이다.

Aho-Corasick 알고리즘

KMP는 하나의 패턴을 하나의 텍스트에서 찾는다. 하지만 100개의 패턴을 동시에 찾아야 한다면? 각 패턴마다 KMP를 돌리면 O(100 × 텍스트 길이)다. Aho-Corasick은 모든 패턴을 한 번의 텍스트 스캔으로 동시에 찾는다. 비결은 Trie + KMP의 실패 링크의 결합이다.

먼저 모든 패턴을 **Trie(트라이)**에 삽입한다. Trie는 공통 접두사를 공유하는 트리 구조다. "he", "she", "his", "hers"를 Trie에 넣으면 'h'로 시작하는 패턴들이 같은 'h' 노드를 공유한다. 그 다음, KMP의 pi 배열에 해당하는 **실패 링크(Failure Link)**를 BFS로 Trie의 각 노드에 추가한다. 실패 링크는 현재 노드에서 매칭이 실패했을 때 이동해야 할 노드를 가리킨다. 텍스트를 스캔할 때, 이 오토마톤 위를 한 글자씩 이동하면 모든 패턴의 매칭이 O(텍스트 길이 + 모든 패턴 길이 합 + 매칭 횟수)에 완료된다. 대규모 로그 분석, 바이러스 패턴 스캔(안티바이러스 소프트웨어), 네트워크 침입 탐지 시스템 등에서 실제로 사용되는 알고리즘이다.

접미사 배열 (Suffix Array)

텍스트 "banana"의 모든 접미사를 나열해보자: "banana"(0), "anana"(1), "nana"(2), "ana"(3), "na"(4), "a"(5). 이것을 사전순으로 정렬하면: "a"(5), "ana"(3), "anana"(1), "banana"(0), "na"(4), "nana"(2). 정렬된 인덱스 배열 [5, 3, 1, 0, 4, 2]가 **접미사 배열(Suffix Array)**이다. 이 배열 하나로 어떤 패턴이 텍스트에 나타나는지 이진 탐색으로 O(m log n)에 찾을 수 있다. LCP(Longest Common Prefix) 배열 — 인접한 두 접미사의 공통 접두사 길이 — 을 함께 사용하면 "텍스트에서 가장 긴 반복 부분 문자열 찾기" 같은 문제를 O(n)에 풀 수 있다. 접미사 배열을 O(n log n)에 구축하는 더블링(Doubling) 알고리즘의 아이디어는, 길이 1인 접미사를 정렬하고 그 다음 길이 2, 4, 8... 식으로 두 배씩 늘려가며 정렬하는 것이다. 1단계의 분할 정복과 같은 철학이다.

[노트 기록] 세 알고리즘의 관계 정리:

  • KMP: 단일 패턴, 단일 텍스트 → O(n+m)
  • Aho-Corasick: 다중 패턴, 단일 텍스트 → O(n + Σm + 매칭 수)
  • 접미사 배열: 단일 텍스트에 대한 범용 색인, 이진 탐색으로 어떤 패턴도 O(m log n)

Part 3: 네트워크 플로우 — 그래프 위의 물리학

흐름(Flow)이란 무엇인가?

파이프 네트워크를 상상하자. 수원(source, S)에서 물이 나와 여러 파이프를 통해 수요처(sink, T)로 흘러간다. 각 파이프는 최대 용량(capacity)이 있다. S에서 T로 보낼 수 있는 최대 물의 양은 얼마인가? 이것이 최대 유량(Maximum Flow) 문제다. 방향 그래프 G = (V, E)에서 각 간선 (u, v)에 용량 c(u, v)가 주어질 때, 유량 함수 f(u, v)는 세 조건을 만족해야 한다: 용량 제약 f(u,v) ≤ c(u,v), 대칭성 f(u,v) = -f(v,u), 흐름 보존 (source/sink 제외한 모든 정점에서 들어오는 양 = 나가는 양). 이것과 최소 컷(Minimum Cut) — 그래프를 source 쪽과 sink 쪽으로 분리하는 간선 집합의 최소 용량 합 — 이 항상 같다는 것이 **최대 유량 최소 컷 정리(Max-Flow Min-Cut Theorem)**다. (Ford와 Fulkerson이 1956년 증명.)

Ford-Fulkerson과 Edmonds-Karp

Ford-Fulkerson 알고리즘의 개념은 단순하다. source에서 sink까지 유량을 보낼 수 있는 경로(증가 경로, Augmenting Path)를 찾아 유량을 흘려보내는 것을 반복한다. 유량을 보낼 때, 실제 간선뿐 아니라 역방향 간선도 사용할 수 있다 — 이미 흘린 유량을 "취소"하는 효과다. 이 역방향 간선의 존재가 핵심이다. 처음에는 왜 역방향이 필요한지 이해하기 어려울 수 있다 — "실수한 결정을 되돌릴 수 있는 능력"이라고 생각하라.

잔여 그래프(Residual Graph): 각 간선 (u, v)에 대해, 잔여 그래프에는 두 개의 간선이 있다. 정방향의 잔여 용량 c(u,v) - f(u,v)와 역방향 간선 (v, u)의 잔여 용량 f(u,v). 증가 경로는 이 잔여 그래프에서 찾는다. Ford-Fulkerson의 문제는 DFS로 경로를 찾을 때 최악의 경우 O(E × 최대유량)이 될 수 있다는 것이다. Edmonds-Karp 알고리즘은 여기에 한 가지만 바꾼다: DFS 대신 BFS로 최단 증가 경로를 찾는다. 이 단순한 변화가 복잡도를 O(V × E²)으로 보장해준다.

[노트 기록] Edmonds-Karp 핵심 구조:

from collections import deque

def bfs(graph, source, sink, parent):
    visited = set([source])
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in visited and graph[u][v] > 0:  # 잔여 용량 > 0
                visited.add(v)
                parent[v] = u
                if v == sink:
                    return True
                queue.append(v)
    return False

def edmonds_karp(graph, source, sink):
    max_flow = 0
    while True:
        parent = {}
        if not bfs(graph, source, sink, parent):
            break
        path_flow = float('inf')  # 경로의 병목 용량
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, graph[u][v])
            v = u
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow   # 정방향 감소
            graph[v][u] += path_flow   # 역방향 증가
            v = u
        max_flow += path_flow
    return max_flow

경쟁 프로그래밍과 현업에서는 주로 Dinic's 알고리즘을 쓴다. BFS로 **레벨 그래프(Level Graph)**를 만들고, 이 위에서 여러 증가 경로를 동시에 찾는 **블로킹 플로우(Blocking Flow)**를 구하는 방식이다. 복잡도는 O(V²E)이며, 이분 그래프에서는 O(E√V)라는 특수한 복잡도를 가진다.

이분 매칭 (Bipartite Matching) — 모든 것이 연결된다

이제 드디어 "작업자-기계 배치 문제"로 돌아오자. **이분 그래프(Bipartite Graph)**는 정점이 두 그룹 A와 B로 나뉘고 간선은 항상 A와 B 사이에만 존재하는 그래프다. 이분 매칭은 각 정점이 최대 하나의 간선과 연결되도록 하면서 매칭 수를 최대화하는 것이다. 이것이 최대 유량 문제와 어떻게 연결되는가? 슈퍼 소스 S를 만들어 A의 모든 정점과 용량 1로 연결하고, 슈퍼 싱크 T를 만들어 B의 모든 정점과 용량 1로 연결한다. A-B 간의 기존 간선들은 용량 1로 설정한다. 이 그래프에서의 최대 유량이 곧 최대 이분 매칭의 크기다. 플로우가 1인 간선은 매칭된 쌍을 의미한다. 세 파트의 지식이 완전히 하나로 합쳐지는 순간이다.

[노트 기록] 쾨니그 정리(König's Theorem): 이분 그래프에서 최대 매칭의 크기 = 최소 정점 덮개의 크기. 이것은 최대 유량 최소 컷 정리의 이분 그래프 버전이다. 실무에서 이분 매칭은 작업자-기계 배치, 학생-과목 배정, 택시-승객 매칭, 광고-사용자 타게팅에 쓰인다.

프로젝트: 스스로 구현해보자

세 가지 프로젝트를 제시한다. 정답은 없다. 직접 생각하고, 막히면 위 본문을 다시 읽어라. 각 프로젝트는 12~15분을 목표로 하지만 처음이라면 더 걸려도 괜찮다. 손으로 먼저 예제를 추적해본 다음 코드를 작성하는 것을 권한다.

프로젝트 1: 구간 쿼리 엔진 (목표 12분)

주식 거래 시스템의 일부를 구현한다. 주가 배열이 주어지고 두 종류의 쿼리가 들어온다.

문제: 배열 크기 n (1 ≤ n ≤ 10⁵)과 쿼리 수 q (1 ≤ q ≤ 10⁵)가 주어진다. 쿼리는 두 종류다. 1 i v: i번째 원소를 v로 변경하라. 2 l r: l번째부터 r번째까지의 최솟값을 출력하라.

예시 입력:

5 6
3 1 4 1 5
2 1 3
1 2 10
2 1 3
2 2 4
1 5 0
2 1 5

예시 출력:

1
3
1
0

도전 과제 (선택): 위를 구현한 후, 쿼리를 다음으로 바꿔보라. 3 l r v: l번째부터 r번째까지 모든 원소에 v를 더하라. 2 l r: l부터 r까지의 합을 출력하라. Lazy Propagation이 필요하다.

프로젝트 2: 실시간 로그 이상 탐지기 (목표 15분)

보안 시스템의 로그 분석 모듈을 구현한다. 미리 알려진 이상 패턴 목록이 있고, 실시간으로 들어오는 로그 스트림에서 이 패턴들을 감지해야 한다.

문제: 먼저 k개의 패턴 문자열이 주어진다 (총 합 길이 ≤ 10⁵). 그 다음 q개의 로그 라인이 주어진다 (각 로그 길이 ≤ 10⁵). 각 로그 라인에서 패턴들이 총 몇 번 출현하는지 (중복 포함) 출력하라.

예시 입력:

3
he
she
his
4
he thinks she is right
hishers
ahishers
hehethe

예시 출력:

2
3
3
3

핵심 질문: KMP를 k번 반복하는 것과 Aho-Corasick을 1번 쓰는 것, 어떤 것이 더 빠른가? Big-O로 두 방법을 비교해서 직접 답을 써보라.

프로젝트 3: 작업자-기계 최적 배치 시스템 (목표 13분)

공장 관리 시스템의 핵심 모듈을 구현한다.

문제: n명의 작업자와 m대의 기계가 있다. 각 작업자는 자신이 다룰 수 있는 기계 목록이 있다. 최대 몇 쌍의 (작업자, 기계) 배치가 가능한가? 한 작업자는 하나의 기계만, 한 기계는 하나의 작업자만 담당한다.

예시 입력:

4 4
작업자 1: 기계 1, 기계 2
작업자 2: 기계 2, 기계 3
작업자 3: 기계 3, 기계 4
작업자 4: 기계 1, 기계 4

예시 출력:

4

단계별 힌트 (막히면 순서대로 하나씩만 보라):

  1. 이 문제를 그래프로 어떻게 그릴 수 있는가?
  2. 슈퍼 소스와 슈퍼 싱크를 어디에 추가하면 되는가?
  3. 각 간선의 용량은 얼마로 설정해야 하는가?

변형 문제 (선택): 최대 매칭을 유지하면서, 특정 (작업자, 기계) 조합에 부여된 선호도 점수의 총합도 최대화하라. (힌트: 최소 비용 최대 유량, Min-Cost Max-Flow)

마무리: 세 세계의 연결

여기까지 왔다면, 완전히 다른 세 문제 도메인 — 구간, 문자열, 그래프 — 을 하나의 공통 철학으로 이해하게 되었을 것이다. 그 철학은 **"분할하여 정복하고, 이미 계산한 것을 재활용하라"**는 것이다. 세그먼트 트리는 배열을 분할하여 반복 계산을 피한다. KMP와 Aho-Corasick은 이미 매칭한 정보를 pi 배열과 실패 링크로 재활용한다. Ford-Fulkerson은 잔여 그래프를 통해 이전 유량 결정을 수정한다. 이것이 1단계의 DP "겹치는 부분 문제"와 정확히 같은 철학이라는 것을 느꼈는가? 알고리즘의 세계에는 같은 철학이 다른 외투를 입고 반복해서 나타난다. 프로젝트를 구현하면서 막히는 지점이 생기는 것은 당연하다. 그 막히는 순간이 바로 네가 진짜 배우는 순간이다. 에러 메시지를 읽고, 예제를 손으로 추적하고, 본문을 다시 읽어라.

← 단계 1단계 3 →