0.1 알고리즘이란 무엇인가?

알고리즘은 어떤 목적을 이루기 위해 기본 명령들을 명확하고 모호하지 않게 나열한 절차다. “기계적으로 실행 가능하다”는 말이 중요하다. 사람이 적당히 눈치껏 해석해야 하는 지시는 알고리즘이 아니다. 예를 들어 n Bottles of Beer 노래를 부르는 절차는 반복 횟수와 각 절의 동작이 분명하므로 알고리즘으로 볼 수 있다.

BottlesOfBeer(n):
  for i ← n downto 1
    sing "{i} bottles of beer on the wall"
    sing "take one down; {i-1} bottles remain"
  sing "no bottles remain"
  sing "go to the store; buy {n} more"

“algorithm”이라는 말은 페르시아 학자 무함마드 이븐 무사 알콰리즈미의 이름이 유럽 언어를 거치며 변한 데서 왔다. 본래는 십진 위치 표기와 산술 절차를 가리키는 말에 가까웠고, 이런 절차를 능숙하게 수행하는 사람을 “computer”라고 부르기도 했다. 오늘날에는 산술을 넘어 모든 계산 절차를 뜻하지만, 출발점은 여전히 “정확히 따라 할 수 있는 방법”이다.

0.2 곱셈

알고리즘은 컴퓨터보다 훨씬 오래되었다. 큰 수의 곱셈은 그 대표적인 예다. 격자 곱셈은 두 수를 자릿수 배열로 보고, 모든 한 자리 곱을 적절한 자리값에 더한다. 입력 배열 X[0..m-1], Y[0..n-1]가 각각 x, y를 나타내면 곱은 다음 합으로 표현된다.

FibonacciMultiply(X[0..m-1], Y[0..n-1]):
  carry ← 0
  for k ← 0 to m+n-1
    for every i,j with i+j = k
      carry ← carry + X[i] * Y[j]
    Z[k] ← carry mod 10
    carry ← floor(carry / 10)
  return Z

이 알고리즘은 어떤 순서로 부분곱을 더하느냐만 다를 뿐, 핵심 비용은 한 자리 곱 mn개다. 따라서 m자리 수와 n자리 수를 곱하는 데 O(mn) 시간이 든다. 초등학교의 세로셈, 피보나치가 소개한 격자 방식, 여러 고대 산술서의 방식은 모두 같은 원리를 다른 표기와 순서로 실행한다.

더 오래된 “두 배와 반으로 나누기” 방식은 곱셈을 홀짝 판정, 덧셈, 두 배, 절반으로 나누기로 환원한다. 핵심 항등식은 다음과 같다.

PeasantMultiply(x, y):
  prod ← 0
  while x > 0
    if x is odd
      prod ← prod + y
    x ← floor(x / 2)
    y ← y + y
  return prod

이 절차는 겉으로는 반복문이지만 본질적으로 재귀적 항등식에 기대고 있다. x를 계속 절반으로 줄이므로 O(log x)번의 단계가 필요하고, 자릿수 표기에서 각 단계의 산술 비용을 고려하면 전체 시간은 대략 O(log x log y), 즉 입력 자릿수 곱에 비례한다. 고대 그리스의 컴퍼스와 직선자 구성도 비슷한 관점에서 볼 수 있다. 수를 선분 길이로 표현하고, 허용된 기하 조작만으로 곱셈과 나눗셈을 구현하는 알고리즘인 셈이다.

0.3 의회 의석 배분

알고리즘은 산술뿐 아니라 사회적 절차에도 등장한다. 미국 하원의 의석을 주별 인구에 비례해 배분하려면, 이상적인 비율은 대개 분수이지만 실제 의석은 정수여야 한다. 현재 쓰이는 헌팅턴-힐 방법은 각 주에 먼저 한 석을 배정한 뒤, 남은 의석을 우선순위가 가장 큰 주에 하나씩 준다.

ApportionCongress(Pop[1..n], R):
  PQ ← empty max-priority queue
  for s ← 1 to n
    Rep[s] ← 1
    insert PQ with key Pop[s] / sqrt(2)
  for k ← 1 to R-n
    s ← extractMax(PQ)
    Rep[s] ← Rep[s] + 1
    key ← Pop[s] / sqrt(Rep[s] * (Rep[s] + 1))
    insert PQ with key key
  return Rep

이 알고리즘의 정당성은 우선순위 규칙 자체에 있고, 우선순위 큐가 내부적으로 배열인지 힙인지는 중요하지 않다. 다만 실행 시간은 구현에 달라진다. 단순 배열을 쓰면 매번 최댓값을 찾는 데 O(n) 시간이 들고, 이진 힙을 쓰면 삽입과 삭제가 O(log n)이 되어 전체 배분을 더 빠르게 수행할 수 있다.

0.4 나쁜 예

모든 절차가 알고리즘은 아니다. “백만 달러를 얻고, 세무서 직원이 오면 잊었다고 말하라”는 농담 같은 절차는 첫 단계가 너무 모호하다. 대부분의 사람에게 “백만 달러를 얻어라”는 기계적으로 실행 가능한 기본 명령이 아니다.

하지만 이 예시는 중요한 생각을 보여 준다. 어려운 문제를 다른 문제로 바꾸어 놓는다는 의미에서 이것은 환원이다. 백만장자가 되어 세금을 내지 않는 문제를 백만 달러를 얻는 문제로 바꾸었기 때문이다. 알고리즘 설계에서는 이런 환원이 반복해서 등장한다. 단, 환원된 문제가 실제로 더 쉽고 명확해야 알고리즘이 된다.

0.5 알고리즘을 설명하는 법

좋은 알고리즘 설명에는 네 가지가 필요하다. 무엇을 푸는지, 어떻게 푸는지, 왜 맞는지, 얼마나 빠른지다. 이 네 요소는 설계 과정에서 서로 영향을 주지만, 독자에게 전달할 때는 구분해서 쓰는 편이 분명하다.

• 문제 명세: 입력과 출력의 타입, 의미, 숨은 가정을 명확히 쓴다.
• 알고리즘 설명: 구현 언어의 문법보다 구조를 드러내는 의사코드를 쓴다.
• 정당성 증명: 모든 가능한 입력에서 결과가 올바름을 보인다.
• 시간 분석: 기본 연산 수나 자료구조 연산 수를 기준으로 최악의 경우를 분석한다.

알고리즘은 프로그램과 다르다. 프로그램은 특정 언어로 쓴 구현이고, 알고리즘은 그보다 추상적인 절차다. 반대로 자연어 설명만으로는 반복, 조건, 재귀의 경계가 흐려지기 쉽다. 따라서 의사코드와 구조화된 설명을 함께 쓰는 것이 좋다. 특히 “이런 식으로 계속한다” 같은 표현은 피해야 한다. 반복이면 반복 범위를 쓰고, 재귀면 기저 사례와 재귀 호출을 명확히 써야 한다.

0.6 알고리즘 분석

알고리즘을 제시한 뒤에는 항상 올바름과 효율을 따져야 한다. 이 책에서 “맞다”는 말은 보통 입력에서 대충 잘 된다는 뜻이 아니라, 가능한 모든 입력에서 항상 맞는다는 뜻이다. 따라서 테스트 몇 개보다 증명이 중요하고, 그 증명에는 귀납법이 자주 쓰인다.

시간은 실제 초 단위보다 입력 크기에 따른 성장률로 측정한다. BottlesOfBeer(n)은 절을 n번 부르므로 Theta(n) 시간이다. 반면 누적 노래인 NDaysOfChristmas는 1+2+...+n = n(n+1)/2개의 선물 이름을 부르므로 Theta(n^2) 시간이 든다.

NDaysOfChristmas(gifts[2..n]):
  for i ← 1 to n
    sing "On the i-th day..."
    for j ← i downto 2
      sing gifts[j]
    sing "a partridge in a pear tree"

재귀 알고리즘의 시간은 보통 점화식으로 표현된다. 예를 들어 농부 곱셈은 T(x,y) ≤ T(floor(x/2),2y)+2를 만족하므로 기본 단계 수가 O(log x)다. 자료구조를 하위 루틴으로 쓰는 알고리즘은 그 자료구조의 연산 시간에 따라 전체 시간이 달라진다. 헌팅턴-힐 알고리즘도 우선순위 큐를 어떻게 구현하느냐에 따라 O(Rn)이 될 수도, O(R log n)이 될 수도 있다.

1.1 환원

환원이란 문제 X를 풀기 위해 문제 Y를 푸는 알고리즘을 검은 상자처럼 사용하는 것이다. 이때 X 알고리즘의 정당성은 Y가 내부적으로 어떻게 구현되었는지에 의존해서는 안 된다. 오직 “Y를 정확히 푼다”는 명세만 믿는다.

농부 곱셈은 곱셈을 덧셈, 절반으로 나누기, 홀짝 판정으로 환원한다. 의석 배분 알고리즘은 배분 문제를 Insert와 ExtractMax를 지원하는 우선순위 큐 문제로 환원한다. 이 분리는 알고리즘 설계의 큰 장점이다. 더 좋은 숫자 표현이나 더 좋은 우선순위 큐를 넣으면, 상위 알고리즘의 논리를 바꾸지 않고도 실행 시간을 개선할 수 있다.

1.2 단순화하고 맡기기

재귀는 자기 자신을 하위 루틴으로 쓰는 환원이다. 주어진 입력을 직접 풀 수 있으면 풀고, 아니면 같은 문제의 더 단순한 입력들로 바꾼 뒤 그 결과를 이용한다. 올바른 재귀에는 무한히 계속 내려가는 호출 사슬이 없어야 한다. 보통 입력 크기가 엄격히 줄어들도록 설계하고, 더 줄일 수 없는 경우를 기저 사례로 둔다.

PeasantMultiply(x, y):
  if x = 0
    return 0
  x2 ← floor(x / 2)
  y2 ← y + y
  prod ← PeasantMultiply(x2, y2)
  if x is odd
    prod ← prod + y
  return prod

이 의사코드에서 현재 호출은 x가 홀수인지에 따른 마지막 조정만 책임진다. floor(x/2) * (y+y)의 계산은 더 작은 재귀 호출이 맡는다. 정당성 증명에서는 이 믿음을 “귀납 가정”이라고 부른다.

1.3 하노이 탑

하노이 탑은 n개의 원반을 한 기둥에서 다른 기둥으로 옮기되, 한 번에 하나만 옮기고 큰 원반을 작은 원반 위에 놓지 않는 퍼즐이다. 핵심은 가장 큰 원반 하나에 집중하는 것이다. 위의 n-1개를 보조 기둥으로 옮기고, 가장 큰 원반을 목적지로 옮긴 뒤, 다시 n-1개를 목적지로 옮긴다.

Hanoi(n, src, dst, tmp):
  if n > 0
    Hanoi(n-1, src, tmp, dst)
    move disk n from src to dst
    Hanoi(n-1, tmp, dst, src)

기저 사례 n=0에서는 아무 일도 하지 않는다. 귀납적으로, n-1개의 원반을 옮기는 두 재귀 호출이 올바르게 수행된다고 가정하면 전체 절차도 올바르다. 이동 횟수 T(n)은 T(0)=0, T(n)=2T(n-1)+1을 만족하므로 T(n)=2^n-1이다.

1.4 병합정렬

병합정렬은 분할 정복의 전형적인 예다. 배열을 거의 반으로 나누고, 두 절반을 재귀적으로 정렬한 뒤, 이미 정렬된 두 배열을 하나로 병합한다. 분할은 쉽고, 재귀 호출은 귀납 가정에 맡기며, 실제 작업은 병합 단계에 모인다.

MergeSort(A[1..n]):
  if n > 1
    m ← floor(n / 2)
    MergeSort(A[1..m])
    MergeSort(A[m+1..n])
    Merge(A[1..n], m)

Merge(A[1..n], m):
  i ← 1
  j ← m+1
  for k ← 1 to n
    choose the smaller front element from A[i..m] and A[j..n]
    write it into B[k]
  copy B back into A

병합의 정당성은 반복 불변식으로 보인다. 매 단계에서 남은 두 부분 배열의 가장 작은 원소가 출력의 다음 원소가 된다. 전체 병합정렬의 정당성은 배열 길이에 대한 귀납법으로 따른다. 실행 시간은 T(n)=T(ceil(n/2))+T(floor(n/2))+O(n), 바닥과 천장을 무시하면 2T(n/2)+O(n)이므로 O(n log n)이다.

1.5 퀵정렬

퀵정렬은 병합정렬과 반대로, 재귀 전에 일을 많이 한다. 피벗을 하나 고르고, 피벗보다 작은 원소와 큰 원소를 나누어 놓은 뒤, 양쪽 부분 배열만 재귀적으로 정렬한다. 병합 단계는 사실상 필요 없다.

QuickSort(A[1..n]):
  if n > 1
    choose pivot index p
    r ← Partition(A, p)
    QuickSort(A[1..r-1])
    QuickSort(A[r+1..n])

Partition(A[1..n], p):
  swap A[p] and A[n]
  less ← 0
  for i ← 1 to n-1
    if A[i] < A[n]
      less ← less + 1
      swap A[less] and A[i]
  swap A[less+1] and A[n]
  return less + 1

Partition의 불변식은 반복이 끝날 때 A[1..less]는 피벗보다 작고, A[less+1..i]는 피벗보다 작지 않다는 것이다. 피벗의 최종 순위가 r이면 시간 점화식은 T(n)=T(r-1)+T(n-r)+O(n)이다. 피벗이 항상 중앙 근처면 O(n log n)이지만, 한쪽으로 치우치면 T(n)=T(n-1)+O(n)이 되어 O(n^2)이 된다.

1.6 패턴

병합정렬과 퀵정렬은 모두 분할 정복이다. 첫째, 원래 문제를 같은 종류의 더 작은 독립 문제들로 나눈다. 둘째, 각 작은 문제를 재귀적으로 푼다. 셋째, 작은 문제들의 답을 합쳐 원래 문제의 답을 만든다. 입력 크기가 충분히 작아지면 직접 푼다.

정당성은 보통 귀납법으로, 시간 분석은 보통 점화식으로 처리한다. 여기서 중요한 태도는 “재귀를 펼쳐서 모든 호출을 따라가겠다”가 아니라, 현재 호출이 어떤 더 작은 문제를 만들고 그 답을 어떻게 결합하는지에 집중하는 것이다.

1.7 재귀 트리

재귀 트리는 분할 정복 점화식을 시각적으로 푸는 도구다. 점화식 T(n)=rT(n/c)+f(n)에서 각 노드는 한 재귀 부분문제를 나타내고, 그 노드의 값은 재귀 호출을 제외하고 그 부분문제에서 쓰는 시간 f(size)다. 전체 시간은 트리의 모든 노드 값을 더한 것이다.

자주 만나는 세 경우가 있다. 각 레벨의 합이 지수적으로 줄면 루트가 지배하여 O(f(n))이다. 모든 레벨이 비슷하면 레벨 수를 곱해 O(f(n) log n)이다. 각 레벨의 합이 지수적으로 커지면 잎의 수가 지배하여 O(n^{log_c r})이다. 병합정렬은 모든 레벨의 합이 O(n)이라 O(n log n)이다.

크기가 다른 하위 문제에도 재귀 트리를 쓸 수 있다. 예를 들어 좋은 피벗을 쓰는 퀵정렬의 T(n)≤T(n/3)+T(2n/3)+O(n)은 각 레벨의 총합이 여전히 O(n)이고 깊이가 O(log n)이므로 O(n log n)이다. 반대로 최악 피벗에서는 한쪽 가지가 길게 늘어져 O(n^2)가 된다.

1.8 선형 시간 선택

선택 문제는 정렬하지 않은 배열에서 k번째로 작은 원소를 찾는 문제다. 퀵셀렉트는 피벗으로 배열을 분할한 뒤, k번째 원소가 들어 있는 한쪽만 재귀적으로 탐색한다. 정당성은 피벗 순위와 분할의 성질에 의해 피벗 왼쪽과 오른쪽의 후보가 분명해진다는 사실에서 나온다.

QuickSelect(A[1..n], k):
  if n = 1
    return A[1]
  choose pivot
  r ← Partition(A, pivot)
  if k < r
    return QuickSelect(A[1..r-1], k)
  if k > r
    return QuickSelect(A[r+1..n], k-r)
  return A[r]

피벗이 나쁘면 T(n)=T(n-1)+O(n)이 되어 O(n^2)이다. Blum-Floyd-Pratt-Rivest-Tarjan의 중앙값의 중앙값 알고리즘은 배열을 5개씩 묶고 각 묶음의 중앙값을 모은 뒤, 그 중앙값들의 중앙값을 재귀적으로 찾아 피벗으로 쓴다. 이 피벗은 적어도 약 3n/10개의 원소보다 크고, 또 적어도 3n/10개의 원소보다 작다.

MomSelect(A[1..n], k):
  if n is small
    solve by brute force
  split A into groups of five
  M ← medians of all groups
  mom ← MomSelect(M, floor(|M|/2))
  r ← Partition(A, mom)
  recurse only into the side containing rank k

시간 점화식은 T(n) ≤ T(n/5) + T(7n/10) + O(n)이다. 두 재귀 문제의 크기 합이 0.9n 이하이므로 재귀 트리의 레벨 합이 지수적으로 줄고, 전체 시간은 O(n)이다. 5개 묶음이 중요한 이유도 여기에 있다. 3개 묶음은 T(n)≤T(n/3)+T(2n/3)+O(n) 꼴이 되어 O(n log n)에 머문다.

1.9 빠른 곱셈

두 n자리 수를 반으로 나누어 x=10^m a+b, y=10^m c+d라 하면 곱은 다음처럼 전개된다.

이 식을 그대로 쓰면 ac, bc, ad, bd 네 번의 재귀 곱셈이 필요하고, 점화식 T(n)=4T(n/2)+O(n)은 여전히 O(n^2)이다. 카라추바의 관찰은 가운데 항을 세 번째 곱셈 하나로 얻을 수 있다는 것이다.

FastMultiply(x, y, n):
  if n = 1
    return x * y
  m ← ceil(n / 2)
  split x into a,b and y into c,d
  e ← FastMultiply(a, c, m)
  f ← FastMultiply(b, d, m)
  g ← FastMultiply(a-b, c-d, m)
  return 10^(2m)e + 10^m(e+f-g) + f

이제 점화식은 T(n)≤3T(n/2)+O(n)이고, 재귀 트리로부터 O(n^{log_2 3}), 약 O(n^1.585)가 된다. 이 아이디어는 더 빠른 Toom-Cook 곱셈과 FFT 기반 곱셈으로 이어지는 출발점이다.

1.10 거듭제곱

a^n을 단순히 a를 n-1번 곱해 계산하면 선형 개수의 곱셈이 든다. 하지만 지수의 절반을 먼저 계산하면 훨씬 빠르다.

PingalaPower(a, n):
  if n = 0
    return 1
  x ← PingalaPower(a, floor(n / 2))
  if n is even
    return x * x
  return x * x * a

점화식은 T(n)≤T(n/2)+2이므로 곱셈 수는 O(log n)이다. 어떤 값이든 “곱셈”이 정의되어 있으면 적용할 수 있어, 정수뿐 아니라 모듈러 거듭제곱이나 행렬 거듭제곱에도 쓰인다. 또한 어떤 알고리즘도 매 곱셈에서 만들 수 있는 최대 지수를 많아야 두 배로 늘릴 수 있으므로, 일반적으로 Omega(log n)번의 곱셈은 필요하다.

2.1 N 퀸

n 퀸 문제는 n x n 체스판에 서로 공격하지 않도록 n개의 퀸을 놓는 문제다. 퀸은 같은 행, 같은 열, 같은 대각선에 있으면 공격한다. 한 행에 퀸 하나씩 놓는다고 보면, 해는 배열 Q[1..n]으로 표현할 수 있고 Q[r]는 r번째 행의 열 번호다.

PlaceQueens(Q[1..n], r):
  if r = n + 1
    print Q
  else
    for col ← 1 to n
      legal ← true
      for i ← 1 to r-1
        if Q[i] = col or Q[i] = col+r-i or Q[i] = col-r+i
          legal ← false
      if legal
        Q[r] ← col
        PlaceQueens(Q, r+1)

각 재귀 호출은 이미 놓은 퀸들과 충돌하지 않는 다음 행의 위치를 고른다. 호출 트리의 노드는 합법적인 부분 배치이고, 간선은 퀸 하나를 더 놓는 선택이다. 완성된 해는 깊이 n의 잎으로 나타나며, 막힌 부분 배치는 더 확장되지 않는 잎이 된다. 따라서 알고리즘 실행은 이 재귀 트리를 깊이 우선 탐색하는 것과 같다.

2.2 게임 트리

숨은 정보와 우연성이 없고 반드시 끝나는 2인 게임은 게임 상태들을 트리로 펼쳐 분석할 수 있다. 각 노드는 현재 말의 배치와 차례를 포함하는 상태이고, 간선은 합법적인 한 수다. 루트에서 잎까지의 경로 하나가 완전한 한 판이다.

상태를 좋은 상태와 나쁜 상태로 재귀적으로 정의한다. 현재 플레이어가 이미 이겼거나 상대에게 나쁜 상태를 넘길 수 있으면 좋은 상태다. 이미 졌거나 모든 가능한 수가 상대에게 좋은 상태를 준다면 나쁜 상태다. 이 정의로부터 완벽한 플레이가 가능하다.

PlayAnyGame(X, player):
  if player already won at X
    return Good
  if player already lost at X
    return Bad
  for every legal move X -> Y
    if PlayAnyGame(Y, other(player)) = Bad
      return Good
  return Bad

실제 체스나 바둑처럼 상태 수가 거대한 게임에서는 전체 트리를 탐색할 수 없다. 그래도 많은 게임 프로그램의 뼈대는 이 재귀 정의다. 평가 함수, 깊이 제한, 가지치기는 이 기본 백트래킹을 현실적인 크기로 줄이는 장치다.

2.3 부분합

부분합 문제는 양의 정수 집합 X와 목표값 T가 주어졌을 때, 합이 T인 부분집합이 있는지 묻는다. 원소 하나 x를 고르면 해는 두 경우 중 하나다. x를 포함하거나, 포함하지 않는다. 포함하면 남은 목표는 T-x가 되고, 포함하지 않으면 그대로 T다.

SubsetSum(X, i, T):
  // Is there a subset of X[1..i] with sum T?
  if T = 0
    return true
  if T < 0 or i = 0
    return false
  with ← SubsetSum(X, i-1, T-X[i])
  without ← SubsetSum(X, i-1, T)
  return with or without

정당성은 원소 X[i]가 해에 들어가는지 여부에 대한 경우 나누기로 증명한다. 실행 시간은 T(n)≤2T(n-1)+O(1)이므로 O(2^n)이다. 목표값이 모든 원소의 합보다 큰 경우처럼 가지치기가 거의 일어나지 않으면 알고리즘은 모든 부분집합을 사실상 검사한다.

같은 재귀 구조로 실제 부분집합을 반환하거나, 가능한 부분집합의 수를 세거나, 조건을 만족하는 부분집합 중 다른 점수를 최대화하는 변형도 풀 수 있다. 백트래킹에서는 처음부터 복잡한 구조를 반환하기보다, 가장 단순한 판정 문제를 먼저 정확히 세우는 편이 좋다.

2.4 일반 패턴

백트래킹은 보통 일련의 결정을 내려 제약을 만족하는 구조를 만든다. n-퀸에서는 각 행의 열을 고르고, 게임에서는 다음 수를 고르며, 부분합에서는 각 원소를 넣을지 말지 고른다. 각 호출은 이전 결정과 모순되지 않는 다음 선택을 하나 만든다.

중요한 설계 질문은 “과거 결정 중 무엇을 기억해야 하는가?”다. n-퀸은 이전 퀸 위치를 거의 모두 알아야 한다. 게임 트리는 현재 상태만 알면 과거 경로는 필요 없다. 부분합은 이미 고른 원소들의 목록이 아니라 남은 목표값만 기억하면 된다. 이 요약이 작을수록 알고리즘을 분석하고 나중에 동적 계획법으로 바꾸기 쉽다.

새 백트래킹 알고리즘을 만들 때는 먼저 실제로 재귀적으로 풀 문제를 일반화한다. 그다음 가능한 다음 선택을 모두 시도한다. 처음부터 “명백히 나쁜 선택”을 감으로 건너뛰려 하지 말고, 올바른 완전 탐색을 먼저 만든 뒤 필요하면 최적화한다.

2.5 문자열 분할

공백 없는 문자열을 단어들의 열로 나눌 수 있는지 묻는 문제를 생각하자. 예를 들어 라틴어의 고대 필사본, 현대의 여러 문자 체계, URL과 해시태그에서 비슷한 문제가 나타난다. IsWord(w)라는 판정 함수가 있다고 하면, 다음 단어가 어디에서 끝나는지만 결정하면 된다.

Splittable(A[1..n]):
  if n = 0
    return true
  for i ← 1 to n
    if IsWord(A[1..i]) and Splittable(A[i+1..n])
      return true
  return false

실제 구현에서는 부분 배열을 계속 복사하지 않고 원본 문자열을 전역으로 두고 인덱스만 넘긴다. Splittable(i)를 “접미사 A[i..n]을 단어로 나눌 수 있는가”로 정의하면 다음 점화식을 얻는다.

이 백트래킹 알고리즘은 최악의 경우 문자열을 자를 수 있는 모든 위치 조합을 탐색한다. 길이 n 문자열에는 대략 2^{n-1}가지 분할이 있으므로, IsWord 호출 수 역시 지수적으로 커질 수 있다.

2.6 최장 증가 부분수열

부분수열은 원래 순서를 유지하면서 일부 원소를 지운 결과다. 최장 증가 부분수열(LIS)은 주어진 수열에서 값이 엄격히 증가하는 가장 긴 부분수열을 찾는 문제다. 첫 번째 백트래킹 전략은 왼쪽에서 오른쪽으로 보며 현재 원소를 포함할지 말지 결정한다.

과거 결정에서 필요한 정보는 지금까지 고른 마지막 값뿐이다. 인덱스 버전으로, LISbigger(i,j)를 “A[j..n]에서 모든 원소가 A[i]보다 큰 증가 부분수열의 최대 길이”라고 하자. 센티널 A[0] = -infinity를 두면 원래 답은 LISbigger(0,1)이다.

LISbigger(i, j):
  if j > n
    return 0
  if A[i] ≥ A[j]
    return LISbigger(i, j+1)
  skip ← LISbigger(i, j+1)
  take ← 1 + LISbigger(j, j+1)
  return max(skip, take)

이 알고리즘은 각 원소에 대해 “선택/비선택”을 나누므로 최악의 경우 O(2^n) 시간이 든다. 하지만 상태가 두 인덱스로 표현된다는 사실은 다음 장에서 동적 계획법으로 개선하는 단서가 된다.

2.7 최장 증가 부분수열, 두 번째

LIS를 보는 다른 방법은 “현재 원소를 쓸까?”가 아니라 “출력 부분수열의 다음 원소는 어디인가?”를 묻는 것이다. LISfirst(i)를 “A[i]로 시작하는, A[i..n]의 최장 증가 부분수열 길이”라고 정의한다.

LISfirst(i):
  best ← 0
  for j ← i+1 to n
    if A[j] > A[i]
      best ← max(best, LISfirst(j))
  return 1 + best

원래 문제는 첫 원소를 모르므로 모든 시작점을 시도하거나, A[0] = -infinity 센티널을 앞에 붙여 LISfirst(0)-1을 계산한다. 이 재귀도 아직은 지수 시간이지만, 상태가 하나의 인덱스로만 표현되므로 동적 계획법으로 더 간단히 바뀐다.

2.8 최적 이진 탐색 트리

정렬된 키 A[1..n]와 각 키의 검색 빈도 f[1..n]가 주어졌다고 하자. 목표는 전체 검색 비용, 즉 각 키의 빈도에 그 노드의 조상 수를 곱해 더한 값을 최소화하는 이진 탐색 트리를 만드는 것이다. 자주 찾는 키는 루트 가까이에 둘수록 좋다.

루트가 A[r]라면 왼쪽 서브트리는 A[i..r-1]만, 오른쪽 서브트리는 A[r+1..k]만 담아야 한다. 루트는 모든 검색에서 한 번 방문되므로, 구간 i..k의 총 빈도 sum_{j=i}^{k} f[j]가 더해진다. 따라서 OptCost(i,k)는 다음 점화식을 따른다.

이 백트래킹은 가능한 루트를 모두 시도하고, 각 루트에 대해 왼쪽과 오른쪽 최적 트리를 재귀적으로 맡긴다. 순진한 재귀 구현은 지수 시간이지만, 하위 문제가 구간 (i,k)로 반복된다는 점 때문에 다음 장에서 다항 시간 동적 계획법으로 바뀐다.

3.1 마트라브리타

고대 인도의 운율 연구에서는 한 박자의 짧은 음절과 두 박자의 긴 음절로 총 n박자를 만드는 방법을 세었다. 마지막 음절이 짧으면 앞부분은 n-1박자이고, 길면 앞부분은 n-2박자다. 따라서 경우의 수 M(n)은 피보나치식 점화식을 따른다.

보통의 피보나치 수는 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)로 정의된다. 이를 그대로 재귀로 구현하면 같은 값을 지나치게 많이 다시 계산한다.

RecFibo(n):
  if n = 0 return 0
  if n = 1 return 1
  return RecFibo(n-1) + RecFibo(n-2)

호출 수 T(n)은 T(n)=T(n-1)+T(n-2)+1이고, 결국 피보나치 수에 비례해 지수적으로 커진다. 이를 고치려면 이미 계산한 값을 배열에 적어 둔다. 이 기법을 메모이제이션이라고 한다.

MemFibo(n):
  if n = 0 return 0
  if n = 1 return 1
  if F[n] is undefined
    F[n] ← MemFibo(n-1) + MemFibo(n-2)
  return F[n]

메모이제이션은 각 F[i]를 한 번만 계산하게 만든다. 더 나아가 값들이 작은 인덱스부터 채워진다는 사실을 알면 재귀를 반복문으로 바꿀 수 있다. 이것이 첫 번째 동적 계획법 알고리즘이다.

IterFibo(n):
  F[0] ← 0
  F[1] ← 1
  for i ← 2 to n
    F[i] ← F[i-1] + F[i-2]
  return F[n]

3.2 더 빠른 피보나치 수

피보나치 수는 행렬 거듭제곱으로도 계산할 수 있다. 행렬 [[0,1],[1,1]]을 벡터에 곱하면 피보나치 반복문 한 단계를 수행한 것과 같다.

거듭제곱을 반복 제곱으로 계산하면 O(log n)번의 2x2 행렬 곱셈만 필요하다. 같은 생각은 다음 인접한 두 피보나치 수의 재귀식으로도 쓸 수 있다.

FastRecFibo(n):
  // return (F[n-1], F[n])
  if n = 1
    return (0, 1)
  m ← floor(n / 2)
  (a, b) ← FastRecFibo(m)
  prev ← a*a + b*b
  curr ← b * (2*a + b)
  next ← prev + curr
  if n is even
    return (prev, curr)
  return (curr, next)

산술 연산의 개수만 세면 O(log n)이지만, F_n 자체가 Theta(n)비트 길이를 가지므로 실제 시간은 임의 정밀도 덧셈과 곱셈 비용을 포함해야 한다. 빠른 곱셈 시간을 M(n)이라 하면 이 방법은 대략 O(M(n)) 시간에 동작하고, 단순 반복 피보나치는 큰 수 덧셈 때문에 실제로 O(n^2) 시간이 든다.

3.3 문자열 분할 다시 보기

백트래킹 장에서 본 문자열 분할 문제의 재귀식은 Splittable(i), 즉 접미사 A[i..n]가 단어들로 나뉠 수 있는지를 묻는 함수였다. 순진한 재귀는 같은 접미사를 여러 경로에서 반복해서 계산한다.

가능한 i는 1부터 n+1까지뿐이다. 따라서 SplitTable[i]에 값을 저장하고, Splittable(i)가 더 큰 인덱스의 값에만 의존한다는 점을 이용해 오른쪽에서 왼쪽으로 채우면 된다.

FastSplittable(A[1..n]):
  SplitTable[n+1] ← true
  for i ← n downto 1
    SplitTable[i] ← false
    for j ← i to n
      if IsWord(i,j) and SplitTable[j+1]
        SplitTable[i] ← true
  return SplitTable[1]

이 알고리즘은 IsWord(i,j)를 가능한 구간쌍에 대해 확인하므로 O(n^2)번 호출한다. 지수 시간 백트래킹이 다항 시간으로 줄어드는 전형적인 예다.

3.4 패턴: 똑똑한 재귀

동적 계획법은 “반복 없는 재귀”다. 표를 채우는 일이 눈에 잘 보이지만, 진짜 어려운 부분은 올바른 재귀 문제를 정의하는 것이다. 잘못된 점화식을 아무리 예쁘게 표로 채워도 답은 틀린다.

1. 재귀적으로 문제를 공식화한다. 하위 문제가 무엇을 의미하는지 한국어로 명확히 쓰고, 그 답들로 현재 답을 계산하는 점화식이나 재귀 알고리즘을 만든다.
2. 하위 문제를 저장한다. 가능한 하위 문제를 식별하고, 배열이나 트리 같은 저장 구조를 고른다.
3. 의존성을 확인한다. 한 항목을 계산할 때 어떤 항목들이 먼저 필요한지 그린다.
4. 평가 순서를 정한다. 모든 의존 대상이 먼저 계산되는 순서를 찾는다.
5. 시간과 공간을 분석한다. 하위 문제 수가 공간의 출발점이고, 각 하위 문제 계산 비용의 합이 시간이다.
6. 알고리즘을 쓴다. 재귀 호출을 저장된 값 조회로 바꾸고, 적절한 반복문으로 표를 채운다.

3.5 경고: 탐욕은 어리석다

탐욕 알고리즘은 매 단계에서 현재 가장 좋아 보이는 선택을 바로 확정한다. 백트래킹이나 동적 계획법처럼 하위 문제를 두루 살펴보지 않는다. 이 방식은 매력적이지만, 최적화 문제에서 올바르게 작동하는 경우는 드물다.

문자열 분할에서 가장 짧은 단어 또는 가장 긴 단어를 먼저 고르는 전략, LIS에서 가장 작은 원소를 먼저 고르는 전략은 모두 그럴듯해 보이지만 일반적으로 틀린다. 탐욕적 직관이 떠오를 때는 대개 “어떤 하위 문제를 정의해야 하지?”라고 물으며 동적 계획법을 먼저 시도하는 편이 안전하다.

탐욕 알고리즘이 맞을 때도 있다. 하지만 그때도 형식적인 정당성 증명이 필요하다. 이 장의 목적은 탐욕을 금지하는 것이 아니라, 증명 없이 직관만으로 선택을 버리는 위험을 경계하게 하는 것이다.

3.6 최장 증가 부분수열

백트래킹 장의 첫 LIS 재귀식 LISbigger(i,j)는 두 인덱스로 상태를 나타낸다. 가능한 상태 수는 O(n^2)이고, 각 상태는 오른쪽 다음 열의 값들에만 의존한다.

FastLIS(A[1..n]):
  A[0] ← -infinity
  for i ← 0 to n
    LISbigger[i, n+1] ← 0
  for j ← n downto 1
    for i ← 0 to j-1
      skip ← LISbigger[i, j+1]
      take ← 1 + LISbigger[j, j+1]
      if A[i] ≥ A[j]
        LISbigger[i, j] ← skip
      else
        LISbigger[i, j] ← max(skip, take)
  return LISbigger[0, 1]

두 번째 재귀식 LISfirst(i)는 훨씬 간단하다. A[i]로 시작하는 최장 증가 부분수열은 뒤쪽의 더 큰 원소 중 하나를 다음 원소로 골라 이어 붙인다. 상태 수는 O(n)이고, 각 상태에서 뒤쪽 원소들을 훑으므로 전체 시간은 O(n^2), 공간은 O(n)이다.

FastLIS2(A[1..n]):
  A[0] ← -infinity
  for i ← n downto 0
    LISfirst[i] ← 1
    for j ← i+1 to n
      if A[j] > A[i]
        LISfirst[i] ← max(LISfirst[i], 1 + LISfirst[j])
  return LISfirst[0] - 1

3.7 편집 거리

두 문자열의 편집 거리는 삽입, 삭제, 치환을 몇 번 해야 하나의 문자열을 다른 문자열로 바꿀 수 있는지의 최솟값이다. 예를 들어 마지막 열의 정렬을 생각하면, 최적 정렬의 마지막 열을 제거한 나머지도 남은 두 접두사의 최적 정렬이어야 한다. 그렇지 않다면 더 짧은 정렬로 바꿔 전체도 개선할 수 있기 때문이다.

Edit(i,j)를 A[1..i]와 B[1..j]의 편집 거리라고 하자. 마지막 열은 세 가지 중 하나다. B[j]를 삽입하거나, A[i]를 삭제하거나, 두 글자를 맞춰 치환한다. 두 글자가 같으면 치환 비용은 0이다.

EditDistance(A[1..m], B[1..n]):
  for j ← 0 to n
    Edit[0,j] ← j
  for i ← 1 to m
    Edit[i,0] ← i
    for j ← 1 to n
      ins ← Edit[i,j-1] + 1
      del ← Edit[i-1,j] + 1
      rep ← Edit[i-1,j-1] + (A[i] ≠ B[j] ? 1 : 0)
      Edit[i,j] ← min(ins, del, rep)
  return Edit[m,n]

표의 각 칸은 왼쪽, 위쪽, 왼쪽 위 대각선 칸에만 의존하므로 행 우선 순서로 채우면 된다. 하위 문제는 (m+1)(n+1)개이고 각 칸 계산이 상수 시간이므로 시간과 공간은 O(mn)이다. 최적 편집 순서는 표를 채운 뒤 선택된 이전 칸을 거꾸로 따라가며 복원할 수 있다.

3.8 부분합

부분합 문제의 재귀 상태를 SS(i,t), 즉 X[i..n]의 어떤 부분집합이 합 t를 만들 수 있는지로 정의한다. 음수 목표는 저장할 필요가 없도록 경우를 나누면 다음 점화식이 된다.

FastSubsetSum(X[1..n], T):
  S[n+1,0] ← true
  for t ← 1 to T
    S[n+1,t] ← false
  for i ← n downto 1
    S[i,0] ← true
    for t ← 1 to X[i]-1
      S[i,t] ← S[i+1,t]
    for t ← X[i] to T
      S[i,t] ← S[i+1,t] or S[i+1,t-X[i]]
  return S[1,T]

이 알고리즘은 O(nT) 시간과 공간을 쓴다. T가 작을 때는 지수 시간 백트래킹보다 훨씬 좋지만, T 자체가 매우 크면 오히려 필요 없는 상태를 많이 채워 느릴 수 있다. 동적 계획법은 반복 계산을 줄이는 도구이지, 항상 모든 입력에서 더 빠른 마법은 아니다.

3.9 최적 이진 탐색 트리

최적 이진 탐색 트리의 점화식에는 구간 빈도 합 sum f[j]가 반복해서 등장한다. 이를 F(i,k)로 미리 계산하면 각 구간 합을 상수 시간에 조회할 수 있다.

InitF(f[1..n]):
  for i ← 1 to n
    F[i,i-1] ← 0
    for k ← i to n
      F[i,k] ← F[i,k-1] + f[k]

이제 OptCost(i,k)는 구간 i..k에 대한 최적 비용이다. 각 칸은 가능한 루트 r를 모두 시도하며, 왼쪽 구간과 오른쪽 구간의 비용에 구간 전체 빈도 F[i,k]를 더한다.

ComputeOptCost(i, k):
  OptCost[i,k] ← infinity
  for r ← i to k
    tmp ← OptCost[i,r-1] + OptCost[r+1,k]
    OptCost[i,k] ← min(OptCost[i,k], tmp)
  OptCost[i,k] ← OptCost[i,k] + F[i,k]

OptimalBST(f[1..n]):
  InitF(f)
  for i ← 1 to n+1
    OptCost[i,i-1] ← 0
  for d ← 0 to n-1
    for i ← 1 to n-d
      ComputeOptCost(i, i+d)
  return OptCost[1,n]

구간 길이 d가 작은 것부터 대각선 순서로 채우면 모든 의존 구간이 먼저 계산되어 있다. 상태 수는 O(n^2)이고, 각 상태에서 루트 후보를 O(n)개 시도하므로 전체 시간은 O(n^3), 공간은 O(n^2)이다.

3.10 트리 위 동적 계획법

동적 계획법의 저장 구조가 항상 배열일 필요는 없다. 트리에서 최대 독립집합을 찾는 문제를 보자. 독립집합은 서로 인접한 정점을 동시에 포함하지 않는 정점 집합이다. 일반 그래프에서는 어렵지만, 트리에서는 루트에서 아래로 내려가는 부분트리 구조를 이용해 선형 시간에 풀 수 있다.

MIS(v)를 v를 루트로 하는 부분트리의 최대 독립집합 크기라고 하자. v를 제외하면 자식들의 부분트리에서 마음대로 최대 독립집합을 고를 수 있다. v를 포함하면 모든 자식은 제외해야 하므로 손자들의 부분트리에서 고른다.

TreeMIS(v):
  skip ← 0
  for each child w of v
    skip ← skip + TreeMIS(w)
  keep ← 1
  for each grandchild x of v
    keep ← keep + x.MIS
  v.MIS ← max(skip, keep)
  return v.MIS

더 깔끔하게는 v를 포함하는 경우와 제외하는 경우를 따로 저장한다. 각 정점에는 두 값 MISyes, MISno만 있으면 된다. 후위 순회로 자식을 먼저 계산하면 전체가 O(n) 시간에 끝난다.

TreeMIS2(v):
  v.MISyes ← 1
  v.MISno ← 0
  for each child w of v
    TreeMIS2(w)
    v.MISyes ← v.MISyes + w.MISno
    v.MISno ← v.MISno + max(w.MISyes, w.MISno)
  return max(v.MISyes, v.MISno)

4.1 테이프에 파일 저장하기

길이가 각각 L[1..n]인 파일을 자기 테이프에 저장한다고 하자. 테이프는 앞에서부터 순서대로 훑어야 하므로, 위치 k에 있는 파일을 읽는 비용은 그 앞의 모든 파일 길이를 더한 값이다. 모든 파일을 같은 확률로 읽는다면, 순열 pi로 파일을 배치했을 때 기대 비용은 다음과 같다.

답은 짧은 파일부터 놓는 것이다. 증명은 인접한 두 파일을 바꾸는 교환 논증으로 충분하다. 어떤 위치에서 L[pi(i)] > L[pi(i+1)]이면 두 파일을 맞바꾸자. 앞의 파일은 뒤로 가며 비용이 줄고, 뒤의 파일은 앞으로 오며 비용이 늘지만, 전체 변화량은 (L[b] - L[a]) / n이므로 음수다. 따라서 잘못된 순서가 남아 있으면 항상 비용을 더 줄일 수 있고, 최적 배치는 길이 오름차순이어야 한다.

파일마다 접근 횟수 F[i]가 다르면 기준이 바뀐다. 길이가 같으면 자주 읽는 파일을 앞에 두는 것이 맞고, 길이와 빈도가 모두 다르면 L[i] / F[i]가 작은 파일을 앞에 둔다. 인접한 두 파일 a, b가 이 비율 순서를 어기면, 교환으로 바뀌는 총비용은 L[b]F[a] - L[a]F[b]이다. 비율 조건 L[a]/F[a] > L[b]/F[b]은 이 변화량이 음수라는 말과 같으므로, 교환하면 더 좋아진다.

StoreFiles(L[1..n], F[1..n]):
  sort files by increasing L[i] / F[i]
  write files in that order

4.2 수업 시간표 짜기

각 수업 i의 시작 시각 S[i]와 종료 시각 F[i]가 주어져 있고, 서로 겹치지 않는 수업을 가능한 한 많이 고르고 싶다고 하자. 동적 계획법으로 풀 수도 있지만, 이 문제에는 더 단순하고 빠른 탐욕 알고리즘이 있다. 종료 시간이 가장 빠른 수업부터 훑으며, 직전에 고른 수업과 겹치지 않는 수업을 즉시 고른다.

GreedySchedule(S[1..n], F[1..n]):
  sort classes by increasing finish time
  X <- empty list
  lastFinish <- -infinity
  for each class i in sorted order:
    if S[i] > lastFinish:
      append i to X
      lastFinish <- F[i]
  return X

핵심 보조정리는 "가장 먼저 끝나는 수업을 포함하는 최적 시간표가 적어도 하나 있다"는 것이다. 어떤 최적 시간표가 그 수업 f를 포함하지 않는다면, 그 시간표에서 가장 먼저 끝나는 수업 g를 f로 바꾼다. f는 g보다 늦게 끝나지 않으므로 이후 수업들과 새 충돌을 만들지 않는다. 수업 수는 변하지 않으니 여전히 최적이다.

이제 귀납적으로 증명할 수 있다. 탐욕 알고리즘은 먼저 f를 고르고, f가 끝난 뒤 시작하는 수업들만 남긴다. 위 보조정리에 의해 어떤 최적해는 f를 포함하므로, 남은 문제에서 다시 최적으로 고르면 전체도 최적이다. 더 직접적으로는 임의의 최적 시간표와 탐욕 시간표를 앞에서부터 비교하여, 처음 다른 선택을 탐욕 선택으로 바꾸어도 충돌이 생기지 않는다는 식으로도 증명할 수 있다.

정렬이 지배적이므로 실행 시간은 O(n log n)이다. 정렬 뒤의 선택 과정은 한 번의 선형 스캔이다.

4.3 일반적인 증명 패턴

앞의 두 예시는 같은 증명 구조를 따른다. 먼저 탐욕해와 다른 최적해가 있다고 가정한다. 그다음 두 해가 처음으로 달라지는 지점을 찾고, 최적해의 그 선택을 탐욕 선택으로 바꾸어도 해가 나빠지지 않음을 보인다. 이런 교환을 반복하면 탐욕 알고리즘의 모든 선택을 포함하는 최적해가 존재하게 된다.

• 탐욕 알고리즘이 만든 해와 다른 최적해를 하나 잡는다.
• 두 해의 첫 번째 차이를 찾는다.
• 최적해의 선택을 탐욕 선택으로 교환해도 타당성과 비용이 유지됨을 보인다.
• 귀납적으로 모든 탐욕 선택을 최적해 안으로 밀어 넣는다.

때로는 마지막에 한 단계가 더 필요하다. 예를 들어 수업 선택 문제에서는 "탐욕 선택들을 모두 포함하면서도 더 많은 수업을 담는 최적해"가 있을 수 없음을 따로 확인해야 한다. 그래야 탐욕해가 단지 어떤 최적해의 부분집합이 아니라 최적해 자체임을 말할 수 있다.

4.4 허프만 코드

이진 코드는 각 문자에 0과 1의 문자열을 배정한다. 어떤 코드어도 다른 코드어의 접두사가 아니면 접두사 없는 코드(prefix-free code)라고 한다. 이런 코드는 이진 트리로 표현할 수 있다. 문자는 잎에 놓이고, 루트에서 왼쪽으로 가면 0, 오른쪽으로 가면 1이라고 읽는다. 따라서 문자 i의 코드 길이는 그 잎의 깊이이다.

허프만 알고리즘은 매우 짧다. 가장 빈도가 낮은 두 문자를 합쳐 하나의 새 문자처럼 보고, 이 과정을 하나의 노드만 남을 때까지 반복한다. 예를 들어 빈도 1과 2의 두 문자가 가장 작다면 둘을 형제 잎으로 묶고 빈도 3의 내부 노드로 올려 보낸다. 모든 병합 기록을 거꾸로 펼치면 최종 코드 트리가 된다.

BuildHuffman(f[1..n]):
  for i <- 1 to n:
    L[i] <- 0; R[i] <- 0
    Insert(i, f[i])
  for i <- n+1 to 2n-1:
    x <- ExtractMin()
    y <- ExtractMin()
    f[i] <- f[x] + f[y]
    Insert(i, f[i])
    L[i] <- x; P[x] <- i
    R[i] <- y; P[y] <- i
  P[2n-1] <- 0
  return root 2n-1 and arrays L, R, P

왜 가장 드문 두 문자를 형제로 묶어도 되는가? 최적 코드 트리에서 가장 깊은 잎 두 개는 형제일 수 있다. 만약 가장 드문 문자 x, y가 그 자리에 없다면, 깊은 잎에 있는 다른 문자와 x, y를 바꿔도 비용은 증가하지 않는다. 빈도가 더 작은 문자를 더 깊게 놓는 교환이기 때문이다. 따라서 어떤 최적 트리에는 x와 y가 가장 깊은 형제 잎으로 존재한다.

그 뒤의 최적성은 재귀로 이어진다. x와 y를 빈도 f[x]+f[y]인 새 기호 z로 합친 작은 문제를 최적으로 풀었다고 하자. 작은 트리의 z 잎을 내부 노드로 바꾸고 x, y를 자식으로 붙이면 원래 문제의 트리가 된다. 이때 원래 트리 비용은 작은 트리 비용에 f[x]+f[y]를 더한 값이므로, 작은 문제를 최적으로 푸는 것이 원래 문제를 최적으로 푸는 것과 같다.

우선순위 큐를 이진 힙으로 구현하면 2n-1번의 삽입과 2n-2번의 최솟값 삭제가 필요하므로 전체 시간은 O(n log n)이다. 만들어진 트리로 인코딩할 때는 잎에서 부모 포인터를 따라 루트까지 올라간 뒤 비트를 역순으로 쓰고, 디코딩할 때는 루트에서 비트를 따라 내려가 잎에 도달할 때마다 문자를 출력한다.

4.5 안정 매칭

안정 매칭 문제에서는 같은 수의 의사와 병원이 있고, 각 의사는 병원 전체에 대한 선호 순서를, 각 병원은 의사 전체에 대한 선호 순서를 가진다고 하자. 완전 매칭이 불안정하다는 것은 어떤 의사 a와 병원 B가 서로 현재 상대보다 상대방을 더 좋아하는 경우가 있다는 뜻이다. 그런 쌍을 불안정 쌍이라고 하며, 목표는 불안정 쌍이 없는 매칭이다.

단순히 불안정 쌍을 찾아 계속 교환하는 방식은 실패할 수 있다. 한 불안정을 고치면 다른 불안정이 생겨 순환할 수 있기 때문이다. Gale-Shapley 알고리즘은 병원이 제안하고 의사가 잠정 수락하는 방식으로 이 문제를 해결한다. 각 병원은 아직 거절당하지 않은 의사 중 가장 선호하는 의사에게 제안한다. 의사는 매칭이 없으면 받아들이고, 이미 제안이 있으면 둘 중 더 좋은 병원을 남기며 다른 병원은 거절한다.

GaleShapley(Hospitals, Doctors):
  while some hospital A is unmatched:
    a <- highest-ranked doctor on A's list who has not rejected A
    if a is unmatched:
      match A with a
    else if a prefers A to her current hospital B:
      unmatch B
      match A with a
    else:
      a rejects A
  return matching

각 병원은 각 의사에게 최대 한 번만 제안하므로 제안 수는 최대 n^2이다. 선호 목록의 다음 후보, 현재 매칭, 의사가 두 병원을 비교하기 위한 순위 배열을 미리 준비하면 전체 구현도 O(n^2) 시간에 가능하다.

종료 시 모든 의사는 매칭되어 있다. 어떤 의사가 아직 매칭되지 않았다면 그 의사에게는 어떤 병원도 제안하지 않았다는 뜻이고, 그러면 아직 제안할 후보가 남은 미매칭 병원이 존재해야 하므로 알고리즘이 끝날 수 없다. 안정성도 간단하다. 최종적으로 의사 a가 병원 A와 매칭되었는데 병원 B를 더 좋아한다고 하자. 의사는 받은 제안 중 가장 좋은 제안을 유지하므로 B는 a에게 제안한 적이 없다. 병원은 최종 상대보다 더 선호하는 의사들에게 모두 먼저 제안했을 것이므로, B는 자기 최종 상대를 a보다 더 좋아한다. 따라서 (a,B)는 불안정 쌍이 아니다.

더 강한 사실도 성립한다. 병원이 제안하는 버전은 모든 안정 매칭 중 각 병원에게 가능한 최선의 상대를 준다. 의사가 병원을 거절하는 순간, 그 의사는 그 병원에게 어떤 안정 매칭에서도 가능한 상대가 아님을 귀납적으로 보일 수 있다. 반대로 의사 입장에서는 이 결과가 가능한 안정 매칭 중 최악일 수 있다. 제안하는 쪽이 유리하다는 점 때문에 실제 매칭 시장에서는 어느 쪽이 제안자가 되는지가 중요한 설계 문제가 된다.

5.1 소개와 역사

그래프적 사고는 현대 컴퓨터 과학보다 훨씬 오래되었다. 도로망과 여행 안내도, 족보와 친족 관계, 힘의 평형을 나타내는 역학 도표, 다면체의 꼭짓점과 변, 회로망과 통신망은 모두 그래프의 초기 사례로 볼 수 있다. 여기서 중요한 점은 그림의 모양이 아니라 연결 관계다. 지리적으로 정확하지 않은 노선도도 경로를 찾기에는 충분한 그래프 정보를 담을 수 있다.

"graph"라는 말은 19세기 후반에 추상적 구조의 이름으로 쓰이기 시작했고, "tree"는 연결되어 있으면서 순환이 없는 그래프를 가리키는 말로 자리 잡았다. 하지만 용어보다 본질이 먼저다. 그래프 알고리즘은 어떤 대상들이 서로 어떻게 닿아 있는지, 그리고 그 연결을 따라 무엇을 계산할 수 있는지를 묻는다.

5.2 기본 정의

단순 그래프는 G = (V, E)로 쓴다. V는 유한한 정점 집합이고, E는 정점 쌍들의 집합이다. 무방향 그래프에서 간선은 순서 없는 쌍 uv이고, 방향 그래프에서 간선은 순서 있는 쌍 u -> v이다. 관례적으로 V와 E를 각각 정점 수와 간선 수의 의미로도 사용한다.

무방향 간선 uv에서 u와 v는 서로 이웃이며, 정점의 차수는 이웃 수다. 방향 간선 u -> v에서는 u를 꼬리, v를 머리라고 하며, u는 v의 predecessor, v는 u의 successor이다. 이에 따라 indegree와 outdegree를 구분한다.

walk는 인접한 정점들을 따라가는 정점열이고, 같은 정점을 두 번 이상 방문하지 않으면 path이다. 무방향 그래프에서 모든 정점 쌍 사이에 경로가 있으면 연결되어 있다고 하며, maximal connected subgraph를 component라고 부른다. 닫힌 walk가 각 정점에 한 번씩만 들어가고 나오면 cycle이고, cycle이 없는 무방향 그래프는 forest, 연결된 forest는 tree이다.

방향 그래프에서는 방향을 따라가는 directed walk, directed path, directed cycle을 사용한다. 모든 정점 쌍 u, v에 대해 u에서 v로도, v에서 u로도 갈 수 있으면 strongly connected이다. 방향 cycle이 없는 그래프는 DAG(directed acyclic graph)라고 한다.

5.3 표현과 예

그래프는 보통 정점을 점으로, 간선을 곡선이나 선분으로 그려 표현한다. 하지만 특정 그림과 그래프 자체를 혼동하면 안 된다. 같은 그래프도 여러 방식으로 그릴 수 있고, 평면 그래프도 잘못 그리면 간선이 교차할 수 있다. 교차 없이 그릴 수 있는 그래프를 평면 그래프라고 하며, 그런 그림을 embedding이라고 한다.

다른 표현도 많다. 교차 그래프(intersection graph)는 기하 객체마다 정점을 두고, 두 객체가 만나면 간선을 둔다. 구간 그래프(interval graph)는 실수선 위 구간들의 교차 그래프다. 재귀 알고리즘의 의존 그래프(dependency graph)는 각 부분문제를 정점으로, 한 부분문제가 다른 부분문제를 필요로 하면 간선으로 나타낸 DAG이다.

편집 거리의 의존 그래프는 격자 모양이다. 정점은 (i,j)이고, 수직, 수평, 대각선 방향의 의존 간선이 생긴다. 동적 계획법은 이런 의존 그래프가 적당히 작고, 각 정점이 predecessor 뒤에 계산되도록 순서를 잡을 수 있을 때 효율적이다.

게임이나 퍼즐의 configuration graph도 중요하다. 각 상태를 정점으로, 한 번의 움직임으로 상태가 바뀌면 간선을 둔다. 이런 그래프는 보통 너무 커서 전체를 명시적으로 만들 수 없지만, 현재 상태에서 가능한 다음 상태를 열거할 수 있다면 그래프 알고리즘을 그대로 적용할 수 있다. 결국 그래프는 특정한 그림이 아니라 "것들의 쌍들의 집합"이다.

5.4 그래프 자료구조

표준적인 그래프 표현은 인접 리스트와 인접 행렬이다. 두 표현 모두 정점이 1..V의 정수 인덱스를 가진다고 가정한다. 인접 리스트는 각 정점마다 이웃 목록을 저장한다. 무방향 간선 uv는 u의 목록과 v의 목록에 한 번씩 저장되고, 방향 간선 u -> v는 u의 out-neighbor 목록에 저장된다. 공간은 O(V+E)이다.

표준 인접 리스트가 연결 리스트로 구현되어 있으면 정점 v의 이웃을 나열하는 데 Theta(1+deg(v)) 시간이 든다. 특정 간선이 있는지 확인하는 데는 방향 그래프에서 O(1+deg(u)), 무방향 그래프에서 두 목록을 함께 훑으면 O(1+min(deg(u),deg(v))) 시간이 든다. 이웃 목록을 균형 탐색 트리나 해시 테이블로 바꾸면 간선 존재 질의를 빠르게 할 수 있지만, 많은 그래프 알고리즘은 임의 간선 질의보다 모든 이웃 나열을 훨씬 자주 사용한다.

인접 행렬은 V x V 크기의 0/1 배열 A로, A[u,v]=1이면 간선이 있음을 뜻한다. 간선 존재 여부는 Theta(1)에 알 수 있지만, 한 정점의 이웃을 모두 나열하려면 행 전체를 훑어 Theta(V) 시간이 들고, 공간도 항상 Theta(V^2)이다. 따라서 매우 조밀한 그래프에서는 단순하고 빠르지만, 희소 그래프에는 보통 낭비가 크다.

이 교재의 그래프 알고리즘 시간 분석은 특별히 말하지 않는 한 표준 인접 리스트를 기준으로 한다. 암시적 그래프도 이 기준으로 이해할 수 있다. 예를 들어 레코드와 포인터로 이루어진 자료구조는 포인터를 간선으로 갖는 방향 그래프처럼 다룰 수 있고, 퍼즐 상태 공간은 현재 상태에서 가능한 이동을 이웃 목록처럼 생성하면 된다.

5.5 무엇이든 먼저 탐색

그래프의 가장 기본적인 전역 질문은 도달 가능성이다. 시작 정점 s에서 어떤 정점들에 도달할 수 있는가? 이를 위해 탐색 알고리즘은 후보 정점들을 담는 "bag"을 유지한다. bag이 스택이면 깊이 우선 탐색, 큐이면 너비 우선 탐색, 우선순위 큐이면 best-first search가 된다.

WhateverFirstSearch(s):
  put (None, s) into the bag
  while the bag is not empty:
    (p, v) <- take an item from the bag
    if v is unmarked:
      mark v
      parent(v) <- p
      for each edge v-w:
        put (v, w) into the bag

이 알고리즘은 s에서 도달 가능한 정점만 표시하고, 도달 가능한 모든 정점을 표시한다. 증명은 최단 경로 길이에 대한 귀납법으로 한다. s에서 v로 가는 최단 경로의 마지막 간선이 u-v라면, 귀납 가정에 의해 u는 언젠가 표시된다. 그때 (u,v)가 bag에 들어가므로, v도 이미 표시되어 있지 않다면 표시된다.

parent 간선들은 시작 정점이 속한 component의 spanning tree를 이룬다. 표시된 각 정점은 parent를 따라가면 결국 s에 도달하며, 시작 정점을 제외한 모든 표시 정점은 정확히 하나의 parent를 갖기 때문이다. 표준 인접 리스트에서 각 간선은 상수 번 bag에 들어가므로, bag 연산 하나가 T 시간이면 전체 시간은 O(V + E T)이다.

5.6 중요한 변형들

bag을 스택으로 구현하면 깊이 우선 탐색(DFS)이 된다. 스택의 push/pop은 O(1)이므로 실행 시간은 O(V+E)이고, parent 간선은 보통 길고 가느다란 DFS spanning tree를 만든다. 이 트리의 구조와 성질은 다음 장의 핵심 주제가 된다.

bag을 큐로 구현하면 너비 우선 탐색(BFS)이 된다. 큐 역시 상수 시간 연산을 제공하므로 시간은 O(V+E)이다. BFS parent tree는 시작 정점에서 각 정점까지의 최단 간선 수 경로를 포함한다. 직관적으로 DFS tree가 깊게 파고든다면 BFS tree는 가까운 층부터 넓게 퍼진다.

bag을 우선순위 큐로 구현하면 best-first search가 된다. 우선순위를 어떻게 정하느냐에 따라 서로 다른 알고리즘이 나온다. 무방향 가중 그래프에서 간선 가중치를 우선순위로 쓰면 minimum spanning tree를 얻고, 시작점에서의 현재 거리 추정값을 우선순위로 쓰면 양의 가중치 그래프의 shortest path tree를 얻는다. 경로의 폭을 "경로 위 최소 간선 가중치"로 정의하고 이를 최대화하도록 우선순위를 두면 widest path tree를 얻는다.

시작 정점 하나에서만 탐색하면 그 정점이 속한 도달 영역만 방문한다. 전체 그래프를 방문하려면 모든 정점을 훑으며 아직 표시되지 않은 정점에서 탐색을 다시 시작한다. 이 wrapper는 component를 세거나 각 정점에 component 번호를 붙일 때 그대로 쓰인다.

CountComponents(G):
  count <- 0
  unmark all vertices
  for each vertex v:
    if v is unmarked:
      count <- count + 1
      WhateverFirstSearch(v)
  return count

방향 그래프에서는 간선을 방향대로만 따라가면 된다. 즉 v를 표시할 때 v의 out-neighbor만 bag에 넣는다. 이때 parent 간선은 s에서 도달 가능한 정점들의 rooted tree를 이루지만, 도달 가능성이 대칭이 아니므로 그래프 전체의 spanning tree가 된다고 기대할 수는 없다.

5.7 그래프 환원: Flood Fill

flood fill은 픽셀 지도에서 주어진 픽셀이 속한 같은 색 연결 영역을 새 색으로 바꾸는 연산이다. 이를 그래프 문제로 바꾸면 간단하다. 각 픽셀을 정점으로 두고, 상하좌우로 인접하면서 색이 같은 픽셀 사이에 무방향 간선을 둔다. 그러면 하나의 같은 색 연결 영역은 이 그래프의 component가 된다.

따라서 flood fill은 시작 픽셀에서의 도달 가능성 문제다. 탐색으로 정점을 표시하는 순간 그 픽셀의 색을 새 색으로 바꾸면 된다. n x n 픽셀 지도에서 정점은 n^2개이고 간선은 많아야 2n^2개이므로 단순 분석으로 O(n^2) 시간이 든다.

FloodFill(M, start, newColor):
  oldColor <- M[start]
  put start into the bag
  while the bag is not empty:
    p <- take an item from the bag
    if M[p] = oldColor:
      M[p] <- newColor
      for each grid neighbor q of p:
        if M[q] = oldColor:
          put q into the bag

실제 구현에서는 별도의 그래프를 만들 필요가 없다. 픽셀 배열 자체가 암시적 인접 리스트다. 각 픽셀의 같은 색 이웃은 상수 개만 확인하면 된다. 더 정밀하게 분석하면 실행 시간은 전체 픽셀 수가 아니라 실제로 채워지는 연결 영역의 픽셀 수에 비례한다.

이 예시는 환원의 기본 형식을 보여 준다. 새 문제를 처음부터 풀지 않고 이미 알고 있는 문제의 입력으로 변환한다. 그래프를 어떻게 구성하는지, 기존 알고리즘의 출력을 원래 문제의 답으로 어떻게 해석하는지, 그리고 시간 분석을 원래 입력 크기로 다시 표현하는지가 환원의 핵심이다.

6.0 DFS의 기본 형태

가장 단순한 DFS는 정점이 아직 표시되지 않았을 때 표시하고, 나가는 간선을 따라 재귀 호출하는 알고리즘이다. 실제 구현에서는 재귀 호출 전에 방문 여부를 확인하여 각 정점에 대한 DFS(v) 호출이 한 번만 일어나게 만든다. 또한 PreVisit과 PostVisit 훅을 두면 탐색 중 다양한 정보를 계산할 수 있다.

DFS(v):
  mark v
  PreVisit(v)
  for each edge v -> w:
    if w is unmarked:
      parent(w) <- v
      DFS(w)
  PostVisit(v)

모든 정점을 훑으려면 DFSAll wrapper를 사용한다. 무방향 그래프에서는 각 component마다 하나의 DFS tree가 생겨 spanning forest를 얻는다. 방향 그래프에서는 도달 가능성이 대칭이 아니므로, 그래프가 약하게 연결되어 있어도 DFS tree의 개수와 모양은 정점 순서와 간선 순서에 따라 크게 달라질 수 있다.

DFSAll(G):
  Preprocess(G)
  unmark all vertices
  for each vertex v:
    if v is unmarked:
      DFS(v)

6.1 전위 순서와 후위 순서

DFS는 각 정점에 두 개의 시간을 붙인다. v.pre는 DFS(v)가 시작될 때, v.post는 DFS(v)가 끝날 때 기록한다. 한 전역 시계를 시작과 종료 때마다 1씩 증가시키면 모든 정점의 활성 구간 [v.pre, v.post]이 생긴다.

Preprocess(G):
  clock <- 0

PreVisit(v):
  clock <- clock + 1
  v.pre <- clock

PostVisit(v):
  clock <- clock + 1
  v.post <- clock

두 정점의 활성 구간은 서로 겹치지 않거나 한쪽이 다른 쪽을 완전히 포함한다. 포함 관계는 DFS forest의 조상-자손 관계와 정확히 일치한다. u가 v의 조상이라는 말은 u.pre <= v.pre < v.post <= u.post라는 말과 같다.

탐색 중 정점은 세 상태 중 하나다. 아직 호출되지 않았으면 new, 호출되었지만 반환되지 않았으면 active, 이미 반환되었으면 finished이다. active 정점들은 재귀 스택 위의 정점들이며, 항상 하나의 방향 경로를 이룬다. 간선 u -> v는 v의 상태와 활성 구간 관계에 따라 tree edge, forward edge, back edge, cross edge로 나뉜다.

• Tree edge: DFS(u)가 직접 DFS(v)를 호출한다.
• Forward edge: v가 u의 proper descendant지만 직접 자식은 아니다.
• Back edge: v가 u의 ancestor이며, DFS 중 active 정점으로 향한다.
• Cross edge: 두 활성 구간이 분리되어 있고, 이미 finished된 정점으로 향한다.

조상 판별 보조정리는 여러 방식으로 같은 사실을 말한다. u가 v의 조상인 것, 위의 시간 부등식이 성립하는 것, DFS(v) 직후 u가 active인 것, 그리고 DFS(u) 직전에 new 정점들만 지나는 u에서 v로의 경로가 존재하는 것은 모두 동치다.

6.2 cycle 검출

DAG는 방향 cycle이 없는 방향 그래프다. DFS의 간선 분류를 이용하면 방향 cycle을 선형 시간에 찾거나 없음을 확인할 수 있다. 어떤 간선 u -> v에 대해 u.post < v.post이면, v에서 u로 가는 DFS tree 경로와 간선 u -> v가 합쳐져 방향 cycle을 만든다. 특히 active 정점으로 향하는 back edge가 발견되면 cycle이 존재한다.

IsAcyclic(G):
  for each vertex v:
    v.status <- New
  for each vertex v:
    if v.status = New:
      if IsAcyclicDFS(v) = False:
        return False
  return True

IsAcyclicDFS(v):
  v.status <- Active
  for each edge v -> w:
    if w.status = Active:
      return False
    if w.status = New:
      if IsAcyclicDFS(w) = False:
        return False
  v.status <- Finished
  return True

모든 정점과 간선을 상수 번만 보므로 실행 시간은 O(V+E)이다. 이 알고리즘은 cycle 검출뿐 아니라 위상 정렬의 실패 조건을 감지하는 데도 그대로 쓰인다.

6.3 위상 정렬

방향 그래프의 위상 순서는 모든 간선 u -> v에 대해 u가 v보다 앞서는 정점의 전체 순서다. cycle이 있으면 위상 순서는 불가능하다. cycle 위에서 가장 오른쪽에 놓인 정점은 cycle의 다음 간선을 왼쪽으로 보내야 하기 때문이다.

반대로 DAG에서는 임의의 DFS 후위 순서를 뒤집으면 위상 순서가 된다. DAG에서는 어떤 간선 u -> v에 대해서도 u.post > v.post가 성립한다. 따라서 post 값이 큰 정점부터 나열하면 모든 간선이 앞에서 뒤로 향한다.

TopologicalSort(G):
  for each vertex v:
    v.status <- New
  clock <- V
  for each vertex v:
    if v.status = New:
      clock <- TopSortDFS(v, clock)
  return S[1..V]

TopSortDFS(v, clock):
  v.status <- Active
  for each edge v -> w:
    if w.status = New:
      clock <- TopSortDFS(w, clock)
    else if w.status = Active:
      fail: G has a directed cycle
  v.status <- Finished
  S[clock] <- v
  return clock - 1

실제 응용에서는 위상 순서 배열 자체가 목적이 아닐 때가 많다. DAG의 정점마다 어떤 계산을 수행해야 한다면, DFS의 PostVisit에서 처리하면 reverse topological order로 처리한 것과 같다. forward topological order가 필요하면 배열을 만들거나, 그래프의 모든 간선을 뒤집은 rev(G)에서 후위 처리를 이용할 수 있다.

6.4 메모이제이션과 동적 계획법

재귀식의 의존 그래프는 각 부분문제를 정점으로, 한 부분문제가 다른 부분문제를 필요로 하면 간선으로 나타낸 DAG이다. 메모이제이션은 이 의존 그래프에서 DFS를 수행하는 것과 같다. 이미 계산된 부분문제는 표시된 정점이고, 아직 계산되지 않은 부분문제는 재귀 호출로 들어간다.

Memoize(x):
  if value[x] is undefined:
    initialize value[x]
    for each subproblem y needed by x:
      Memoize(y)
      update value[x] using value[y]
    finalize value[x]
  return value[x]

동적 계획법은 같은 의존 그래프를 후위 순서, 즉 모든 의존 대상이 먼저 계산되는 순서로 처리한다. 많은 DP에서는 의존 그래프가 격자나 삼각형처럼 규칙적이어서, 실행 중에 위상 정렬을 하지 않고 중첩 반복문으로 평가 순서를 하드코딩한다. 그래도 개념적으로는 DAG의 postorder traversal이다.

DAG에서 최장 경로를 구하는 문제를 보자. 목표 정점 t를 고정하고, LLP(v)를 v에서 t까지 가는 최장 경로 길이라고 하자. 간선 길이를 ell(v,w)라 쓰면 다음 재귀식을 얻는다.

LongestPath(v, t):
  if v = t:
    return 0
  if v.LLP is undefined:
    v.LLP <- -infinity
    for each edge v -> w:
      v.LLP <- max(v.LLP, length(v,w) + LongestPath(w, t))
  return v.LLP

이 재귀의 의존 그래프는 입력 DAG 자체다. 따라서 DFS 메모이제이션으로도, postorder 순회 후 반복문으로도 O(V+E) 시간에 계산할 수 있다. 텍스트 분할, 부분집합 합, LIS, 편집 거리 같은 많은 DP 문제도 적절한 DAG의 최단/최장 경로 문제로 다시 볼 수 있다.

6.5 강한 연결성

방향 그래프에서 두 정점 u, v가 서로 도달 가능하면 strongly connected라고 한다. 이 관계는 동치 관계이므로 정점 집합을 equivalence class들로 나누며, 이 class들을 strongly connected components, 줄여서 strong components 또는 SCC라고 부른다.

그래프 전체가 하나의 SCC이면 strongly connected이고, 모든 SCC가 한 정점짜리이면 DAG다. 각 SCC를 하나의 정점으로 수축하고 SCC 사이의 간선만 남기면 strong component graph, 또는 condensation graph scc(G)를 얻는다. 이 그래프는 항상 DAG이다. 만약 SCC들 사이에 cycle이 있다면 그 cycle 위의 SCC들이 사실 서로 도달 가능해져 하나의 SCC여야 하기 때문이다.

한 정점 v의 SCC만 구하는 것은 쉽다. 원래 그래프에서 reach(v)를 구하고, 간선을 모두 뒤집은 그래프에서 reach^{-1}(v), 즉 v로 도달할 수 있는 정점들을 구한 뒤 교집합을 취하면 된다. 이는 O(V+E) 시간이다. 하지만 이 방법을 모든 SCC에 반복하면 최악의 경우 O(VE)가 되어 너무 느리다.

6.6 선형 시간 강한 연결 요소

모든 SCC 알고리즘의 핵심 관찰은 DFS forest 안에서 각 SCC가 연결된 subtree처럼 나타난다는 것이다. 임의의 SCC C에서 시작 시간이 가장 빠른 정점 r을 잡자. r의 parent가 있다면 그 parent는 더 먼저 시작했으므로 C 안에 있을 수 없다. 반면 C의 다른 모든 정점은 r이 호출되기 직전에 new 정점들만 지나는 경로로 도달 가능하므로, DFS forest에서 r의 자손이 된다.

Kosaraju-Sharir 알고리즘은 두 번의 탐색으로 SCC를 찾는다. 먼저 rev(G)에서 DFS를 수행하여 정점이 끝날 때 스택에 push한다. rev(G)의 마지막 후위 정점은 원래 그래프의 sink SCC 안에 있다. 둘째 단계에서는 원래 그래프를 스택에서 pop되는 순서로 DFS한다. 이때 각 DFS 호출은 정확히 하나의 SCC를 방문한다.

KosarajuSharir(G):
  S <- empty stack
  unmark all vertices; root[v] <- None for all v

  # Phase 1: DFS in rev(G), push vertices in postorder
  for each vertex v:
    if v is unmarked:
      PushPostRevDFS(v, S)

  # Phase 2: DFS in G, in reverse postorder of rev(G)
  while S is not empty:
    v <- Pop(S)
    if root[v] = None:
      LabelOneDFS(v, v)

PushPostRevDFS(v, S):
  mark v
  for each reversed edge v -> u in rev(G):
    if u is unmarked:
      PushPostRevDFS(u, S)
  Push(S, v)

LabelOneDFS(v, r):
  root[v] <- r
  for each edge v -> w in G:
    if root[w] = None:
      LabelOneDFS(w, r)

Tarjan 알고리즘은 한 번의 DFS와 보조 스택만으로 SCC를 찾는다. 각 정점 v에 대해 low(v)를, tree edge들을 따라간 뒤 최대 한 번의 non-tree edge를 사용해 도달할 수 있는 정점 중 가장 작은 시작 시간으로 정의한다. 탐색 중 아직 SCC가 확정되지 않은 정점만 보조 스택에 유지한다. low(v) = v.pre가 되는 순간, v는 하나의 sink SCC의 root이고, 그 SCC의 정점들은 스택 맨 위에서 v까지 연속해서 놓여 있다.

Tarjan(G):
  clock <- 0
  S <- empty stack
  unmark all vertices; root[v] <- None for all v
  for each vertex v:
    if v is unmarked:
      TarjanDFS(v)

TarjanDFS(v):
  mark v
  clock <- clock + 1
  v.pre <- clock
  v.low <- v.pre
  Push(S, v)
  for each edge v -> w:
    if w is unmarked:
      TarjanDFS(w)
      v.low <- min(v.low, w.low)
    else if root[w] = None:
      v.low <- min(v.low, w.pre)
  if v.low = v.pre:
    repeat:
      w <- Pop(S)
      root[w] <- v
    until w = v

Kosaraju-Sharir와 Tarjan 알고리즘은 모두 정점과 간선을 상수 번만 처리하므로 O(V+E) 시간에 SCC를 계산한다. Kosaraju-Sharir는 발상이 단순하고, Tarjan은 더 섬세하지만 한 번의 DFS로 끝난다는 장점이 있다.

7.1 서로 다른 간선 가중치

가중치가 같은 간선이 있으면 최소 신장 트리가 여러 개일 수 있다. 예를 들어 모든 간선 가중치가 1이면 모든 spanning tree가 MST이다. 알고리즘 설명을 단순하게 하기 위해 먼저 모든 간선 가중치가 서로 다르다고 가정한다. 이때 MST는 유일하다.

유일성 증명도 교환 논증이다. 서로 다른 두 MST T와 T'가 있다고 하자. T \ T'에서 가장 가벼운 간선을 e, T' \ T에서 가장 가벼운 간선을 e'라 하고, 대칭성을 이용해 w(e) <= w(e')라 하자. T' + e에는 정확히 하나의 cycle이 생긴다. 이 cycle에는 T에 없는 간선 e''가 있고, e''는 T' \ T에 속하므로 w(e'') >= w(e') >= w(e)이다.

이제 T'' = T' + e - e''를 만들면 다시 spanning tree이고, w(T'') <= w(T')이다. T'가 이미 MST이므로 두 무게는 같아야 하고, 결국 w(e)=w(e'')가 된다. 따라서 두 MST가 존재하려면 같은 가중치의 간선 쌍이 있어야 한다. 모든 가중치가 서로 다르면 MST는 유일하다.

실제 입력에 같은 가중치가 있어도, 간선의 끝점 번호를 이용해 일관된 tie-breaking을 정의하면 알고리즘은 마치 가중치가 모두 다른 것처럼 동작할 수 있다. 예컨대 먼저 가중치를 비교하고, 같으면 작은 끝점 번호, 그다음 큰 끝점 번호를 비교한다.

ShorterEdge(i, j, k, l):
  if w(i,j) < w(k,l): return (i,j)
  if w(i,j) > w(k,l): return (k,l)
  if min(i,j) < min(k,l): return (i,j)
  if min(i,j) > min(k,l): return (k,l)
  if max(i,j) < max(k,l): return (i,j)
  return (k,l)

7.2 하나의 일반 MST 알고리즘

고전적인 MST 알고리즘들은 거의 모두 하나의 틀에서 나온다. 중간 결과로 forest F를 유지하되, 항상 F가 실제 MST의 부분그래프라는 불변식을 지킨다. 처음에는 간선이 없는 V개의 한 정점 트리에서 시작하고, 안전한 간선을 추가하여 component들을 합친다. F가 하나의 spanning tree가 되면 불변식에 의해 그것이 MST이다.

현재 forest F에 대해 간선은 세 종류로 나뉜다. useless edge는 F의 같은 component 안의 두 정점을 잇는 간선이다. 이를 추가하면 cycle이 생기므로 MST에 필요 없다. safe edge는 어떤 component에서 바깥으로 나가는 간선 중 가장 가벼운 간선이다. 그 밖의 간선은 아직 undecided이다.

safe edge가 MST에 들어간다는 사실은 cut property이다. 임의의 정점 부분집합 S를 가르는 간선 중 가장 가벼운 간선 e를 생각하자. 어떤 spanning tree T가 e를 포함하지 않으면, T 안에는 S와 바깥을 잇는 다른 간선 e'가 있다. e'를 빼고 e를 넣으면 여전히 spanning tree이고 더 가벼워진다. 따라서 T는 MST가 아니다.

GenericMST(G):
  F <- (V, empty edge set)
  while F has more than one component:
    choose one or more safe edges for F
    add them to F
  return F

Boruvka, Jarnik, Kruskal 알고리즘은 모두 이 틀의 서로 다른 구현이다. 차이는 매 단계 어떤 safe edge를 선택하고, 그것을 얼마나 빠르게 찾느냐에 있다.

7.3 Boruvka 알고리즘

Boruvka 알고리즘은 각 반복에서 모든 component의 safe edge를 한꺼번에 추가한다. 한 줄로 요약하면 "모든 안전한 간선을 추가하고 반복하라"이다. 여러 component가 같은 간선을 safe edge로 고를 수도 있지만, 그런 중복은 forest를 망치지 않는다.

Boruvka(V, E):
  F <- (V, empty edge set)
  count <- CountAndLabel(F)
  while count > 1:
    AddAllSafeEdges(E, F, count)
    count <- CountAndLabel(F)
  return F

AddAllSafeEdges(E, F, count):
  for i <- 1 to count:
    safe[i] <- Null
  for each edge u-v in E:
    if comp(u) != comp(v):
      if safe[comp(u)] = Null or w(u-v) < w(safe[comp(u)]):
        safe[comp(u)] <- u-v
      if safe[comp(v)] = Null or w(u-v) < w(safe[comp(v)]):
        safe[comp(v)] <- u-v
  for i <- 1 to count:
    add safe[i] to F

각 반복은 모든 간선을 한 번 훑어 각 component의 safe edge를 찾고, 현재 forest의 component를 다시 라벨링한다. forest에는 많아야 V-1개의 간선만 있으므로 라벨링은 O(V), 간선 스캔은 O(E)이고, 연결 그래프에서는 V <= E+1이므로 반복당 O(E)이다.

매 반복마다 component 수는 적어도 절반으로 줄어든다. 각 component가 적어도 하나의 safe edge를 내보내고, 최악의 경우 component들이 둘씩만 합쳐지기 때문이다. 따라서 반복 수는 O(log V), 전체 시간은 O(E log V)이다. 이 알고리즘은 component별 작업이 독립적이어서 병렬화가 쉽고, 평면 그래프 같은 "nice"한 그래프에서는 더 빠른 변형도 가능하다.

7.4 Jarnik 알고리즘

Jarnik 알고리즘은 보통 Prim 알고리즘이라는 이름으로 더 널리 알려져 있다. 이 알고리즘은 forest 안에 하나의 비자명 component T만 키운다. 임의의 시작 정점에서 출발하여, 매 단계 T에서 바깥으로 나가는 가장 가벼운 간선을 추가한다.

간단한 구현은 T에 인접한 모든 간선을 우선순위 큐에 넣는다. 최솟값 간선을 꺼냈을 때 양 끝점이 이미 T 안에 있으면 버리고, 그렇지 않으면 그 간선을 추가한 뒤 새로 들어온 정점의 incident edge들을 큐에 넣는다. 이는 5장의 best-first search를 MST용 우선순위로 실행한 것이다. 이진 힙을 쓰면 시간은 O(E log E) = O(E log V)이다.

JarnikSimple(G, s):
  T <- ({s}, empty edge set)
  insert all edges incident to s into a priority queue
  while T has fewer than V vertices:
    e <- ExtractMin()
    if e has exactly one endpoint outside T:
      add e and that endpoint to T
      insert all edges incident to the new vertex
  return T

Fibonacci heap을 사용하면 정점을 우선순위 큐에 넣고, 각 정점의 우선순위를 현재 T와 연결하는 가장 가벼운 간선의 무게로 유지할 수 있다. DecreaseKey가 상각 O(1), ExtractMin이 상각 O(log V)이므로 실행 시간은 O(E + V log V)가 된다. 다만 실제 구현에서는 상수와 복잡도가 커서, 매우 큰 조밀 그래프가 아니면 단순 이진 힙 구현이 더 실용적일 때가 많다.

JarnikWithVertexQueue(V, E, s):
  T <- ({s}, empty edge set)
  for each vertex v != s:
    priority(v) <- w(s-v) if s-v exists, otherwise infinity
    edge(v) <- s-v if s-v exists, otherwise Null
    Insert(v)
  repeat V-1 times:
    v <- ExtractMin()
    add v and edge(v) to T
    for each neighbor u of v:
      if u is not in T and priority(u) > w(u-v):
        edge(u) <- u-v
        DecreaseKey(u, w(u-v))
  return T

7.5 Kruskal 알고리즘

Kruskal 알고리즘은 모든 간선을 가중치 오름차순으로 훑는다. 현재 forest의 서로 다른 component를 잇는 간선이면 safe edge이므로 추가하고, 같은 component 안을 잇는 간선이면 useless edge이므로 버린다.

Kruskal(V, E):
  sort E by increasing weight
  F <- (V, empty edge set)
  for each vertex v:
    MakeSet(v)
  for each edge u-v in sorted E:
    if Find(u) != Find(v):
      Union(u, v)
      add u-v to F
  return F

올바름은 safe edge 관점에서 바로 나온다. 간선을 가벼운 것부터 보므로, 현재 서로 다른 component를 잇는 간선 e보다 더 가벼운 crossing edge가 남아 있을 수 없다. 그런 간선이 있었다면 이미 앞에서 처리되었을 것이고, 그때 두 component를 합쳤을 것이기 때문이다. 따라서 e는 어떤 component의 safe edge이다.

component 관리는 disjoint-set union 자료구조로 한다. MakeSet은 한 정점짜리 집합을 만들고, Find는 정점이 속한 집합의 대표를 반환하며, Union은 두 집합을 합친다. 간선 정렬에 O(E log E)=O(E log V) 시간이 들고, 보통의 union-find 구현 비용은 이보다 작거나 비슷하므로 전체 시간은 O(E log V)로 볼 수 있다.

union-by-rank와 path compression을 쓰면 Find와 Union의 상각 시간은 거의 상수인 O(alpha(V))가 된다. 그래도 비교 기반 정렬을 그대로 사용하면 Kruskal 알고리즘의 병목은 여전히 간선 정렬이다.

8.1 최단 경로 트리

단일 시작점 최단 경로(SSSP) 문제는 시작 정점 s에서 모든 정점 v까지의 최단 경로를 구한다. 최단 경로가 유일하면, 그 경로들의 합집합은 자연스럽게 s를 뿌리로 하는 방향 트리가 된다. 최단 경로가 여러 개여도 각 정점마다 하나씩 적절히 선택하면 역시 하나의 최단 경로 트리를 만들 수 있다.

이 트리는 최소 신장 트리와 다르다. 최단 경로 트리는 시작점에 의존하고, 방향 그래프에서 가장 자연스럽고, 각 정점까지의 거리 합이 아니라 개별 s-v 경로 길이를 최적화한다. 반면 최소 신장 트리는 보통 무방향 그래프에서 전체 간선 가중치 합을 최소화한다.

• 최단 경로 트리: 루트 s에서 각 정점까지의 경로가 최단이다.
• 최소 신장 트리: 모든 정점을 연결하는 간선 집합의 총 가중치가 최소다.
• 간선 가중치가 모두 달라도, 시작점이 바뀌면 최단 경로 트리는 완전히 달라질 수 있다.

8.2 음수 간선

거리나 시간처럼 가중치가 실제 길이를 나타낼 때는 모든 간선 가중치가 음이 아니라고 생각하기 쉽다. 그러나 비용, 이익, 잠재량 차이 같은 값을 모델링하면 음수 간선이 자연스럽게 등장한다. 문제는 음수 사이클이다. s에서 t로 가는 어떤 경로가 음수 사이클을 지나갈 수 있다면, 그 사이클을 한 번 더 돌 때마다 전체 길이가 더 작아지므로 최단 경로가 정의되지 않는다.

정확히 말하면 s에서 t로 가는 최단 walk가 존재하려면, s에서 t로 가는 경로가 적어도 하나 있어야 하고, s에서 t로 가는 어떤 경로도 음수 사이클을 건드리면 안 된다. 이 장에서는 이 미묘함 때문에 주로 방향 그래프를 다룬다. 무방향 음수 간선을 단순히 양방향 간선 두 개로 바꾸면 길이 2의 음수 사이클이 생기므로, 무방향 음수 간선은 훨씬 조심스럽게 다루어야 한다.

8.3 단 하나의 SSSP 알고리즘: 완화

많은 최단 경로 알고리즘은 하나의 일반 원리, 즉 긴장된 간선(tense edge)을 완화(relax)하는 과정으로 설명된다. 각 정점 v는 현재 알고 있는 s-v 경로 길이의 상한 dist(v)와, 그 경로에서 v 바로 앞 정점 pred(v)를 저장한다. 처음에는 dist(s)=0, 나머지는 ∞로 둔다.

간선 u→v가 다음 부등식을 만족하면, 현재 v까지의 추정 경로는 명백히 더 줄일 수 있다. 이때 u→v를 완화한다.

InitSSSP(s):
    dist(s) ← 0
    pred(s) ← Null
    for every vertex v ≠ s:
        dist(v) ← ∞
        pred(v) ← Null

Relax(u→v):
    dist(v) ← dist(u) + w(u→v)
    pred(v) ← u

FordSSSP(s):
    InitSSSP(s)
    while some edge u→v is tense:
        Relax(u→v)

알고리즘이 멈추어 더 이상 긴장된 간선이 없다면, pred 포인터는 최단 경로 트리를 이룬다. 증명은 네 가지 관찰로 이루어진다. dist(v)는 항상 실제 s-v walk의 길이이거나 ∞이고, 음수 사이클이 없으면 가능한 단순 경로 수가 유한하므로 무한히 줄어들 수 없다. 또한 pred 경로와 다른 더 짧은 경로가 있다면 그 경로의 마지막 어딘가에 긴장된 간선이 남아야 하므로 모순이다.

8.4 무가중 그래프: 너비 우선 탐색

모든 간선 가중치가 1이면 경로 길이는 간선 개수다. 이 경우 BFS는 Ford식 완화 알고리즘의 가장 단순한 구현이다. FIFO 큐에 s를 넣고, 정점 u를 꺼낼 때마다 모든 간선 u→v를 검사하여 처음 발견한 정점의 거리를 dist(u)+1로 정한다.

BFS(s):
    InitSSSP(s)
    Push(s)
    while queue is not empty:
        u ← Pull()
        for every edge u→v:
            if dist(v) > dist(u) + 1:
                dist(v) ← dist(u) + 1
                pred(v) ← u
                Push(v)

분석은 큐를 거리별 층으로 나누어 보면 선명하다. i번째 단계가 끝났을 때 큐에는 정확히 거리 i인 정점들이 들어 있다. 따라서 각 정점은 한 번만 큐에 들어가고, 각 간선도 한 번만 검사된다. 전체 시간은 O(V+E)다.

정확성은 임의의 s-v 경로 v₀, v₁, ..., v_ℓ에 대해 dist(v_j) ≤ j임을 귀납적으로 보이면 된다. 즉 BFS가 찾은 거리는 어떤 경로 길이보다도 크지 않다. 반대로 pred 포인터를 따라가면 그 길이를 갖는 실제 경로가 나오므로, 이 값은 최단 거리다.

8.5 방향 비순환 그래프: 위상 순서 완화

DAG에서는 음수 간선이 있어도 음수 사이클이 없다. 따라서 최단 거리 함수는 다음 점화식으로 안전하게 정의된다. 일반 그래프에서는 순환 의존 때문에 이 식을 그대로 재귀 평가할 수 없지만, DAG에서는 위상 순서가 의존성을 끊어 준다.

정점들을 위상 순서로 훑으며 들어오는 간선을 완화해도 되고, 더 Ford 알고리즘답게 위상 순서로 정점 u를 보면서 나가는 간선 u→v를 완화해도 된다. 어느 쪽이든 모든 간선은 정확히 한 번 의미 있게 검사되므로 시간은 O(V+E)다.

PushDagSSSP(s):
    InitSSSP(s)
    for every vertex u in topological order:
        for every outgoing edge u→v:
            if u→v is tense:
                Relax(u→v)

정확성은 위상 순서에 대한 귀납법으로 증명한다. u를 처리할 때, u로 들어오는 모든 경로의 마지막 이전 정점들은 이미 처리되었다. 그러므로 dist(u)는 더 이상 줄어들 수 없고, u에서 나가는 완화는 이후 정점들에 올바른 후보를 전달한다.

8.6 최선 우선: 다익스트라 알고리즘

BFS의 FIFO 큐를 dist 값을 키로 하는 우선순위 큐로 바꾸면 다익스트라 알고리즘이 된다. 매번 현재 추정 거리가 가장 작은 정점을 꺼내고, 그 정점에서 나가는 간선을 완화한다.

Dijkstra(s):
    InitSSSP(s)
    Insert(s, 0)
    while priority queue is not empty:
        u ← ExtractMin()
        for every edge u→v:
            if u→v is tense:
                Relax(u→v)
                if v is in the priority queue:
                    DecreaseKey(v, dist(v))
                else:
                    Insert(v, dist(v))

모든 간선 가중치가 음이 아니면, 꺼내지는 정점들의 거리 값은 감소하지 않는다. 어떤 정점 v가 한 번 ExtractMin으로 확정된 뒤 다시 더 짧아지려면, 그 사이에 음수 간선이 개입해야 한다. 따라서 비음수 그래프에서 각 정점은 한 번만 확정되고, 각 간선은 한 번만 완화된다.

이 경우 이진 힙을 쓰면 Insert, ExtractMin, DecreaseKey가 O(log V)이므로 전체 시간은 O(E log V)이다. 조밀한 그래프에서는 배열 기반 O(V²) 구현이 더 나을 수 있고, 더 복잡한 우선순위 큐를 쓰면 이론적으로 O(E+V log V)까지 개선된다. 음수 간선이 있으면 같은 정점과 간선이 여러 번 다시 처리될 수 있어 최악의 경우 지수 시간이 걸릴 수 있다.

8.7 모든 간선 완화: 벨만-포드

벨만-포드 알고리즘은 가장 직접적인 Ford식 구현이다. 매 단계 모든 간선을 훑으며 긴장된 간선을 전부 완화한다. 음수 간선이 있어도 동작하고, 음수 사이클도 감지할 수 있다.

BellmanFord(s):
    InitSSSP(s)
    repeat V - 1 times:
        for every edge u→v:
            if u→v is tense:
                Relax(u→v)
    for every edge u→v:
        if u→v is tense:
            return "Negative cycle!"

핵심 불변식은 i번의 전체 간선 스캔 뒤, dist(v)가 "간선을 최대 i개 쓰는 s-v walk"의 최단 길이 이하라는 것이다. 음수 사이클이 없다면 최단 walk는 단순 경로이며, 간선을 최대 V-1개만 쓴다. 따라서 V-1번 스캔하면 모든 거리가 확정된다. 그 뒤에도 줄어드는 간선이 있다면 도달 가능한 음수 사이클이 존재한다.

동적 계획법 관점에서는 dist≤i(v)를 간선 수가 i 이하인 최단 walk 길이로 두고 다음 점화식을 쓴다.

2차원 표를 행별로 채우는 구현에서 시작해, 같은 행을 제자리 갱신하도록 최적화하면 표준 벨만-포드가 된다. 시간은 O(VE), 공간은 거리와 predecessor만 저장하면 O(V)다.

9.1 도입

모든 쌍 최단 경로(APSP) 문제는 모든 정점쌍 (u, v)에 대해 u에서 v로 가는 최단 거리와 predecessor를 계산한다. 출력은 보통 V×V 거리 배열 dist[u,v]와 predecessor 배열 pred[u,v]다.

경계 사례도 명확히 정한다. u에서 v로 가는 경로가 없으면 dist[u,v]=∞다. u에서 v로 가는 과정에서 음수 사이클을 거칠 수 있으면 길이를 임의로 작게 만들 수 있으므로 dist[u,v]=-∞로 본다. u가 음수 사이클 위에 있지 않다면 dist[u,u]=0이다.

9.2 단일 시작점 알고리즘을 여러 번 실행하기

가장 직관적인 APSP 알고리즘은 각 정점을 한 번씩 시작점으로 삼아 SSSP를 실행하는 것이다.

ObviousAPSP(V, E, w):
    for every vertex s:
        dist[s, ·] ← SSSP(V, E, w, s)

그래프 종류에 따라 총 시간이 달라진다. 무가중 그래프에서는 BFS를 V번 실행해 O(VE)=O(V³), DAG에서는 위상 순서 SSSP를 V번 실행해 O(VE), 비음수 가중치에서는 다익스트라로 O(VE log V), 일반 가중치에서는 벨만-포드로 O(V²E)가 된다.

9.3 재가중

음수 간선을 없애기 위해 모든 간선에 같은 상수를 더하는 방법은 실패한다. 간선 수가 많은 경로가 더 많이 벌점을 받으므로 최단 경로 자체가 바뀔 수 있기 때문이다. 대신 각 정점에 가격 π(v)를 붙이고 다음처럼 간선 가중치를 바꾸면, 같은 시작점과 끝점을 잇는 모든 경로 길이가 같은 양만큼만 변한다.

경로 u⇝v의 중간 정점에서 받은 가격과 낸 가격은 서로 상쇄된다. 따라서

가 되어, u에서 v로 가는 경로들 사이의 상대적 순서는 변하지 않는다. 이 성질이 Johnson 알고리즘의 핵심이다.

9.4 존슨 알고리즘

Johnson 알고리즘은 먼저 모든 정점에 도달하는 인공 시작점 s를 추가하고, s에서 모든 정점으로 가중치 0인 간선을 넣는다. 그 다음 Bellman-Ford를 한 번 실행해 π(v)=dist(s,v)를 얻는다. Bellman-Ford가 음수 사이클을 발견하면 APSP는 정상적으로 정의되지 않는다.

이 가격을 사용하면 모든 원래 간선 u→v에 대해 dist(s,u)+w(u→v)≥dist(s,v)이므로 w′(u→v)≥0이다. 따라서 이후에는 각 정점을 시작점으로 하여 다익스트라를 실행할 수 있다. 마지막으로 재가중된 거리 dist′를 원래 거리로 되돌린다.

JohnsonAPSP(V, E, w):
    add a new source s
    for every vertex v:
        add edge s→v with weight 0

    h[·] ← BellmanFord(s)
    if a negative cycle is found:
        fail

    for every edge u→v:
        w′(u→v) ← h[u] + w(u→v) - h[v]

    for every vertex u:
        dist′[u, ·] ← Dijkstra(w′, u)

    for every pair u, v:
        dist[u, v] ← dist′[u, v] - h[u] + h[v]

이진 힙 다익스트라를 기준으로 전체 시간은 O(VE log V)이다. 음수 간선은 허용하지만 음수 사이클은 허용하지 않는 희소 그래프에서 특히 유용하다.

9.5 동적 계획법

APSP를 직접 동적 계획법으로 풀 수도 있다. dist(u,v,ℓ)을 u에서 v로 가는, 간선을 최대 ℓ개 쓰는 최단 경로 길이라고 하자. 음수 사이클이 없다면 실제 최단 경로는 간선을 최대 V-1개 쓴다.

AllPairsBellmanFord(V, E, w):
    for every u, v:
        dist[u, v] ← 0 if u = v else ∞
    for ℓ ← 1 to V - 1:
        for every vertex u:
            for every edge x→v:
                if dist[u, v] > dist[u, x] + w(x→v):
                    dist[u, v] ← dist[u, x] + w(x→v)

이 알고리즘은 본질적으로 V개의 Bellman-Ford 실행을 서로 엮어 놓은 형태다. 시간은 O(V²E), 조밀 그래프에서는 O(V⁴)이다.

9.6 분할 정복

Bellman식 점화식은 경로를 "더 짧은 경로 + 마지막 간선"으로 나눈다. Fischer-Meyer식 관점은 경로를 중간 정점 x에서 두 개의 절반 경로로 나눈다. 간선 수 제한 ℓ이 2의 거듭제곱이라고 생각하면 다음 점화식이 나온다.

ℓ을 1, 2, 4, ...로 두 배씩 늘리면 O(log V)번의 단계만 필요하다. 각 단계에서 모든 삼중쌍 (u,x,v)을 검사하므로 시간은 O(V³ log V)이다. 제자리 갱신을 사용하면 공간은 O(V²)로 줄어든다.

LeyzorekAPSP(V, E, w):
    for every u, v:
        dist[u, v] ← w(u→v)
    for i ← 1 to ⌈lg V⌉:
        for every u:
            for every v:
                for every x:
                    if dist[u, v] > dist[u, x] + dist[x, v]:
                        dist[u, v] ← dist[u, x] + dist[x, v]

9.7 이상한 행렬 곱셈

최단 경로 계산은 행렬 거듭제곱과 닮았다. 일반 행렬 곱에서는 덧셈과 곱셈을 사용하지만, 최단 경로에서는 덧셈 대신 최솟값을, 곱셈 대신 더하기를 쓴다. 이를 min-plus 또는 tropical 곱셈이라고 부른다.

가중 인접 행렬 W에 대해 W의 min-plus 제곱은 간선을 최대 2개 쓰는 최단 거리, 네제곱은 최대 4개 쓰는 최단 거리, 계속해서 충분히 큰 거듭제곱은 APSP 거리 행렬을 준다. 이 연결은 APSP와 빠른 행렬 곱셈 사이의 깊은 관계를 설명하지만, 일반 가중치에서 곧바로 Floyd-Warshall보다 실용적으로 빠른 알고리즘이 되는 것은 아니다.

9.8 Floyd-Warshall 알고리즘

Floyd-Warshall은 세 번째 매개변수를 "사용할 수 있는 중간 정점의 번호"로 잡는다. π(u,v,r)을 중간 정점이 1..r에만 속하는 u-v 최단 경로라고 하자. 최적 경로는 정점 r을 쓰지 않거나, r을 써서 u⇝r과 r⇝v로 나뉜다.

FloydWarshall(V, E, w):
    for every u, v:
        dist[u, v] ← w(u→v)
    for every vertex r:
        for every vertex u:
            for every vertex v:
                if dist[u, v] > dist[u, r] + dist[r, v]:
                    dist[u, v] ← dist[u, r] + dist[r, v]

루프 순서가 중요하다. r을 바깥 루프에 두면 dist[u,v]는 "지금까지 허용한 중간 정점들만 쓰는 최단 거리"라는 의미를 유지한다. 시간은 O(V³), 공간은 O(V²)이며, 조밀 그래프에서 단순하고 강력한 표준 알고리즘이다.

10.1 흐름

(s,t)-흐름은 각 간선에 실수 값을 주는 함수 f:E→R이며, s와 t를 제외한 모든 정점에서 유입량과 유출량이 같아야 한다. 또한 용량이 주어지면 0≤f(e)≤c(e)를 만족해야 feasible flow다.

흐름의 값 |f|는 소스에서 순수하게 빠져나가는 양이다. 보존 법칙을 모든 정점에 대해 합하면, 이는 싱크로 순수하게 들어가는 양과 같다는 사실이 바로 따라온다.

10.2 컷

(s,t)-컷은 정점 집합을 S와 T로 나누되 s∈S, t∈T가 되게 하는 분할이다. 컷의 용량은 S에서 T로 넘어가는 간선들의 용량 합이다. T에서 S로 되돌아가는 간선은 컷 용량에 포함하지 않는다.

어떤 feasible flow f와 어떤 cut (S,T)에 대해서도 |f|≤‖S,T‖이다. 증명은 S 내부 정점들의 순유출량을 더하면 내부 간선은 서로 상쇄되고, S에서 T로 나가는 흐름에서 T에서 S로 들어오는 흐름을 뺀 값이 남는다는 계산이다.

등호가 성립하려면 S에서 T로 가는 모든 간선은 포화되어야 하고, T에서 S로 가는 모든 간선에는 흐름이 없어야 한다. 따라서 같은 값을 갖는 흐름과 컷을 찾으면 둘 다 최적이다.

10.3 최대흐름-최소컷 정리

최대흐름-최소컷 정리는 모든 네트워크에서 최대 흐름의 값이 최소 컷의 용량과 같다고 말한다. 증명의 중심 도구는 현재 흐름 f에 대한 잔여 용량과 잔여 그래프다.

잔여 그래프 G_f에서 s에서 t로 가는 경로가 있으면 이를 증가 경로라고 한다. 경로의 최소 잔여 용량 F만큼 흐름을 밀면, 정방향 간선의 흐름은 늘리고 역방향 간선의 흐름은 줄여 더 큰 feasible flow를 얻는다.

반대로 잔여 그래프에서 s가 t에 도달하지 못하면, S를 s에서 도달 가능한 정점들의 집합으로 둔다. 그러면 S에서 T로 가는 모든 원래 간선은 포화되어 있고 T에서 S로 가는 간선에는 흐름이 없다. 앞 절의 부등식에서 등호가 성립하므로 f는 최대 흐름이고 (S,T)는 최소 컷이다.

10.4 Ford-Fulkerson 증가 경로 알고리즘

정리의 증명은 곧 알고리즘을 준다. 0 흐름에서 시작하여 잔여 그래프에 s-t 경로가 있는 동안 그 경로를 따라 가능한 만큼 흐름을 증가시킨다.

FordFulkerson(G, c, s, t):
    f(e) ← 0 for every edge e
    while there is an s-t path P in the residual graph G_f:
        F ← min residual capacity on P
        augment f along P by F
    return f

모든 용량이 정수이면 매 증가량 F도 양의 정수다. 따라서 각 반복에서 |f|가 적어도 1 증가하고, 최대 흐름값 |f*|번 이하의 반복 뒤 멈춘다. 한 반복에 O(E)가 걸리므로 O(E|f*|) 시간이다. 이 정수성 정리는 또한 정수 용량 네트워크에는 정수 최대 흐름이 존재함을 보장한다.

그러나 증가 경로를 아무렇게나 고르면 최악의 경우 입력 비트 수에 대해 지수 시간이 될 수 있다. 용량이 무리수이면 알고리즘이 영원히 멈추지 않거나 최대 흐름에 수렴하지 않는 실행도 가능하다. 따라서 증가 경로 선택 규칙이 중요하다.

10.5 흐름의 결합과 분해

두 흐름 f,g의 선형결합 αf+βg도 흐름이며 값은 α|f|+β|g|이다. 특히 s-t 경로 하나를 따라 1을 보내는 path flow와, 방향 사이클을 따라 1을 순환시키는 cycle flow를 기본 조각으로 볼 수 있다.

흐름 분해 정리는 모든 비음수 (s,t)-흐름이 양의 계수를 갖는 s-t 경로 흐름들과 방향 사이클 흐름들의 합으로 표현된다고 말한다. 또한 양의 흐름이 흐르는 간선은 적어도 하나의 조각에 나타나며, 필요한 경로와 사이클 수는 E개 이하로 잡을 수 있다.

증명은 Ford-Fulkerson을 거꾸로 돌리는 느낌이다. 양의 흐름이 남아 있으면, s에서 시작해 양의 흐름 간선을 따라가서 t에 도달하거나 사이클을 찾는다. 그 경로나 사이클 위의 최소 흐름량을 빼면 적어도 한 간선의 흐름이 0이 되고, 귀납적으로 계속한다. 구현 시간은 O(VE)이다.

10.6 Edmonds-Karp 알고리즘들

Edmonds와 Karp는 증가 경로를 고르는 두 가지 규칙을 분석했다. 첫째는 병목 용량이 가장 큰, 즉 가장 두꺼운 증가 경로를 고르는 것이다. 이 경로는 최대 병목 경로 문제로, 다익스트라와 비슷한 best-first 탐색으로 O(E log V)에 찾을 수 있다.

정수 용량에서 가장 두꺼운 경로를 쓰면 잔여 최대 흐름값이 매번 적어도 1/E 비율만큼 줄어든다. 따라서 O(E log |f*|)번 정도의 증가 뒤 잔여 최대 흐름이 1 미만이 되고, 정수성 때문에 0이 된다. 전체 시간은 다항식이다.

둘째 규칙은 잔여 그래프에서 간선 수가 가장 적은 증가 경로를 고르는 것이다. BFS로 찾을 수 있으며, 보통 Edmonds-Karp 알고리즘이라고 부르는 것은 이 버전이다. 핵심 분석은 각 정점의 BFS 레벨이 시간이 지날수록 감소하지 않고, 각 잔여 간선이 사라졌다 다시 나타날 때 관련 레벨이 적어도 2 증가한다는 점이다.

10.7 이후의 발전

최대 흐름 알고리즘은 이후 수십 년 동안 계속 발전했다. blocking flow, network simplex, push-relabel, pseudoflow, dynamic tree를 이용한 변형 등 다양한 조합 알고리즘이 알려져 있다. 이 교재 수준의 알고리즘 분석에서는 다음 문장을 표준 도구처럼 사용할 수 있다.

단위 용량 네트워크에서는 더 빠른 알고리즘도 있다. 예를 들어 Dinitz/Karzanov식 blocking flow 분석은 O(min{V^2/3, E^1/2}E) 시간 경계를 주고, 이후 더 정교한 알고리즘들이 알려졌다. 다만 실제 응용 절에서는 보통 O(VE) 최대 흐름 서브루틴으로 충분하다.

11.1 간선 서로소 경로

방향 그래프에서 s에서 t로 가는 간선 서로소 경로의 최대 개수는 각 간선 용량을 1로 둔 최대 흐름값과 같다. 최대 흐름의 정수성 때문에 각 간선은 0 또는 1만큼만 사용되고, 흐름 분해를 하면 포화된 간선들은 s-t 경로들과 사이클들로 나뉜다. 사이클을 무시하면 원하는 경로 집합이 나온다.

반대로 k개의 간선 서로소 경로가 있으면 각 경로에 1씩 흘려 값 k인 흐름을 만들 수 있다. 무방향 그래프에서는 각 무방향 간선을 양방향 용량 1 간선 두 개로 바꾸고, 흐름 사이클을 제거하면 각 사용 간선에 일관된 방향이 생긴다.

11.2 정점 용량과 정점 서로소 경로

정점에도 용량이 있다면, 각 정점 v를 v_in과 v_out으로 쪼개고 그 사이에 용량 c(v)의 간선을 둔다. 원래 간선 u→v는 u_out→v_in으로 바꾼다. 그러면 정점을 통과하는 모든 흐름이 반드시 v_in→v_out 간선을 지나므로 정점 용량 제약이 간선 용량 제약으로 바뀐다.

VertexSplit(G):
    for every vertex v:
        create v_in and v_out
        add edge v_in→v_out with capacity c(v)
    for every original edge u→v:
        add edge u_out→v_in with the original edge capacity

정점 서로소 s-t 경로 최대 개수는 s,t를 제외한 모든 정점 용량을 1로 두고 이 변환 뒤 최대 흐름을 계산하면 된다.

11.3 이분 매칭

이분 그래프 G=(L∪R,E)의 최대 매칭은 최대 흐름으로 바로 환원된다. 새 소스 s에서 L의 모든 정점으로 용량 1 간선을 넣고, 원래 간선은 L에서 R 방향의 용량 1 간선으로 둔다. R의 모든 정점에서 새 싱크 t로 용량 1 간선을 넣는다.

매칭의 각 간선 u-v는 경로 s→u→v→t에 1의 흐름을 보내는 것과 같다. 반대로 정수 최대 흐름에서 L-R 사이 포화된 간선들은 서로 끝점을 공유할 수 없으므로 매칭이다. 따라서 최대 흐름값은 최대 매칭 크기와 같다.

Ford-Fulkerson 관점에서 보면 매 반복은 현재 매칭에 대한 alternating path를 찾고 대칭차 M⊕P로 매칭 크기를 1 늘리는 과정이다. 이것은 Berge의 augmenting path characterization과 같은 내용이다.

11.4 튜플 선택

튜플 선택 문제는 여러 자원 집합 X₁,...,X_d에서 각 집합의 원소 하나씩을 골라 d-튜플을 만들되, 원소별 용량과 인접 자원쌍별 용량을 지키며 가능한 한 많은 튜플을 고르는 문제다. 자원 집합들이 선형으로 배열되고 제약이 인접한 집합 사이에만 있으면 흐름으로 풀 수 있다.

각 원소를 정점으로 만들고, X_i의 원소 x에서 X_i+1의 원소 y로 용량 c(x,y)의 간선을 둔다. 원소 자체의 사용 제한은 정점 용량으로 표현하고, 필요하면 정점 분할로 간선 용량으로 바꾼다. s에서 X₁로, X_d에서 t로 간선을 넣으면, s-t 경로 하나가 선택된 튜플 하나를 나타낸다.

예컨대 시험 시간표 문제에서는 class→room→time→proctor 경로 하나가 한 과목의 시험 배정을 뜻한다. 강의는 한 번만 배정되고, 방-시간 조합은 한 시험만 쓰고, 감독은 가능한 시간에만 배정되며 총 횟수 제한을 갖도록 각 간선과 정점 용량을 둔다.

11.5 서로소 경로 덮개

방향 그래프의 path cover는 모든 정점을 적어도 한 경로에 포함하는 경로들의 집합이고, disjoint path cover는 각 정점이 정확히 한 경로에만 들어가는 경우다. 일반 그래프에서는 경로 하나로 덮을 수 있는지 묻는 것만으로도 Hamiltonian path 문제가 되어 어렵지만, DAG에서는 이분 매칭으로 풀 수 있다.

DAG G의 각 정점 v를 왼쪽 복사본 v^-과 오른쪽 복사본 v⁺으로 만들고, 원래 간선 u→v마다 이분 그래프에 u^-v⁺ 간선을 넣는다. 크기 m의 매칭은 m개의 "어떤 정점 뒤에 어떤 정점이 온다" 관계를 선택한 것이다. V개의 정점으로 이루어진 disjoint path cover에서 간선 수가 V-k이면 경로 수는 k다.

수업-교수 배정 문제도 같은 형태다. 한 교수가 수업 i 다음에 수업 j를 맡을 수 있으면 i→j 간선을 넣은 DAG를 만들고, 최소 경로 덮개를 구하면 필요한 교수 수의 최솟값이 나온다.

11.6 야구 탈락

어떤 팀 n이 아직 지구 1위를 할 가능성이 있는지 판단하려면, 팀 n이 남은 경기를 모두 이긴다고 가정한다. 그러면 다른 팀 i가 앞으로 이길 수 있는 최대 경기 수는 W[n]+R[n]-W[i]로 제한된다. 남은 경기들의 승자를 이 제한 안에서 배정할 수 있는지가 문제다.

흐름 네트워크는 게임 정점과 팀 정점으로 이루어진다. 소스에서 각 게임 정점 g_i,j로 용량 G[i,j]를 보내고, 게임 정점에서 두 팀 정점으로 무한 용량 간선을 둔다. 각 팀 정점 t_i에서 싱크로 가는 간선 용량은 W[n]+R[n]-W[i]다.

소스에서 나가는 모든 간선이 포화되는 feasible flow가 존재하면, 모든 남은 경기의 승자를 배정하면서도 어떤 팀도 n의 최대 승수보다 앞서지 않게 할 수 있다. 포화시킬 수 없다면 n은 수학적으로 탈락했다. 네트워크 크기는 O(n²)이고 최대 흐름으로 판정한다.

11.7 프로젝트 선택

프로젝트마다 이익 또는 비용이 있고, 어떤 프로젝트는 다른 프로젝트가 선행되어야 할 수 있다. 선택한 프로젝트 집합 S는 prerequisite에 대해 닫혀 있어야 하며, 총 이익을 최대화해야 한다. 이는 최소 컷 문제로 바뀐다.

이익이 양수인 프로젝트 v에는 s→v 간선을 용량 profit(v)로 넣고, 비용이 있는 프로젝트 u에는 u→t 간선을 용량 -profit(u)로 넣는다. 의존성 u→v, 즉 u를 하려면 v도 해야 한다는 조건은 용량 ∞ 간선 u→v로 넣는다.

유한 용량 컷 (S,T)는 선택된 프로젝트 S가 모든 의존성을 만족함을 뜻한다. 양의 이익 총합을 P라고 하면, 컷 용량은 선택한 비용과 포기한 이익을 합친 값이고 선택 이익은 P-‖S,T‖다. 따라서 최소 컷을 찾으면 최대 이익 프로젝트 집합이 나온다.

12.1 이길 수 없는 게임

CircuitSat는 불리언 회로가 주어졌을 때, 입력 스위치 값을 적절히 정해 출력이 True가 되게 할 수 있는지 묻는 문제다. 특정 입력 하나가 주어지면 회로를 한 번 평가해 다항 시간, 실제로는 선형 시간에 확인할 수 있다. 하지만 만족시키는 입력이 존재하는지 찾는 일반 알고리즘은 알려진 최선이 본질적으로 2ⁿ개 입력을 모두 시도하는 방식이다.

이 장의 출발점은 "해답을 확인하는 일은 쉬워 보이지만, 해답을 찾는 일은 아주 어려워 보이는" 문제들이다. CircuitSat는 그 대표 사례이며, Cook-Levin 정리에 의해 모든 NP 문제의 어려움을 품고 있는 기준 문제가 된다.

12.2 P 대 NP

결정 문제는 답이 Yes 또는 No인 문제다. P는 다항 시간에 풀 수 있는 결정 문제들의 집합이다. NP는 Yes라는 답에 대해, 그 사실을 증명하는 인증서가 주어지면 다항 시간에 검증할 수 있는 결정 문제들의 집합이다. co-NP는 No 답을 다항 시간에 검증할 수 있는 문제들의 집합이다.

• P: 빠르게 풀 수 있는 문제.
• NP: Yes 증거를 빠르게 확인할 수 있는 문제.
• co-NP: No 증거를 빠르게 확인할 수 있는 문제.

모든 P 문제는 NP에도 co-NP에도 속한다. 하지만 NP의 모든 문제가 P에 속하는지는 아무도 모른다. 대부분의 알고리즘 연구자는 P≠NP라고 믿지만, 엄밀한 증명은 없다. 이 열린 문제가 이 장의 모든 "난해성" 주장의 배경이다.

12.3 NP-hard, NP-easy, NP-complete

문제 Π가 NP-hard라는 말은, Π를 다항 시간에 풀 수 있다면 NP의 모든 문제를 다항 시간에 풀 수 있다는 뜻이다. 즉 Π는 적어도 NP의 모든 문제만큼 어렵다.

NP-easy는 보통 NP에 속한다는 뜻으로 쓰이며, NP-hard이면서 NP에도 속하는 문제를 NP-complete라고 한다. NP-complete 문제 하나라도 다항 시간 알고리즘이 발견되면 모든 NP 문제가 다항 시간에 풀린다. Cook-Levin 정리는 CircuitSat가 NP-hard임을 보장하는 첫 기준점이다.

12.4 형식적 정의

엄밀한 복잡도 이론에서는 문제를 문자열 집합, 즉 언어로 보고, 계산 모델로 튜링 기계를 사용한다. P는 결정론적 튜링 기계가 다항 시간에 판정하는 언어들의 집합이고, NP는 비결정론적 튜링 기계가 다항 시간에 판정하는 언어들의 집합이다.

NP-hardness는 환원으로 정의된다. Cook 환원은 어떤 문제를 풀 때 다른 문제의 해답기를 여러 번 서브루틴처럼 호출할 수 있는 환원이고, Karp 환원은 입력 x를 f(x)로 한 번 바꾸어 답이 보존되게 하는 many-one 환원이다.

이 장에서 다루는 표준 NP-hardness 증명은 모두 다항 시간 Karp 환원으로 이해해도 충분하다.

12.5 환원과 SAT

어떤 문제 A가 NP-hard임을 보이려면 이미 NP-hard인 문제를 A로 환원한다. 방향이 중요하다. A를 어려운 문제로 환원하는 것이 아니라, 어려운 문제를 A의 가상 알고리즘으로 풀 수 있음을 보여야 한다.

SAT는 불리언 공식이 만족 가능한지 묻는다. CircuitSat에서 SAT로 가는 환원은 회로의 각 내부 와이어를 변수로 만들고, 각 게이트의 의미를 등식으로 적은 뒤, 마지막 출력 변수가 True임을 요구한다. 회로를 만족시키는 입력은 모든 와이어 값까지 확장되어 공식을 만족시키고, 공식을 만족시키는 배정은 입력 변수만 남겨 회로를 만족시킨다.

CircuitSat(K):
    transcribe circuit K into a Boolean formula Φ
    return Sat(Φ)

전사는 회로 크기에 선형인 시간에 가능하므로, SAT가 다항 시간에 풀리면 CircuitSat도 다항 시간에 풀린다. 따라서 SAT는 NP-hard다.

12.6 3SAT

3SAT는 CNF 공식 중 각 절이 정확히 세 리터럴을 갖는 경우의 만족 가능성 문제다. CircuitSat에서 직접 3SAT로 환원할 수 있다. 먼저 모든 AND/OR 게이트를 입력 2개짜리로 바꾸고, 각 와이어를 변수로 둔다.

각 게이트는 CNF 절들로 바꾼다. 예를 들어 a=b∧c는 세 절로, a=b∨c도 세 절로, a=¬b는 두 절로 표현된다.

a = b ∧ c  ↦  (a ∨ ¬b ∨ ¬c) ∧ (¬a ∨ b) ∧ (¬a ∨ c)
a = b ∨ c  ↦  (¬a ∨ b ∨ c) ∧ (a ∨ ¬b) ∧ (a ∨ ¬c)
a = ¬b     ↦  (a ∨ b) ∧ (¬a ∨ ¬b)

두 리터럴 절은 새 변수 x를 써서 (a∨b∨x)∧(a∨b∨¬x)로 만들고, 한 리터럴 절도 두 새 변수를 써서 네 개의 3-리터럴 절로 확장한다. 각 단계는 만족 가능성을 보존하고 전체 크기는 상수배만 증가하므로 3SAT는 NP-hard다.

12.7 최대 독립 집합

그래프의 독립 집합은 서로 인접한 두 정점을 포함하지 않는 정점 집합이다. MaxIndSet가 NP-hard임은 3SAT에서 환원해 보인다. k개의 절을 가진 3CNF 공식 Φ에 대해, 각 리터럴 발생 하나마다 정점을 만들고, 같은 절 안의 세 정점을 삼각형으로 연결한다. 또한 어떤 리터럴과 그 부정 리터럴에 해당하는 정점쌍도 모두 연결한다.

각 절 삼각형에서 독립 집합은 최대 하나의 정점만 고를 수 있으므로 크기는 최대 k다. Φ가 만족 가능하면 각 절에서 True인 리터럴 하나를 고르면 크기 k 독립 집합이 된다. 반대로 크기 k 독립 집합이 있으면 각 절에서 하나씩 골린 것이고, 모순 리터럴끼리는 간선으로 막혀 있으므로 일관된 진리값 배정을 만들 수 있다. 이 배정은 모든 절을 만족시킨다.

12.8 일반 패턴

다항 시간 환원 X≤_pY는 세 부분으로 이루어진다. 첫째, X의 임의 입력 x를 Y의 특수 입력 y로 다항 시간에 바꾼다. 둘째, x의 Yes 인증서를 y의 Yes 인증서로 바꿀 수 있음을 보인다. 셋째, y의 Yes 인증서를 다시 x의 Yes 인증서로 바꿀 수 있음을 보인다.

1. instance transformation: x ↦ y
2. forward certificate: x의 해답 ⇒ y의 해답
3. backward certificate: y의 해답 ⇒ x의 해답

주의할 점은 입력 변환은 한 방향이지만, 정확성 증명은 양방향이라는 것이다. 다만 역방향 증명은 Y의 모든 입력을 다루는 것이 아니라, 환원이 만들어 낸 특수한 y만 다룬다. 좋은 환원은 바로 이 특수 구조를 설계하는 일이다.

12.9 클리크와 정점 덮개

클리크는 모든 정점쌍이 간선으로 연결된 완전 부분그래프다. 그래프 G의 보수 그래프 Ḡ에서는, G의 독립 집합이 정확히 Ḡ의 클리크가 된다. 따라서 MaxClique는 MaxIndSet에서 즉시 환원되어 NP-hard다.

정점 덮개는 모든 간선을 적어도 한 끝점에서 만지는 정점 집합이다. I가 독립 집합일 필요충분조건은 V\I가 정점 덮개라는 것이다. 따라서 n정점 그래프에서 최대 독립 집합 크기가 α이면 최소 정점 덮개 크기는 n-α다. MinVertexCover 역시 NP-hard다.

12.10 그래프 색칠

3Color는 그래프 정점들을 세 색으로 칠하되, 모든 간선의 양 끝 색이 다르게 할 수 있는지 묻는다. 3SAT에서 3Color로 환원할 때는 의미를 강제하는 gadget을 사용한다.

먼저 T, F, X 세 정점으로 이루어진 삼각형을 만들어 세 색의 이름을 고정한다. 각 변수 a에는 a와 ¬a 정점을 만들고 둘 다 X와 삼각형을 이루게 하여 두 정점이 T/F 중 반대 색을 갖도록 강제한다. 각 절에는 세 리터럴 중 적어도 하나가 T색이어야만 전체가 3색칠 가능한 clause gadget을 붙인다.

만족 배정이 있으면 리터럴 정점들을 T/F로 칠하고 각 clause gadget을 완성할 수 있다. 반대로 3색칠이 있으면 각 변수 gadget에서 진리값을 읽을 수 있고, 모든 clause gadget은 적어도 하나의 True 리터럴을 강제하므로 원래 공식이 만족된다.

12.11 해밀턴 순환

해밀턴 순환은 모든 정점을 정확히 한 번 방문하는 순환이다. 방향 그래프의 HamiltonianCycle은 VertexCover 또는 3SAT에서 환원해 NP-hard임을 보일 수 있다.

VertexCover 환원에서는 원래 그래프의 각 간선을 edge gadget으로, 각 정점을 incident edge gadget들을 잇는 vertex chain으로 바꾼다. 추가로 k개의 cover vertex를 두어 해밀턴 순환이 정확히 k개의 vertex chain을 통과하게 만든다. 어떤 chain을 선택하는지는 원래 그래프에서 정점 덮개에 포함할 정점을 뜻한다. 모든 edge gadget의 정점들이 방문되려면 원래 모든 간선이 선택된 chain 중 적어도 하나에 닿아야 하므로, 선택된 정점들은 vertex cover다.

3SAT 환원에서는 각 변수 gadget을 양방향 사슬로 만들어 왼쪽에서 오른쪽으로 지나가면 True, 반대로 지나가면 False를 뜻하게 한다. 각 절 정점은 그 절을 만족시키는 리터럴의 방향에서만 detour로 방문할 수 있게 연결한다. 따라서 해밀턴 순환은 모든 절 정점을 방문할 수 있을 때, 곧 만족 배정이 있을 때만 존재한다.

해밀턴 경로, 무방향 해밀턴 순환/경로, 그리고 모든 간선 가중치가 1인 경우를 포함하는 traveling salesman 문제도 이들로부터 쉽게 NP-hard가 된다.

12.12 부분집합 합

SubsetSum은 양의 정수 집합 X와 목표 T가 주어졌을 때 합이 T인 부분집합이 있는지 묻는다. VertexCover에서 환원한다. 그래프의 각 간선 i에 대해 b_i=4ⁱ를 만들고, 각 정점 v에 대해 그 정점에 닿는 간선 자리들이 1이고 가장 높은 자리도 1인 수 a_v를 만든다.

크기 k의 vertex cover C가 있으면 C에 해당하는 a_v들을 고르고, 정확히 한 끝점만 C에 들어간 간선에 대해 b_i를 더하면 각 낮은 자리 숫자가 2가 되고 높은 자리는 k가 된다. 반대로 합이 T가 되는 부분집합이 있으면, 낮은 각 자리에서 2를 만들려면 각 간선의 적어도 한 끝점에 해당하는 a_v가 선택되어야 한다. 따라서 선택된 정점들은 크기 k 이하의 vertex cover다.

주의할 점은 SubsetSum에 O(nT) 동적 계획 알고리즘이 있다는 사실과 모순되지 않는다는 것이다. T는 입력 비트 수에 비해 지수적으로 클 수 있으므로 O(nT)는 진정한 다항 시간이 아니라 pseudo-polynomial 시간이다. 이런 문제를 weakly NP-hard라고 부른다.

12.13 유용한 다른 NP-hard 문제들

새로운 NP-hardness 증명을 만들 때는 이미 잘 알려진 기준 문제를 고르는 일이 중요하다. 대표적인 출발점으로 PlanarCircuitSat, 1-in-3Sat, NotAllEqual3Sat, Planar3Sat, Exact3DimensionalMatching, Partition, 3Partition, SetCover, HittingSet, LongestPath, SteinerTree, Max2Sat, MaxCut 등이 있다.

• SetCover와 HittingSet은 작은 집합을 고르는 문제의 출발점으로 좋다.
• 3Partition은 숫자와 작은 그룹 분할이 함께 등장하는 강한 NP-hardness 증명에 자주 쓰인다.
• LongestPath와 HamiltonianPath는 순서나 방문 순열을 강제하는 문제에 잘 맞는다.
• Planar3Sat류 문제는 평면성 제약이 있는 기하/그래프 문제에 유용하다.

퍼즐과 게임의 일반화도 자주 NP-hard 또는 그 이상으로 나타난다. 지뢰찾기, 스도쿠, 테트리스, 팩맨, 슈퍼 마리오, 2048, 루빅스 큐브 최단해 같은 문제들이 그런 예다.

12.14 올바른 출발 문제 고르기

환원을 설계할 때 가장 어려운 단계는 어떤 알려진 NP-hard 문제에서 시작할지 고르는 것이다. 완전한 규칙은 없지만, 문제의 형태를 보면 좋은 후보가 보인다.

• 비트 배정, 부분집합 선택, 두 부분으로 나누기: SAT, 3SAT, Partition.
• 작은 수의 라벨 배정: 3Color 또는 kColor.
• 객체를 순서대로 배열하기: HamiltonianPath, HamiltonianCycle, TSP.
• 작은 부분집합 찾기: VertexCover, SetCover, HittingSet.
• 큰 부분집합 찾기: IndependentSet, Clique, Max2Sat.
• 많은 작은 묶음으로 나누기: 3Partition 또는 X3M.

가능하면 문제의 어려움을 가장 직접적으로 닮은 단순한 출발 문제를 고르는 것이 좋다. 너무 복잡한 게임이나 퍼즐에서 시작하면, 환원 자체가 불필요하게 다루기 어려워진다.

12.15 가벼운 실제 예: 국제 드래프츠

국제 드래프츠는 체커와 비슷하지만, 킹이 대각선으로 여러 칸 움직일 수 있고, 가능한 한 많은 말을 반드시 잡아야 한다는 전역 최대 포획 규칙이 있다. 고정된 10×10 보드에서는 모든 상태를 상수 크기 표로 생각할 수도 있지만, n×n 보드로 일반화하면 단순히 합법적인 수를 찾는 일조차 NP-hard가 된다.

환원은 HamiltonianCycle에서 온다. 그래프의 정점은 "vault" gadget으로, 간선은 대각선 통로와 corner/crossing gadget으로 표현한다. 흰 킹이 한 번의 이동으로 많은 검은 말을 잡으려면 vault들을 그래프의 해밀턴 순환 순서로 방문해야 한다. N을 충분히 크게 잡아 정점 gadget 내부 포획 수가 다른 보조 gadget의 영향을 압도하게 하면, 많은 말을 잡을 수 있음과 원래 그래프의 해밀턴 순환 존재가 동치가 된다.

12.16 P와 NP 너머

P와 NP는 더 큰 복잡도 계층의 시작일 뿐이다. PSPACE는 다항 공간으로 풀 수 있는 결정 문제들의 집합이며, QBF(수량화된 불리언 공식)는 대표적인 PSPACE-hard 문제다. 많은 일반화된 2인 게임도 PSPACE-hard로 나타난다.

EXP 또는 EXPTIME은 지수 시간에 풀 수 있는 문제들의 집합이다. PSPACE는 EXP에 포함되며, P≠EXP는 증명되어 있지만 P와 PSPACE, NP와 EXP의 분리는 아직 모른다. 일부 일반화된 체스, 바둑, 체커류 게임은 규칙의 종료 조건에 따라 PSPACE에 머무르거나 EXP-hard가 된다.

그 위로 NEXP, EXPSPACE, 이중/삼중 지수 시간과 공간 계층이 이어진다. 알려진 포함 관계는 다음과 같지만, 인접한 포함이 모두 엄격한지는 대부분 미해결이다.

ELEMENTARY는 고정된 높이의 지수탑 시간 또는 공간으로 풀 수 있는 문제들의 합집합이다. 심지어 이 범위를 벗어나는 자연스러운 결정 문제도 존재한다는 사실은, "계산 가능"과 "효율적" 사이의 간격이 얼마나 넓은지를 잘 보여 준다.