17주차: 고급 알고리즘과 최적화

학습 목표

이번 주차를 마치면 다음을 할 수 있습니다:

동적 계획법(DP)이 성립하는 두 조건(겹치는 부분 문제, 최적 부분 구조)을 말하고, “상태 → 점화식 → 기저” 3단계로 문제를 정리할 수 있다
메모이제이션(하향식)과 테이블(상향식)을 각각 구현하고, 어느 쪽을 언제 쓸지 고를 수 있다
0/1 배낭, LCS, 동전 거스름돈을 DP로 풀고, 표를 거꾸로 걸어 “무엇을 골랐는지”까지 복원할 수 있다
백트래킹의 “선택 → 재귀 → 취소” 리듬으로 N-Queens와 부분집합·조합·순열 생성을 짤 수 있다
분기한정이 백트래킹을 어떻게 가속하는지 숫자로 설명할 수 있다
빠른 거듭제곱으로 분할 정복을 구현하고, 마스터 정리로 시간 복잡도를 계산할 수 있다
탐욕이 정답인 문제와 함정인 문제를 구별하고, 반례를 직접 만들어 확인할 수 있다

들어가며

같은 답을 내는 두 프로그램이 있습니다. 하나는 함수를 1억 2,649만 번 부르고, 다른 하나는 75번 부릅니다. 계산 결과는 둘 다 39088169로 똑같습니다. 무엇이 다를까요?

두 번째 프로그램은 첫 번째 프로그램에 딱 세 줄을 더한 것입니다. “한 번 계산한 답은 노트에 적어 두고, 다음에 같은 질문이 오면 노트를 본다.” 이 세 줄이 이번 주의 첫 번째 주제, 동적 계획법입니다.

Part 2의 마지막 주입니다. 10주차부터 8주 동안 자료구조(“데이터를 어떻게 담을까”)와 알고리즘(“어떻게 다룰까”)을 배웠습니다. 오늘은 그 정점인 알고리즘 설계 패러다임을 다룹니다. 패러다임이란 개별 알고리즘이 아니라 문제를 공략하는 사고방식입니다. 지금까지 배운 알고리즘들이 개별 도구였다면, 오늘 배울 것은 “어떤 도구를 언제 꺼낼지 정하는 눈”입니다.

패러다임	한 줄 요약	대표 문제	이번 주 예제
동적 계획법(DP)	작은 답을 적어 두고 조립한다	배낭, LCS, 편집 거리	1~4절
백트래킹	가보고, 막히면 되돌아온다	N-Queens, 스도쿠, 미로	5~7절
분할 정복	반으로 쪼개 각각 정복한다	병합 정렬, 빠른 거듭제곱	8절
탐욕법	매 순간 최선을 골라도 될 때 고른다	활동 선택, 최소 신장 트리	9절

사실 우리는 이 패러다임들을 이미 여러 번 만났습니다. 병합 정렬과 퀵 정렬(15주차)은 분할 정복이었고, 다익스트라와 크루스칼(14주차)과 허프만(16주차)은 탐욕법이었으며, 편집 거리(16주차)와 플로이드-워셜(14주차)은 DP였습니다. 오늘은 그것들에 이름을 붙여 정리하고, 처음 보는 문제에 적용하는 훈련을 합니다.

이번 주의 목표는 하나입니다. 문제를 보면 어떤 무기를 뽑을지 아는 눈. 마지막 프로젝트에서 세 가지 실전 문제에 각각 다른 무기를 꽂아 보며 그 눈을 완성합니다.

준비

예제 코드는 week17/examples/와 week17/projects/에 있습니다. make 한 번이면 전부 build/ 폴더에 만들어집니다.

$ cd week17
$ make
컴파일: examples/coin_change.c
...
✓ 모든 파일 빌드 완료!
$ ls build
algo_library  algo_visualizer  coin_change  combinations  divide_conquer
fib_dp  greedy  knapsack  lcs  maze_backtrack  nqueens  optimizer

예제 하나만 따로 컴파일하고 싶으면 1주차부터 쓰던 명령 그대로입니다.

$ gcc -Wall -Wextra -std=c11 -g examples/fib_dp.c -o build/fib_dp

이 글의 모든 실행 결과와 측정값은 실제로 돌려서 얻은 것입니다. 시간(ms)은 이 글을 쓴 컴퓨터에서 잰 값이라 여러분의 컴퓨터에서는 다를 수 있습니다. 하지만 몇 배 차이가 나는지, 어느 쪽이 빠른지는 같게 나옵니다. 그 비율이 이번 주에 보려는 것입니다.

이 주차를 읽는 법: 절마다 예제 코드 전체를 먼저 싣고, 실행한 뒤, 코드의 핵심 부분을 한 줄씩 뜯어봅니다. 그리고 절 끝에 “바꾸면 어떻게 될까” 실험이 있습니다. 실험은 결과를 먼저 예상하고 나서 돌려 보세요. 예상이 틀린 곳이 여러분이 오늘 새로 배우는 곳입니다.

1. 동적 계획법 입문: 피보나치 4단 진화

1.1 같은 문제를 네 번 풀기

동적 계획법(Dynamic Programming, DP) 을 설명하는 데 피보나치 수열만 한 예제가 없습니다. 피보나치 수열은 “앞의 두 수를 더해 다음 수를 만드는” 수열입니다.

F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, ...
F(n) = F(n-1) + F(n-2)

5주차 재귀에서 이 수열을 재귀 함수로 만들었고, F(45)를 계산하는 데 5초가 넘게 걸리는 것을 봤습니다. 그때는 “재귀는 느릴 수 있다”에서 끝냈는데, 오늘은 왜 느린지 정확히 세어 보고, 세 줄로 고칩니다. 같은 문제를 네 가지 방법으로 풀면서 DP가 무엇인지 체감해 봅시다.

examples/fib_dp.c:

/*
 * fib_dp.c - 동적 계획법 입문: 피보나치 4단 진화
 * 17주차: 고급 알고리즘과 최적화
 *
 * 같은 문제를 네 가지 방법으로 풀며 DP의 핵심을 체득합니다:
 *
 * 1. 순수 재귀     : O(2^n)  - 같은 계산을 수백만 번 반복!
 * 2. 메모이제이션  : O(n)    - "한 번 푼 건 적어두자" (하향식 DP)
 * 3. 테이블        : O(n)    - "작은 것부터 차곡차곡" (상향식 DP)
 * 4. 변수 2개      : O(n), 공간 O(1) - 상태 공간 최적화
 *
 * DP가 성립하는 두 조건:
 * - 겹치는 부분 문제: fib(50)은 fib(48)을 두 번 이상 만난다
 * - 최적 부분 구조: 큰 답이 작은 답들로 조립된다
 */
#include <stdio.h>
#include <string.h>
#include <time.h>

static long long call_count;

/* ---------- 1. 순수 재귀: 교과서의 함정 ---------- */
long long fib_naive(int n) {
    call_count++;
    if (n <= 1) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

/* ---------- 2. 메모이제이션 (하향식): 재귀 + 노트 ---------- */
static long long memo[100];
static int computed[100];

long long fib_memo(int n) {
    call_count++;
    if (n <= 1) return n;
    if (computed[n]) return memo[n];         /* 이미 풀었다! 즉시 반환 */

    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    computed[n] = 1;
    return memo[n];
}

/* ---------- 3. 테이블 (상향식): 작은 것부터 ---------- */
long long fib_table(int n) {
    long long dp[100];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];       /* 재귀 없음. 그냥 반복문 */
        call_count++;
    }
    return dp[n];
}

/* ---------- 4. 상태 공간 최적화: 어차피 직전 둘만 쓴다 ---------- */
long long fib_optimized(int n) {
    if (n <= 1) return n;
    long long prev = 0, cur = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + cur;
        prev = cur;
        cur = next;
        call_count++;
    }
    return cur;                              /* 배열 100칸 -> 변수 2개! */
}

double ms(clock_t a, clock_t b) {
    return (double)(b - a) * 1000.0 / CLOCKS_PER_SEC;
}

int main(void) {
    int n = 38;
    printf("fib(%d)를 네 가지 방법으로\n", n);
    printf("=====================================\n\n");

    clock_t t0 = clock();
    call_count = 0;
    long long r1 = fib_naive(n);
    long long naive_calls = call_count;
    clock_t t1 = clock();
    printf("1. 순수 재귀     : %lld (%8.1f ms, 호출 %10lld번!)\n",
           r1, ms(t0, t1), call_count);

    call_count = 0;
    memset(computed, 0, sizeof(computed));
    clock_t t2 = clock();
    long long r2 = fib_memo(n);
    clock_t t3 = clock();
    printf("2. 메모이제이션  : %lld (%8.3f ms, 호출 %10lld번)\n",
           r2, ms(t2, t3), call_count);

    call_count = 0;
    long long r3 = fib_table(n);
    printf("3. 테이블(상향식): %lld (          , 반복 %10lld번)\n",
           r3, call_count);

    call_count = 0;
    long long r4 = fib_optimized(n);
    printf("4. 변수 2개      : %lld (          , 반복 %10lld번, 공간 O(1))\n",
           r4, call_count);

    printf("\n=== 왜 이런 차이가? ===\n");
    printf("순수 재귀의 호출 트리를 보면:\n");
    printf("            fib(5)\n");
    printf("           /      \\\n");
    printf("      fib(4)      fib(3)   <- fib(3)이 여기서도\n");
    printf("      /    \\      /   \\\n");
    printf("  fib(3) fib(2) fib(2) fib(1)  <- 또 계산된다!\n");
    printf("같은 문제를 셀 수 없이 다시 푼다. n=%d이면 %lld번 호출!\n",
           n, naive_calls);

    printf("\n=== 하향식 vs 상향식, 뭘 쓸까? ===\n");
    printf("메모이제이션(하향식): 재귀 그대로 + 노트. 필요한 것만 계산.\n");
    printf("  -> 점화식이 복잡하거나 일부 상태만 쓸 때\n");
    printf("테이블(상향식): 반복문. 스택 오버플로우 없음, 캐시 친화.\n");
    printf("  -> 대부분의 경우 이쪽이 빠르고 안전 (기본값!)\n");

    printf("\nDP 3단계 레시피 (이번 주 내내 반복됩니다):\n");
    printf("1. 상태 정의   : dp[i] = \"i번째 피보나치 수\"\n");
    printf("2. 점화식     : dp[i] = dp[i-1] + dp[i-2]\n");
    printf("3. 기저 + 순서 : dp[0]=0, dp[1]=1부터 왼쪽에서 오른쪽\n");
    return 0;
}

코드가 길어 보이지만 함수 네 개와 그것을 차례로 부르는 main이 전부입니다. 먼저 실행해 봅시다.

$ ./build/fib_dp
fib(38)를 네 가지 방법으로
=====================================

1. 순수 재귀     : 39088169 (   183.0 ms, 호출  126491971번!)
2. 메모이제이션  : 39088169 (   0.001 ms, 호출         75번)
3. 테이블(상향식): 39088169 (          , 반복         37번)
4. 변수 2개      : 39088169 (          , 반복         37번, 공간 O(1))
...

재귀 vs 메모이제이션 vs 반복

재귀 vs 메모이제이션 vs 반복

그림은 글을 쓴 뒤 다시 돌린 결과입니다. 벤치마크라서 본문 표와 수치가 몇 % 다릅니다. 배속과 순서가 같은지를 보세요 — 절대값이 아니라 그게 이 측정이 말하려는 것입니다.

네 방법 모두 답은 39088169로 같습니다. 그런데 1억 2,649만 번 대 75번. 호출 횟수가 168만 배 차이 납니다. 시간으로는 183ms 대 0.001ms입니다.

1.2 왜 이런 차이가 나는가

fib_naive가 무엇을 하는지 작은 n으로 따라가 봅시다. fib(5)를 부르면 fib(4)와 fib(3)을 부르고, fib(4)는 다시 fib(3)과 fib(2)를 부릅니다. 호출 관계를 나무로 그리면 이렇습니다.

                    fib(5)
                  /        \
             fib(4)          fib(3)
            /      \        /      \
        fib(3)   fib(2)  fib(2)   fib(1)
       /     \    /   \   /   \
   fib(2) fib(1) f(1) f(0) f(1) f(0)
   /   \
 f(1) f(0)

세어 보면 fib(3)이 2번, fib(2)가 3번, fib(1)이 5번 계산됩니다. 그런데 fib(3)의 답은 언제 물어봐도 2입니다. 같은 질문에 같은 답을 내려고 같은 계산을 처음부터 다시 하는 것이죠. n이 커지면 이 중복이 기하급수로 불어납니다.

정확히 얼마나 불어나는지 재 봅시다. n을 2씩 늘리면서 호출 횟수와 시간을 찍는 작은 프로그램을 만들었습니다.

  n    fib(n)     호출 횟수   시간(ms)   직전 대비
 30     832040      2692537       5.8
 32    2178309      7049155      15.3   x2.65배
 34    5702887     18454929      31.6   x2.07배
 36   14930352     48315633      98.5   x3.12배
 38   39088169    126491971     207.8   x2.11배
 40  102334155    331160281     584.5   x2.81배

n이 2 커질 때마다 호출 횟수가 약 2.6배씩 늘어납니다. 시간도 그렇습니다(측정 오차가 있어 2~3배 사이를 오갑니다). n이 10 커지면 2.6⁵ ≈ 120배, 20 커지면 약 1만 4천 배입니다. 이런 증가를 지수적(exponential) 이라고 하고, 복잡도로는 O(2ⁿ) 이라고 씁니다(정확히는 약 1.618ⁿ인데, “n에 비례해 지수가 커진다”는 뜻으로 O(2ⁿ)이라 부릅니다).

재미있는 사실 하나. 호출 횟수는 답과 관계가 있습니다. fib(30)의 호출 횟수 2,692,537은 정확히 2 × F(31) − 1입니다. 5주차에서 봤던 그 규칙입니다. 답 자체가 지수적으로 커지는 수열이니, 답을 1씩 세듯 계산하는 순수 재귀도 지수적일 수밖에 없습니다.

그런데 생각해 보면 fib(3)의 답은 언제나 2입니다. 한 번 계산했으면 적어 두고 재사용하면 됩니다. 이 한 문장이 DP의 전부입니다.

DP가 성립하려면 두 조건이 필요합니다.

겹치는 부분 문제(overlapping subproblems): 같은 하위 문제를 여러 번 만난다. 위 그림에서 fib(3)이 두 번 나오는 것이 그것입니다.
최적 부분 구조(optimal substructure): 큰 문제의 답이 작은 문제의 답으로 조립된다. F(5) = F(4) + F(3)처럼요.

둘 다 필요합니다. 겹치지 않으면 적어 둘 이유가 없습니다. 병합 정렬은 배열을 반으로 나누지만 두 반쪽이 겹치지 않으니 DP가 아니라 분할 정복입니다(8절). 그리고 조립되지 않으면 애초에 나눌 수 없습니다.

1.3 메모이제이션: 재귀에 노트 세 줄 붙이기

메모이제이션(memoization, 하향식 top-down) 은 재귀를 그대로 두고 “노트”만 추가합니다. 낯선 단어인데, 메모(memo)에서 온 말입니다. “메모해 두기”라고 읽으면 됩니다.

static long long memo[100];      /* 노트: memo[n] = fib(n)의 답 */
static int computed[100];        /* memo[n]에 답이 적혀 있는가? */

long long fib_memo(int n) {
    call_count++;
    if (n <= 1) return n;
    if (computed[n]) return memo[n];         /* ① 이미 풀었다! 즉시 반환 */

    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);   /* ② 처음이면 계산해서 */
    computed[n] = 1;                                /* ③ 적어 둔다 */
    return memo[n];
}

원래 재귀 함수와 비교하면 딱 세 줄이 늘었습니다. ① 노트를 먼저 보고, 있으면 그 자리에서 돌려줍니다. ② 없으면 원래대로 계산하고, ③ 계산한 값을 노트에 적고 “적었다”고 표시합니다.

static 배열 두 개가 노트입니다. memo[n]에 답을 적고, computed[n]에 “이 칸은 적혀 있다”는 표시를 합니다. C에서 static 변수와 전역 변수는 초기값을 안 적으면 0으로 초기화됩니다(1주차 10절의 초기화 안 한 지역 변수 x와 다른 점입니다). 그래서 처음에는 모든 칸이 “안 적혀 있음”입니다.

이 세 줄이 정말 중복 계산을 막는지 눈으로 확인해 봅시다. fib_memo에 “지금 무엇을 하는지” 출력을 넣어 fib(5)를 불러 봤습니다.

fib(5) 호출 -> 처음이다. 계산 시작
  fib(4) 호출 -> 처음이다. 계산 시작
    fib(3) 호출 -> 처음이다. 계산 시작
      fib(2) 호출 -> 처음이다. 계산 시작
        fib(1) 호출 -> 기저, 1
        fib(0) 호출 -> 기저, 0
      fib(2) = 1 를 노트에 적음
      fib(1) 호출 -> 기저, 1
    fib(3) = 2 를 노트에 적음
    fib(2) 호출 -> 노트에 있음! 1
  fib(4) = 3 를 노트에 적음
  fib(3) 호출 -> 노트에 있음! 2
fib(5) = 5 를 노트에 적음

들여쓰기가 재귀의 깊이입니다. 앞의 호출 나무와 비교해 보세요. fib(4) 아래에서 fib(3)을 계산하고 노트에 적었기 때문에, fib(5)가 오른쪽 가지에서 fib(3)을 다시 물었을 때는 “노트에 있음! 2” 로 즉시 끝났습니다. 그 아래에 있던 fib(2), fib(1), fib(0) 호출은 아예 일어나지 않았습니다. 나무의 오른쪽 절반이 통째로 잘린 것이죠.

이제 호출 횟수 75번의 정체도 보입니다. fib(38)부터 fib(2)까지 37개의 값이 각각 딱 한 번만 “처음이다. 계산 시작”을 거치고, 그때마다 두 번 부르니 각각의 “노트에 있음” 또는 기저 호출이 하나씩 따라옵니다. 그래서 대략 2n번, 정확히는 2×38 − 1 = 75번입니다. 지수(O(2ⁿ))가 선형(O(n)) 이 됐습니다.

computed[] 배열이 따로 필요한 이유

“memo[n]이 0이 아니면 계산된 것”으로 판정하면 배열 하나로 되지 않을까요? 안 됩니다. 답이 진짜 0인 경우를 “아직 안 계산함”과 구분할 수 없기 때문입니다.

피보나치에서는 fib(0)이 기저 조건에서 바로 걸러지니 티가 안 납니다. 답이 0인 부분 문제가 많은 다른 문제로 실험해 봤습니다. “동전 {3, 7}로 금액 a를 만드는 방법의 수”는 3으로도 7로도 안 만들어지는 금액이 많아서 답이 0인 부분 문제가 많습니다.

computed[] 로 판정: 답 551927, 호출 189번
memo!=0  로 판정: 답 551927, 호출 223번
답이 0인 부분 문제: 1~100 중 12개 (이것들은 '없음'으로 오인되어 매번 다시 계산됨)

답은 같지만 호출이 늘었습니다. 답이 0인 12개 부분 문제가 “아직 안 풀었다”로 오인되어 물을 때마다 다시 계산됐기 때문입니다. 여기서는 34번 차이지만, 답이 0인 부분 문제가 큰 나무의 뿌리 쪽에 있으면 순수 재귀와 다를 바 없이 느려집니다. 그래서 “계산했는가”는 별도의 표시로 기록합니다. 답이 음수가 될 수 없는 문제라면 memo를 -1로 초기화해 “−1이면 안 계산함”으로 쓰는 방법도 흔합니다.

1.4 테이블: 재귀 없이 작은 것부터

테이블(tabulation, 상향식 bottom-up) 은 재귀를 버리고, 작은 문제부터 차례로 표를 채웁니다.

long long fib_table(int n) {
    long long dp[100];
    dp[0] = 0;                               /* 기저: 제일 작은 답을 미리 적고 */
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];       /* 앞의 두 칸을 보고 다음 칸을 채운다 */
    }
    return dp[n];
}

dp는 DP에서 관습적으로 쓰는 배열 이름입니다. dp[i]에 “i번째 피보나치 수”를 적어 둔다고 정하고, 왼쪽에서 오른쪽으로 채웁니다.

i    : 0  1  2  3  4  5  6  7  8
dp[i]: 0  1  1  2  3  5  8 13 21
                  ↑
         dp[3] = dp[2] + dp[1] = 1 + 1

메모이제이션이 “필요할 때 계산해서 적는” 방식이라면, 테이블은 “어차피 다 필요하니 순서대로 미리 채우는” 방식입니다. dp[i]를 채우는 시점에 dp[i-1]과 dp[i-2]는 반드시 이미 채워져 있습니다. 왼쪽부터 채웠으니까요. 이 “계산 순서”를 우리가 직접 정하는 것이 테이블 방식의 핵심이자, 어려운 점입니다.

어느 쪽을 쓸까요?

	메모이제이션 (하향식)	테이블 (상향식)
형태	재귀 + 노트	반복문
계산 범위	필요한 상태만	모든 상태
스택	재귀 깊이만큼 쌓임 (5주차의 스택 오버플로우 위험)	없음
캐시	불리 (여기저기 점프)	유리 (순차 접근, 10주차 캐시 실험)
구현 난이도	점화식만 알면 쉬움	계산 순서를 설계해야 함

대부분의 경우 상향식이 기본값입니다. 빠르고 안전하니까요. 하향식은 상태 공간이 넓은데 실제로 쓰는 상태는 일부일 때, 또는 계산 순서를 정하기 까다로울 때 유리합니다.

1.5 상태 공간 최적화: 배열 100칸에서 변수 2개로

네 번째 버전을 보세요.

long long fib_optimized(int n) {
    if (n <= 1) return n;
    long long prev = 0, cur = 1;             /* dp[i-2], dp[i-1] 역할 */
    for (int i = 2; i <= n; i++) {
        long long next = prev + cur;         /* dp[i] */
        prev = cur;                          /* 한 칸씩 밀어서 */
        cur = next;                          /* 다음 반복을 준비 */
    }
    return cur;
}

점화식 dp[i] = dp[i-1] + dp[i-2]는 직전 두 칸만 봅니다. dp[0]부터 dp[i-3]까지는 한 번 쓰고 나면 다시 볼 일이 없습니다. 그렇다면 배열 전체를 들고 있을 이유가 없습니다. 변수 두 개를 한 칸씩 밀면서 쓰면 됩니다.

반복 i=2: prev=0, cur=1  -> next=1   -> prev=1, cur=1
반복 i=3: prev=1, cur=1  -> next=2   -> prev=1, cur=2
반복 i=4: prev=1, cur=2  -> next=3   -> prev=2, cur=3
반복 i=5: prev=2, cur=3  -> next=5   -> prev=3, cur=5

메모리가 O(n)에서 O(1) 이 됐습니다. 이것을 상태 공간 최적화라고 하고, 점화식이 “직전 몇 개”만 참조할 때 항상 쓸 수 있습니다. 10절 프로젝트 3에서 배낭 문제의 2차원 표를 1차원으로 줄이는 것도 같은 기법입니다.

1.6 DP 3단계 레시피

모든 DP 문제는 같은 순서로 접근합니다. 이번 주 내내 이 틀을 반복할 테니 지금 외워 두세요.

① 상태 정의 → ② 점화식 → ③ 기저와 계산 순서

피보나치로 적용하면 이렇습니다.

상태 정의: dp[i] = i번째 피보나치 수. “표의 한 칸에 무엇을 적을 것인가”를 정하는 단계입니다.
점화식: dp[i] = dp[i-1] + dp[i-2]. “한 칸을 이미 채운 다른 칸들로 어떻게 만드는가”입니다. 점화식(漸化式)은 “차례로 변해 가는 식”이라는 뜻입니다.
기저와 순서: dp[0]=0, dp[1]=1을 미리 적고, 왼쪽에서 오른쪽으로 채웁니다. 점화식이 참조하는 칸이 먼저 채워지는 순서여야 합니다.

셋 중 가장 어려운 것은 ① 상태 정의입니다. “무엇을 표에 적을 것인가”를 잘못 정하면 점화식이 세워지지 않습니다. DP 문제를 못 풀 때는 대개 여기서 막힌 것이니, 점화식을 붙잡고 씨름하기 전에 상태 정의부터 다시 보세요. 다음 절의 배낭 문제가 좋은 연습입니다. 상태를 dp[i][w]라는 2차원으로 잡는 순간 문제가 풀립니다.

실험: 바꾸면 어떻게 될까

fib_naive의 n을 45로 바꿔 보세요. 38에서 183ms였고 n이 2 커질 때마다 약 2.6배씩 늘었으니, 45는 2.6^3.5 ≈ 28배, 약 5초로 예상됩니다. 5주차에서 잰 5.34초와 맞아떨어지는지 확인해 보세요. 그리고 n=50이면 얼마나 걸릴지 계산해 보세요. 호출 횟수 2×F(51)−1 ≈ 407억 번은 n=38의 약 320배이니 1분쯤입니다. 실제로 돌려도 되지만 커피 한 잔은 준비하세요.
fib_memo에서 computed[n] = 1; 한 줄을 지우고 실행해 보세요. 노트에 적기는 하는데 “적었다”는 표시를 안 하니, 노트를 한 번도 읽지 않게 됩니다. 호출 횟수가 순수 재귀와 똑같은 1억 2천만으로 돌아갑니다.
n을 93으로 바꿔 보세요. F(93)은 12,200,160,415,121,876,738로 long long의 최댓값(약 922경)을 넘습니다. 2주차에서 배운 오버플로가 일어나 음수가 찍힙니다. DP로 빠르게 계산할 수 있게 되면, 그다음 벽은 자료형의 크기입니다. 8절에서 이 벽을 나머지 연산으로 넘습니다.

2. 0/1 배낭: DP의 대표 선수

2.1 문제

“배낭 용량은 15kg. 물건마다 무게와 가치가 있다. 가치 합이 최대가 되게 담아라. 단, 물건은 쪼갤 수 없다.”

이름의 “0/1″이 바로 그 뜻입니다. 각 물건은 담거나(1) 안 담거나(0) 둘 중 하나입니다. 텐트를 반만 담을 수는 없죠.

직관적으로는 “kg당 가치가 높은 것부터 담으면 되지 않나?” 싶습니다. 9절에서 배울 탐욕법입니다. 그런데 이게 틀릴 수 있습니다. 왜 틀리는지가 이 예제의 핵심이고, 어떻게 하면 절대 안 틀리는지가 DP의 답입니다.

examples/knapsack.c:

/*
 * knapsack.c - 0/1 배낭 문제: DP의 대표 선수
 * 17주차: 고급 알고리즘과 최적화
 *
 * "배낭 용량은 15kg. 물건마다 무게와 가치가 있다.
 *  가치 합이 최대가 되게 담아라. 단, 물건은 쪼갤 수 없다!"
 *
 * 탐욕(가치/무게 비율 순)은 실패할 수 있습니다 - 반례 포함.
 * 정답은 DP:
 *   dp[i][w] = 앞 i개 물건만 고려, 용량 w일 때 최대 가치
 *   물건 i를 (1) 안 담거나: dp[i-1][w]
 *            (2) 담거나  : dp[i-1][w - 무게i] + 가치i
 *   둘 중 큰 쪽!
 *
 * 역추적으로 "뭘 담았는지"까지 복원합니다.
 */
#include <stdio.h>
#include <string.h>

#define MAX_ITEMS 16
#define MAX_CAP 64

typedef struct {
    const char *name;
    int weight;
    int value;
} Item;

int max2(int a, int b) { return a > b ? a : b; }

/* 0/1 배낭 DP. 반환 = 최대 가치, picked[]에 선택 여부 */
int knapsack(const Item items[], int n, int cap, int picked[]) {
    static int dp[MAX_ITEMS + 1][MAX_CAP + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i - 1][w];                     /* 안 담는 경우 */
            if (items[i - 1].weight <= w) {              /* 담을 수 있으면 */
                dp[i][w] = max2(dp[i][w],
                                dp[i - 1][w - items[i - 1].weight]
                                + items[i - 1].value);
            }
        }
    }

    /* 역추적: 표를 거꾸로 걸으며 "담았는지" 판정 */
    int w = cap;
    for (int i = n; i >= 1; i--) {
        if (dp[i][w] != dp[i - 1][w]) {  /* 값이 달라졌다 = i를 담았다! */
            picked[i - 1] = 1;
            w -= items[i - 1].weight;
        } else {
            picked[i - 1] = 0;
        }
    }
    return dp[n][cap];
}

/* 비교용: 가치/무게 비율 탐욕 (0/1에서는 틀릴 수 있다!) */
int greedy_ratio(const Item items[], int n, int cap, int picked[]) {
    int order[MAX_ITEMS];
    for (int i = 0; i < n; i++) { order[i] = i; picked[i] = 0; }

    /* 비율 내림차순 정렬 (선택 정렬로 충분) */
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            double ri = (double)items[order[i]].value / items[order[i]].weight;
            double rj = (double)items[order[j]].value / items[order[j]].weight;
            if (rj > ri) { int t = order[i]; order[i] = order[j]; order[j] = t; }
        }
    }

    int total = 0, remaining = cap;
    for (int k = 0; k < n; k++) {
        int i = order[k];
        if (items[i].weight <= remaining) {
            picked[i] = 1;
            remaining -= items[i].weight;
            total += items[i].value;
        }
    }
    return total;
}

void show_choice(const Item items[], int n, const int picked[]) {
    int tw = 0;
    printf("      담은 것:");
    for (int i = 0; i < n; i++) {
        if (picked[i]) {
            printf(" %s", items[i].name);
            tw += items[i].weight;
        }
    }
    printf(" (총 %dkg)\n", tw);
}

int main(void) {
    /* 캠핑 배낭 시나리오 */
    Item items[] = {
        {"텐트",   8, 50},
        {"버너",   3, 30},
        {"코펠",   2, 20},
        {"침낭",   5, 40},
        {"랜턴",   1, 15},
        {"의자",   4, 25},
    };
    int n = 6, cap = 15;
    int picked[MAX_ITEMS];

    printf("=== 캠핑 배낭 문제 (용량 %dkg) ===\n", cap);
    printf("  %-6s %6s %6s %8s\n", "물건", "무게", "가치", "가치/kg");
    for (int i = 0; i < n; i++) {
        printf("  %-6s %5dkg %6d %8.1f\n",
               items[i].name, items[i].weight, items[i].value,
               (double)items[i].value / items[i].weight);
    }

    int g = greedy_ratio(items, n, cap, picked);
    printf("\n[탐욕: 가치/kg 높은 순으로 담기]\n      최대 가치: %d\n", g);
    show_choice(items, n, picked);

    int d = knapsack(items, n, cap, picked);
    printf("\n[DP: 모든 조합을 표로 계산]\n      최대 가치: %d\n", d);
    show_choice(items, n, picked);

    printf("\n%s\n", (d > g)
        ? ">>> 탐욕이 손해를 봤다! 비율 좋은 걸 덜컥 담으면 큰 그림을 놓친다."
        : ">>> 이번엔 같지만, 탐욕은 '보장'이 없다.");

    /* 탐욕이 확실히 지는 반례 */
    printf("\n=== 탐욕 격파 반례 (용량 10) ===\n");
    Item trap[] = {
        {"A", 6, 60},        /* 비율 10.0 - 탐욕이 덥석 문다 */
        {"B", 5, 45},        /* 비율 9.0 */
        {"C", 5, 45},        /* 비율 9.0 */
    };
    int tp[MAX_ITEMS];

    int g2 = greedy_ratio(trap, 3, 10, tp);
    printf("탐욕: A(비율 최고!)를 담으면 남은 4로 B/C를 못 담는다 -> %d\n", g2);
    int d2 = knapsack(trap, 3, 10, tp);
    printf("DP  : A를 포기하고 B+C -> %d  (탐욕보다 %d 이득!)\n", d2, d2 - g2);

    printf("\n정리:\n");
    printf("1. 상태: dp[i][w] = 앞 i개, 용량 w의 최대 가치\n");
    printf("2. 점화식: max(안 담기, 담기) - 딱 두 갈래\n");
    printf("3. 역추적: 표를 거꾸로 걸으면 '무엇을'까지 나온다\n");
    printf("4. 쪼갤 수 있는 배낭(분수 배낭)은 탐욕이 정답 - greedy.c에서!\n");
    return 0;
}

$ ./build/knapsack
=== 캠핑 배낭 문제 (용량 15kg) ===
  물건 무게 가치 가치/kg
  텐트     8kg     50      6.2
  버너     3kg     30     10.0
  코펠     2kg     20     10.0
  침낭     5kg     40      8.0
  랜턴     1kg     15     15.0
  의자     4kg     25      6.2

[탐욕: 가치/kg 높은 순으로 담기]
      최대 가치: 130
      담은 것: 버너 코펠 침낭 랜턴 의자 (총 15kg)

[DP: 모든 조합을 표로 계산]
      최대 가치: 130
      담은 것: 버너 코펠 침낭 랜턴 의자 (총 15kg)

>>> 이번엔 같지만, 탐욕은 '보장'이 없다.

=== 탐욕 격파 반례 (용량 10) ===
탐욕: A(비율 최고!)를 담으면 남은 4로 B/C를 못 담는다 -> 60
DP  : A를 포기하고 B+C -> 90  (탐욕보다 30 이득!)
...

배낭 문제

배낭 문제

캠핑 배낭에서는 탐욕과 DP의 답이 같습니다. 그런데 아래의 세 물건 반례에서는 탐욕이 60, DP가 90입니다. 같은 알고리즘인데 입력에 따라 맞기도 틀리기도 하는 것, 이것이 탐욕법의 위험입니다.

(출력의 표 머리글 “물건 무게 가치”가 값 줄과 어긋나 보이는 것은 8주차에서 본 그 문제입니다. %-6s가 바이트 수로 폭을 세는데 한글은 한 글자가 3바이트라서 그렇습니다. 예제의 본질이 아니라 그대로 두었습니다.)

2.2 상태 정의: 표의 한 칸에 무엇을 적을까

1절의 레시피 첫 단계입니다. 피보나치는 dp[i] 하나였는데, 배낭은 두 가지가 변합니다. “어떤 물건까지 고려했는가”와 “용량이 얼마 남았는가”. 그래서 표가 2차원입니다.

dp[i][w] = 앞에서부터 i개의 물건만 고려하고, 배낭 용량이 w일 때 얻을 수 있는 최대 가치

이 정의를 소리 내어 읽어 보세요. dp[3][5]는 “물건 1, 2, 3만 놓고, 용량 5짜리 배낭에 담을 수 있는 최대 가치”입니다. 우리가 최종적으로 알고 싶은 것은 dp[n][cap], “모든 물건을 놓고 용량 15일 때”입니다.

2.3 점화식: 담거나, 말거나

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i - 1][w];                     /* ① 안 담는 경우 */
            if (items[i - 1].weight <= w) {              /* ② 담을 수 있으면 */
                dp[i][w] = max2(dp[i][w],
                                dp[i - 1][w - items[i - 1].weight]   /* ③ 담는 경우 */
                                + items[i - 1].value);
            }
        }
    }

dp[i][w]를 채울 때 물건 i에 대해 할 수 있는 일은 딱 두 가지입니다.

① 안 담기: 물건 i가 없는 셈 치면, 답은 “앞 i−1개만 고려한 답” 그대로입니다. dp[i-1][w].
③ 담기: 물건 i를 담으려면 그 무게만큼 자리를 비워 둬야 합니다. “앞 i−1개를 용량 w − 무게ᵢ에 최대로 채운 값”에 물건 i의 가치를 더합니다. dp[i-1][w - 무게ᵢ] + 가치ᵢ.
둘 중 큰 쪽이 답입니다. 단, ②처럼 물건이 용량보다 무거우면 담는 선택지 자체가 없습니다.

items[i - 1]인 이유는 배열이 0번부터 시작하기 때문입니다. dp의 i는 “i개까지”라는 개수이고, 그 i번째 물건은 배열에서 items[i-1]입니다. 이런 “1 차이”는 DP 코드에서 가장 흔한 실수 지점이라 항상 확인하세요.

“담기” 쪽의 w − 무게ᵢ가 핵심입니다. “이 물건을 넣을 자리를 확보한 상태에서 앞 물건들이 최대로 채운 가치”를 가져오는 것이죠. 그리고 그 값은 이미 표에 계산되어 있습니다. 작은 문제의 답으로 큰 문제를 조립한다, 최적 부분 구조가 바로 이겁니다.

2.4 표를 직접 채워 보기

말로만 들으면 잡히지 않으니, 손으로 채울 수 있는 크기로 줄여서 표를 만들어 봅시다. 물건 3개, 용량 5입니다.

물건	무게	가치
물건1	2	3
물건2	3	4
물건3	4	5

같은 코드로 이 입력을 돌려 표 전체를 찍었습니다.

        w=0  1  2  3  4  5
i=0(없음)  0  0  0  0  0  0
i=1 물건1(2kg,3)  0  0  3  3  3  3
i=2 물건2(3kg,4)  0  0  3  4  4  7
i=3 물건3(4kg,5)  0  0  3  4  5  7

dp[3][5] = 7

몇 칸을 직접 따라가 봅시다.

i=0 행: 물건이 하나도 없으니 어떤 용량이든 가치 0. 이것이 기저입니다. memset(dp, 0, ...)이 이 행을 채웁니다.
dp[1][1] (물건1만, 용량 1): 물건1은 2kg이라 못 담습니다. ①만 가능 → dp[0][1] = 0.
dp[1][2] (물건1만, 용량 2): 담을 수 있습니다. ① 안 담기 = dp[0][2] = 0, ③ 담기 = dp[0][0] + 3 = 3. 큰 쪽 3.
dp[2][5] (물건1·2, 용량 5): ① 안 담기 = dp[1][5] = 3. ③ 물건2(3kg)를 담으면 남는 용량 2에 앞 물건들이 채운 최대 = dp[1][2] = 3, 여기에 4를 더해 7. 큰 쪽 7. “3kg 물건을 넣을 자리를 비워 두고 나머지 2kg에 물건1을 넣는” 조합을 표가 찾아낸 것입니다.
dp[3][5] (전부, 용량 5): ① = dp[2][5] = 7. ③ 물건3(4kg)을 담으면 남는 1kg에 채울 수 있는 최대 = dp[2][1] = 0, 더해서 5. 큰 쪽 7. 물건3은 안 담는 게 낫다는 뜻입니다.

표는 위에서 아래로, 왼쪽에서 오른쪽으로 채웁니다. dp[i][w]를 계산할 때 참조하는 dp[i-1][w]와 dp[i-1][w-무게]는 모두 윗줄에 있어서 이미 채워져 있습니다. 이것이 레시피 ③ “계산 순서”입니다.

행이 6개(i=0~6), 열이 16개(w=0~15)인 캠핑 배낭에서는 이 계산을 96번 합니다. 물건 n개, 용량 W면 O(n × W) 입니다.

2.5 역추적: “얼마”에서 “무엇을”로

DP 표는 최댓값 7을 알려 주지만, 우리가 정말 알고 싶은 것은 “그래서 뭘 담아야 하나?” 입니다. 표를 거꾸로 걸으면 나옵니다.

    int w = cap;
    for (int i = n; i >= 1; i--) {
        if (dp[i][w] != dp[i - 1][w]) {  /* 값이 달라졌다 = i를 담았다! */
            picked[i - 1] = 1;
            w -= items[i - 1].weight;    /* 담았으니 남은 용량이 줄어든다 */
        } else {
            picked[i - 1] = 0;
        }
    }

논리가 우아합니다. dp[i][w]와 dp[i-1][w]가 같다면, 물건 i가 있으나 없으나 결과가 같았다는 뜻이니 안 담은 것입니다. 다르다면 물건 i 덕분에 값이 올라간 것이니 담은 것이고, 그렇다면 남은 용량은 그 무게만큼 줄어듭니다. 위의 작은 표에서 실제로 걸어 봅시다.

역추적: dp[3][5]=7 == dp[2][5]=7 -> 물건3(4kg,5) 안 담음
        dp[2][5]=7 != dp[1][5]=3 -> 물건2(3kg,4) 담음, 남은 용량 2
        dp[1][2]=3 != dp[0][2]=0 -> 물건1(2kg,3) 담음, 남은 용량 0

마지막 행에서 출발해서, 담은 물건을 만날 때마다 왼쪽으로 그 무게만큼 이동하며 위로 올라갑니다. 결과는 물건1과 물건2, 가치 3 + 4 = 7. 표의 값과 일치합니다.

이 역추적 패턴은 DP 문제 전반에 적용됩니다. 표만 있으면 구성을 복원할 수 있으니, 선택을 따로 기록할 필요조차 없습니다. 4절의 동전 문제에서는 반대로 choice[] 배열에 선택을 명시적으로 기록하는 방식을 봅니다. 둘 다 흔히 씁니다.

2.6 탐욕이 지는 이유

반례를 뜯어봅시다.

용량 10:  A(6kg, 60, 비율 10.0)  B(5kg, 45, 비율 9.0)  C(5kg, 45, 비율 9.0)

탐욕: 비율 1등 A를 담는다 (60). 남은 용량 4kg으로는 B도 C도 못 담는다. → 60
DP  : A를 포기하고 B + C = 10kg 꽉 참 → 90

탐욕이 지는 이유가 명확합니다. “지금의 최선”이 “미래의 선택지”를 망가뜨렸습니다. A를 담는 순간 4kg이라는 어중간한 공간이 남아 버려진 것이죠. 탐욕은 한 번 담은 것을 되돌리지 않으니 이 손해를 만회할 방법이 없습니다.

DP는 왜 안 틀릴까요? dp[3][10]을 계산할 때 “A를 담는 경우”와 “안 담는 경우”를 둘 다 계산하고 큰 쪽을 고르기 때문입니다. 탐욕이 한 갈래만 가 보는 반면, DP는 모든 갈래를 표 한 장에 압축해서 전부 비교합니다. 그래서 느리지만(O(n×W)) 틀리지 않습니다.

재미있게도 쪼갤 수 있다면 탐욕이 정답이 됩니다(분수 배낭). 9절에서 그 이유를 봅니다. 같은 문제에서 제약 하나가 바뀌면 최적 알고리즘도 바뀝니다.

실험: 바꾸면 어떻게 될까

캠핑 배낭의 용량을 15에서 12로 바꿔 보세요. 탐욕과 DP의 답이 달라지는지 확인하세요. 탐욕은 비율 순서(랜턴, 버너, 코펠, 침낭, …)로 담다가 자리가 안 맞으면 건너뜁니다.
텐트의 가치를 50에서 100으로 바꿔 보세요. 비율이 12.5로 1등이 되어 탐욕이 텐트를 먼저 담습니다. 남은 7kg에 무엇을 담을지, DP가 다른 답을 내는지 보세요.
MAX_CAP을 10으로 줄이고 캠핑 배낭(용량 15)을 그대로 돌려 보세요. dp[i][15]는 배열 밖입니다. 4주차에서 배운 대로 컴파일러는 아무 말도 하지 않고, 실행하면 엉뚱한 값이 나오거나 죽습니다. 4.6절에서 이 실수의 실제 사례를 봅니다.

3. LCS: diff의 심장

3.1 최장 공통 부분 수열

git diff를 쓰면 두 파일에서 바뀐 줄만 +와 -로 보여 줍니다. 컴퓨터는 어떻게 “바뀌지 않은 줄”을 찾아낼까요? 답은 이 절의 주제, LCS(Longest Common Subsequence, 최장 공통 부분 수열) 입니다.

부분 수열(subsequence)은 원래 순서를 지키면서 띄엄띄엄 골라낸 것입니다. 연속일 필요는 없습니다. 연속이어야 하는 것은 부분 문자열(substring)이고, 다른 개념입니다.

A = ABCBDAB
B = BDCABA
LCS = BCBA (길이 4)

BCBA가 A에서는 AB?C?B?A? 순서로, B에서는 BDCABA 순서로 나타납니다. 띄엄띄엄이지만 순서는 지켜졌죠.

이 문제는 16주차 편집 거리와 쌍둥이입니다. 표의 모양이 같고 점화식만 다릅니다.

examples/lcs.c:

/*
 * lcs.c - 최장 공통 부분 수열 (LCS): diff의 심장
 * 17주차: 고급 알고리즘과 최적화
 *
 * 두 문자열에서 "순서를 유지하며" 공통으로 뽑을 수 있는
 * 가장 긴 수열. (연속일 필요는 없다!)
 *
 *   ABCBDAB / BDCABA 의 LCS = BCBA (길이 4)
 *
 * 점화식 (지난주 편집 거리의 쌍둥이):
 *   같은 문자면: dp[i][j] = dp[i-1][j-1] + 1   (LCS에 편입!)
 *   다르면    : max(dp[i-1][j], dp[i][j-1])   (한쪽을 버린 것 중 최선)
 *
 * git diff가 "공통 부분(LCS)은 놔두고 나머지를 +/-"로 보여주는
 * 원리가 바로 이것입니다. 미니 diff까지 만들어 봅니다.
 */
#include <stdio.h>
#include <string.h>

#define MAX_LEN 64

int max2(int a, int b) { return a > b ? a : b; }

int lcs_table(const char *a, const char *b,
              int dp[MAX_LEN][MAX_LEN]) {
    int la = (int)strlen(a), lb = (int)strlen(b);

    for (int i = 0; i <= la; i++) dp[i][0] = 0;
    for (int j = 0; j <= lb; j++) dp[0][j] = 0;

    for (int i = 1; i <= la; i++) {
        for (int j = 1; j <= lb; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max2(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[la][lb];
}

/* 역추적으로 LCS 문자열 복원 */
void lcs_string(const char *a, const char *b,
                int dp[MAX_LEN][MAX_LEN], char *out) {
    int i = (int)strlen(a), j = (int)strlen(b);
    int len = dp[i][j];
    out[len] = '\0';

    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            out[--len] = a[i - 1];       /* 공통 문자: LCS의 일부 */
            i--; j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;                         /* 위쪽이 크다: a쪽 문자 버림 */
        } else {
            j--;
        }
    }
}

/* ---------- 미니 diff: 줄 단위 LCS ---------- */
void mini_diff(const char *old_lines[], int n_old,
               const char *new_lines[], int n_new) {
    static int dp[MAX_LEN][MAX_LEN];

    for (int i = 0; i <= n_old; i++) dp[i][0] = 0;
    for (int j = 0; j <= n_new; j++) dp[0][j] = 0;
    for (int i = 1; i <= n_old; i++) {
        for (int j = 1; j <= n_new; j++) {
            if (strcmp(old_lines[i - 1], new_lines[j - 1]) == 0) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max2(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    /* 역추적하며 diff 출력 (재귀로 순서 복원) */
    /* 스택 대신 간단히: 결과를 역순으로 모아서 뒤집어 출력 */
    char ops[2 * MAX_LEN];
    int line_a[2 * MAX_LEN], count = 0;
    int i = n_old, j = n_new;

    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 &&
            strcmp(old_lines[i - 1], new_lines[j - 1]) == 0) {
            ops[count] = ' '; line_a[count++] = i - 1;   /* 공통 */
            i--; j--;
        } else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
            ops[count] = '+'; line_a[count++] = j - 1;   /* 추가됨 */
            j--;
        } else {
            ops[count] = '-'; line_a[count++] = i - 1;   /* 삭제됨 */
            i--;
        }
    }

    for (int k = count - 1; k >= 0; k--) {
        if (ops[k] == ' ')      printf("    %s\n", old_lines[line_a[k]]);
        else if (ops[k] == '-') printf("  - %s\n", old_lines[line_a[k]]);
        else                    printf("  + %s\n", new_lines[line_a[k]]);
    }
}

int main(void) {
    static int dp[MAX_LEN][MAX_LEN];

    printf("=== LCS 기본 ===\n");
    const char *a = "ABCBDAB";
    const char *b = "BDCABA";
    int len = lcs_table(a, b, dp);

    char result[MAX_LEN];
    lcs_string(a, b, dp, result);
    printf("A = %s\nB = %s\n", a, b);
    printf("LCS = \"%s\" (길이 %d)\n", result, len);

    /* DP 표 출력 */
    printf("\nDP 표 (행=A, 열=B):\n      ");
    for (int j = 0; b[j]; j++) printf("%2c ", b[j]);
    printf("\n");
    for (int i = 0; i <= (int)strlen(a); i++) {
        if (i == 0) printf("   ");
        else        printf(" %c ", a[i - 1]);
        for (int j = 0; j <= (int)strlen(b); j++) printf("%2d ", dp[i][j]);
        printf("\n");
    }

    printf("\n=== 응용: DNA 유사도 ===\n");
    const char *dna1 = "ACCGGTCGAGTG";
    const char *dna2 = "GTCGTTCGGAATGCC";
    len = lcs_table(dna1, dna2, dp);
    lcs_string(dna1, dna2, dp, result);
    printf("%s vs %s\n", dna1, dna2);
    printf("공통 서열: %s (길이 %d)\n", result, len);

    printf("\n=== 미니 diff (git diff의 원리!) ===\n");
    const char *old_code[] = {
        "#include <stdio.h>",
        "int main(void) {",
        "    printf(\"hello\");",
        "    return 0;",
        "}",
    };
    const char *new_code[] = {
        "#include <stdio.h>",
        "#include <stdlib.h>",
        "int main(void) {",
        "    printf(\"hello, world\");",
        "    return 0;",
        "}",
    };
    printf("변경 전 5줄 -> 변경 후 6줄:\n\n");
    mini_diff(old_code, 5, new_code, 6);

    printf("\n(공통 줄(LCS)은 그대로, 아닌 것만 +/- : diff의 정체!)\n");

    printf("\n정리:\n");
    printf("1. 편집 거리와 표는 같고 점화식만 다르다 (min+1 vs max, +1)\n");
    printf("2. 역추적 = 표를 거꾸로 걷기. '답'뿐 아니라 '구성'까지\n");
    printf("3. 응용: diff/git, DNA 정렬, 표절 검사, 자동 병합\n");
    return 0;
}

$ ./build/lcs
=== LCS 기본 ===
A = ABCBDAB
B = BDCABA
LCS = "BCBA" (길이 4)

DP 표 (행=A, 열=B):
       B  D  C  A  B  A
    0  0  0  0  0  0  0
 A  0  0  0  0  1  1  1
 B  0  1  1  1  1  2  2
 C  0  1  1  2  2  2  2
 B  0  1  1  2  2  3  3
 D  0  1  2  2  2  3  3
 A  0  1  2  2  3  3  4
 B  0  1  2  2  3  4  4

=== 응용: DNA 유사도 ===
ACCGGTCGAGTG vs GTCGTTCGGAATGCC
공통 서열: CGTCGATG (길이 8)

=== 미니 diff (git diff의 원리!) ===
변경 전 5줄 -> 변경 후 6줄:

    #include <stdio.h>
  + #include <stdlib.h>
    int main(void) {
  -     printf("hello");
  +     printf("hello, world");
        return 0;
    }
...

3.2 표 읽기: 한 칸이 뜻하는 것

레시피대로 갑시다.

상태: dp[i][j] = A의 앞 i글자와 B의 앞 j글자의 LCS 길이
점화식: 아래 두 갈래
기저: dp[0][*] = dp[*][0] = 0. 한쪽이 빈 문자열이면 공통 부분이 없습니다.

            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;         /* 공통 문자 발견! */
            } else {
                dp[i][j] = max2(dp[i - 1][j], dp[i][j - 1]);  /* 한쪽 버리기 */
            }

마지막 글자가 같으면: 그 글자는 반드시 LCS에 들어갑니다. 두 문자열에서 그 글자를 하나씩 떼어 낸 문제(dp[i-1][j-1], 표에서 대각선 위)의 답에 1을 더합니다.
다르면: 두 글자 중 적어도 하나는 LCS에 못 들어갑니다. A의 마지막을 버린 경우(dp[i-1][j], 위)와 B의 마지막을 버린 경우(dp[i][j-1], 왼쪽) 중 더 좋은 쪽을 고릅니다.

출력된 표에서 몇 칸을 확인해 봅시다. 행이 A(ABCBDAB), 열이 B(BDCABA)입니다.

A행 B열 (dp[1][1]): A ≠ B. 위(dp[0][1]=0)와 왼쪽(dp[1][0]=0) 중 최대 → 0.
A행 A열 (dp[1][4]): A = A! 대각선 위 dp[0][3]=0에 1을 더해 → 1. 그 오른쪽 칸들도 1입니다. “A”와 “BDCA…”, 공통은 A 하나뿐이니까요.
B행 B열 (dp[2][1]): B = B. 대각선 위 dp[1][0]=0 + 1 → 1.
C행 C열 (dp[3][3]): C = C. 대각선 위 dp[2][2]=1 + 1 → 2. “ABC”와 “BDC”의 공통은 “BC”입니다.
오른쪽 아래 (dp[7][6]): B ≠ A. 위 dp[6][6]=4와 왼쪽 dp[7][5]=4의 최대 → 4. 최종 답입니다.

표의 어떤 칸이든 위, 왼쪽, 대각선 위 세 칸만 보고 채워집니다. 그래서 왼쪽 위에서 오른쪽 아래로 채우면 항상 필요한 칸이 먼저 채워져 있습니다.

3.3 편집 거리와 나란히 놓기

16주차 편집 거리와 비교해 봅시다.

	편집 거리	LCS
같을 때	`dp[i-1][j-1]` (비용 0)	`dp[i-1][j-1] + 1` (길이 +1)
다를 때	`1 + min(대각, 위, 왼쪽)`	`max(위, 왼쪽)`
목표	최소화	최대화
기저	`dp[i][0] = i` (i글자 지우기)	`dp[i][0] = 0`

구조가 완전히 같고 min/max와 +1의 위치만 다릅니다. DP를 여러 문제에 적용하다 보면 이런 패턴의 재사용이 보이기 시작합니다. 표를 채우는 방식은 같고 점화식만 문제에 맞게 바꾸는 것이죠. 사실 편집 거리, LCS, 그리고 DNA 서열 정렬은 모두 같은 틀의 변형입니다.

3.4 역추적으로 LCS 문자열 복원하기

    int i = (int)strlen(a), j = (int)strlen(b);
    int len = dp[i][j];
    out[len] = '\0';                     /* 결과 길이를 알고 있으니 끝을 먼저 찍는다 */

    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            out[--len] = a[i - 1];       /* 공통 문자: LCS의 일부. 뒤에서부터 채운다 */
            i--; j--;                    /* 대각선 위로 */
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;                         /* 위쪽이 크거나 같다: 위로 */
        } else {
            j--;                         /* 왼쪽으로 */
        }
    }

배낭과 같은 발상입니다. 오른쪽 아래에서 출발해서, 표를 채울 때의 판단을 거꾸로 따라갑니다. 글자가 같으면 그 글자를 결과에 넣고 대각선으로, 다르면 값이 컸던 쪽으로 이동합니다.

결과를 out[--len]처럼 뒤에서부터 채우는 점을 보세요. 역추적은 문자열의 끝에서 시작하므로 LCS의 마지막 글자를 먼저 만납니다. 배열의 끝 칸부터 거꾸로 채우면 뒤집을 필요가 없습니다. 4주차 문자열 뒤집기에서 본 것과 같은 요령입니다.

3.5 미니 diff: git이 하는 일

이 예제의 하이라이트는 줄 단위 LCS로 만든 diff입니다. 문자 대신 줄을 원소로 삼습니다. a[i-1] == b[j-1] 자리에 strcmp(old_lines[i-1], new_lines[j-1]) == 0이 들어간 것 말고는 표를 채우는 코드가 똑같습니다.

    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 &&
            strcmp(old_lines[i - 1], new_lines[j - 1]) == 0) {
            ops[count] = ' '; line_a[count++] = i - 1;   /* 공통: 그대로 */
            i--; j--;
        } else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
            ops[count] = '+'; line_a[count++] = j - 1;   /* 새 파일에만 있음: 추가 */
            j--;
        } else {
            ops[count] = '-'; line_a[count++] = i - 1;   /* 옛 파일에만 있음: 삭제 */
            i--;
        }
    }

역추적하면서 공통 줄(LCS에 속한 줄)은 그대로 두고, 왼쪽으로 이동할 때는 “새 파일에 추가된 줄”(+), 위로 이동할 때는 “옛 파일에서 삭제된 줄”(-)로 표시합니다. git diff가 보여 주는 그 화면의 정체입니다.

while (i > 0 || j > 0)이 &&가 아니라 ||인 이유도 보세요. LCS 문자열 복원은 공통 글자만 필요해서 한쪽이 끝나면 멈춰도 됐지만, diff는 남은 줄을 전부 + 또는 -로 표시해야 합니다. 그래서 둘 다 0이 될 때까지 갑니다.

역추적이 끝에서 시작하므로 결과가 역순으로 쌓입니다. 그래서 ops 배열에 모은 뒤 뒤에서부터 출력합니다(for (int k = count - 1; k >= 0; k--)). 14주차 BFS 경로 복원에서 재귀로 뒤집었던 것과 같은 문제를, 여기서는 배열로 해결한 것이죠.

실제 git은 마이어스(Myers) 알고리즘이라는 더 정교한 버전을 씁니다. 기본 LCS DP는 두 파일이 각각 n줄이면 n×n 칸의 표가 필요해서 큰 파일에는 부담이니까요. 하지만 근본 아이디어는 똑같습니다.

3.6 O(n×m)을 실측하기

표의 칸 수가 두 문자열 길이의 곱이니 시간도 그에 비례해야 합니다. 길이 n의 무작위 DNA 서열 두 개로 LCS 길이만 계산하는 시간을 재 봤습니다(표 전체를 저장하면 메모리가 n²이라, 두 행만 번갈아 쓰는 방식으로 재었습니다).

    n      칸 수(n*n)   LCS   시간(ms)  직전 대비
  1000        1000000    645       2.9
  2000        4000000   1297      12.0  x4.1
  4000       16000000   2617      51.2  x4.3
  8000       64000000   5212     238.8  x4.7
 16000      256000000  10468    1050.8  x4.4

n을 2배로 늘리면 시간이 약 4배가 됩니다. n²이니까요. 15주차에서 정렬 알고리즘의 복잡도를 실측했던 것과 같은 방법입니다. 복잡도 표기는 이론이지만, 이렇게 표로 확인하면 “n이 2배면 4배 느려진다”는 감각이 생깁니다. 두 파일이 각각 만 줄이면 표가 1억 칸입니다. git이 다른 알고리즘을 쓰는 이유입니다.

실험: 바꾸면 어떻게 될까

lcs_string의 >=를 >로 바꿔 보세요. 위와 왼쪽 값이 같을 때 어느 쪽으로 갈지가 바뀝니다. LCS의 길이는 같지만 복원되는 문자열이 달라질 수 있습니다. “ABCBDAB”와 “BDCABA”의 LCS는 BCBA 말고도 BCAB, BDAB 등 여러 개입니다. DP 표는 길이만 보장하고, 어느 것을 복원할지는 동률 처리 규칙이 정합니다.
mini_diff의 옛 코드에서 return 0; 줄을 지우고 실행해 보세요. 그 줄이 +로 표시되는지 확인하세요.
DNA 예제의 두 서열을 같은 것으로 바꿔 보세요. LCS 길이가 서열 길이와 같아지고, 표의 대각선이 1, 2, 3, …으로 증가합니다.

4. 동전 거스름돈: 탐욕과 DP의 갈림길

4.1 같은 문제, 다른 답

“최소 개수의 동전으로 거슬러 주기.” 편의점에서 매일 일어나는 계산입니다. 그리고 대부분 큰 동전부터 최대한 쓰는 탐욕법으로 답이 나옵니다. 1,780원이면 500원 3개, 100원 2개, 50원 1개, 10원 3개. 9개.

그런데 이 방법이 동전의 종류에 따라 틀립니다. 동전이 1원, 3원, 4원짜리라면 6원을 거슬러 줄 때 큰 것부터 쓰면 4+1+1로 3개인데, 3+3이면 2개입니다.

examples/coin_change.c:

/*
 * coin_change.c - 동전 거스름돈: 탐욕과 DP의 갈림길
 * 17주차: 고급 알고리즘과 최적화
 *
 * "최소 개수의 동전으로 거슬러 주기"
 *
 * 한국 동전(500/100/50/10)은 큰 것부터 탐욕으로 담으면 항상 최적.
 * 그런데 동전계가 {1, 3, 4}라면?
 *   6원 = 탐욕: 4+1+1 (3개)  vs  정답: 3+3 (2개)!
 *
 * 같은 문제인데 왜 탐욕이 되다가 안 될까?
 * -> "탐욕 선택 속성"이 동전계에 따라 성립하기도, 깨지기도 하기 때문.
 * -> 보장이 필요하면 DP.
 *
 * dp[amount] = 금액 amount를 만드는 최소 동전 수
 * dp[a] = min(dp[a - coin] + 1) for 각 동전
 */
#include <stdio.h>
#include <string.h>

#define INF 999999
#define MAX_AMOUNT 2000

/* 탐욕: 큰 동전부터 최대한 */
int greedy_coins(const int coins[], int n, int amount, int used[]) {
    int total = 0;
    for (int i = 0; i < n; i++) used[i] = 0;

    for (int i = n - 1; i >= 0; i--) {       /* coins는 오름차순 가정 */
        while (amount >= coins[i]) {
            amount -= coins[i];
            used[i]++;
            total++;
        }
    }
    return (amount == 0) ? total : -1;       /* 못 만들면 -1 */
}

/* DP: 1원부터 차곡차곡 */
int dp_coins(const int coins[], int n, int amount, int used[]) {
    static int dp[MAX_AMOUNT + 1];
    static int choice[MAX_AMOUNT + 1];       /* 역추적: 마지막에 쓴 동전 */

    if (amount > MAX_AMOUNT) return -1;      /* 배열 범위 방어! */

    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        dp[a] = INF;
        choice[a] = -1;
        for (int i = 0; i < n; i++) {
            if (coins[i] <= a && dp[a - coins[i]] + 1 < dp[a]) {
                dp[a] = dp[a - coins[i]] + 1;
                choice[a] = i;
            }
        }
    }

    if (dp[amount] >= INF) return -1;

    /* 역추적 */
    for (int i = 0; i < n; i++) used[i] = 0;
    for (int a = amount; a > 0; a -= coins[choice[a]]) {
        used[choice[a]]++;
    }
    return dp[amount];
}

void show(const int coins[], int n, const int used[]) {
    printf("(");
    int first = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (used[i] > 0) {
            printf("%s%d원x%d", first ? "" : " + ", coins[i], used[i]);
            first = 0;
        }
    }
    printf(")");
}

void compare(const char *label, const int coins[], int n, int amount) {
    int used_g[16], used_d[16];

    printf("\n[%s] %d원 거슬러 주기\n", label, amount);

    int g = greedy_coins(coins, n, amount, used_g);
    int d = dp_coins(coins, n, amount, used_d);

    printf("  탐욕: ");
    if (g < 0) printf("실패!");
    else { printf("%d개 ", g); show(coins, n, used_g); }
    printf("\n  DP  : ");
    if (d < 0) printf("불가능 판정 (정확!)");
    else { printf("%d개 ", d); show(coins, n, used_d); }
    printf("\n");

    if (g < 0 && d < 0)  printf("  -> 애초에 만들 수 없는 금액. DP는 이것도 정확히 판정!\n");
    else if (g < 0)      printf("  -> 탐욕은 실패했지만 DP는 해결!\n");
    else if (g == d)     printf("  -> 같다. 이 동전계에선 탐욕도 최적!\n");
    else                 printf("  -> 탐욕이 %d개 손해! 보장은 DP만.\n", g - d);
}

int main(void) {
    printf("동전 거스름돈: 탐욕 vs DP\n");
    printf("=====================================\n");

    /* 1. 한국 동전: 탐욕의 홈그라운드 */
    int krw[] = {10, 50, 100, 500};
    compare("한국 동전 {10,50,100,500}", krw, 4, 1780);

    /* 2. 이상한 동전계: 탐욕의 함정 */
    int weird[] = {1, 3, 4};
    compare("동전계 {1,3,4}", weird, 3, 6);

    /* 3. 옛 영국 동전 스타일 */
    int old_uk[] = {1, 5, 8, 12};
    compare("동전계 {1,5,8,12}", old_uk, 4, 16);

    /* 4. 1이 없는 동전계: 탐욕은 실패까지 한다 */
    int no_one[] = {3, 7};
    compare("동전계 {3,7} (1원 없음)", no_one, 2, 12);
    /* 탐욕: 7을 덥석 -> 남은 5를 못 만든다. DP: 3x4로 해결! */

    /* 5. 진짜 불가능한 금액: DP는 '불가능'도 정확히 판정 */
    compare("동전계 {3,7}", no_one, 2, 11);

    printf("\n=====================================\n");
    printf("교훈:\n");
    printf("1. 탐욕이 최적인지는 '증명'이 필요하다 (감이 아니라!)\n");
    printf("   - 실제 화폐는 탐욕이 되도록 '설계'된 것\n");
    printf("2. 확신이 없으면 DP - 모든 경우를 표로 보장\n");
    printf("3. dp[a] = min(dp[a - coin] + 1): 한 줄 점화식의 힘\n");
    printf("4. choice[] 배열 하나 추가로 '몇 개'가 '무엇을'이 된다\n");
    return 0;
}

$ ./build/coin_change
동전 거스름돈: 탐욕 vs DP
=====================================

[한국 동전 {10,50,100,500}] 1780원 거슬러 주기
  탐욕: 9개 (500원x3 + 100원x2 + 50원x1 + 10원x3)
  DP  : 9개 (500원x3 + 100원x2 + 50원x1 + 10원x3)
  -> 같다. 이 동전계에선 탐욕도 최적!

[동전계 {1,3,4}] 6원 거슬러 주기
  탐욕: 3개 (4원x1 + 1원x2)
  DP  : 2개 (3원x2)
  -> 탐욕이 1개 손해! 보장은 DP만.

[동전계 {1,5,8,12}] 16원 거슬러 주기
  탐욕: 5개 (12원x1 + 1원x4)
  DP  : 2개 (8원x2)
  -> 탐욕이 3개 손해! 보장은 DP만.

[동전계 {3,7} (1원 없음)] 12원 거슬러 주기
  탐욕: 실패!
  DP  : 4개 (3원x4)
  -> 탐욕은 실패했지만 DP는 해결!

[동전계 {3,7}] 11원 거슬러 주기
  탐욕: 실패!
  DP  : 불가능 판정 (정확!)
  -> 애초에 만들 수 없는 금액. DP는 이것도 정확히 판정!
...

4.2 다섯 시나리오가 말하는 것

시나리오 1 (한국 동전): 탐욕이 최적입니다. 우연이 아닙니다. 실제 화폐 체계는 탐욕이 통하도록 설계되어 있습니다(1-5-10 배수 구조). 사람이 암산으로 거스름돈을 계산할 수 있어야 하니까요.

시나리오 2 ({1,3,4}에서 6원): 탐욕은 4를 먼저 집어 4+1+1 세 개, DP는 3+3 두 개. 큰 것을 집는 순간 나머지가 어중간해지는 배낭 문제의 반례와 똑같은 구조입니다.

시나리오 3 ({1,5,8,12}에서 16원): 탐욕이 5개, DP가 2개. 손해가 더 큽니다.

시나리오 4 ({3,7}에서 12원): 여기서는 탐욕이 실패합니다. 7을 집으면 남은 5를 3과 7로 만들 수 없거든요. 탐욕은 한 번 집으면 되돌아가지 않으니 “만들 수 없다”고 답합니다. DP는 3+3+3+3을 찾아냅니다.

시나리오 5 ({3,7}에서 11원): 정말로 불가능한 금액입니다. DP는 이것도 정확히 판정합니다. 모든 경우를 표로 검토했으니 “없다”는 결론에 근거가 있죠.

4.3 점화식과 표 채우기

    dp[0] = 0;                                   /* 기저: 0원은 동전 0개 */
    for (int a = 1; a <= amount; a++) {
        dp[a] = INF;                             /* 일단 "불가능"으로 놓고 */
        choice[a] = -1;
        for (int i = 0; i < n; i++) {            /* 마지막 동전으로 무엇을 쓸지 전부 시도 */
            if (coins[i] <= a && dp[a - coins[i]] + 1 < dp[a]) {
                dp[a] = dp[a - coins[i]] + 1;    /* 더 적은 개수를 찾으면 갱신 */
                choice[a] = i;                   /* 역추적용: 그때 쓴 동전 */
            }
        }
    }

상태: dp[a] = 금액 a를 만드는 최소 동전 수
점화식: dp[a] = min(dp[a − 동전] + 1), 모든 동전에 대해. “금액 a를 만드는 마지막 동전이 c라면, 그 전까지는 a−c를 최소로 만들었을 것”이라는 생각입니다.
기저와 순서: dp[0] = 0, 1원부터 차례로. dp[a]는 자기보다 작은 금액의 칸만 보므로 작은 금액부터 채우면 됩니다.

{1, 3, 4}로 6원까지 표를 채우는 과정을 전부 찍어 봤습니다. 각 금액에서 어떤 후보들이 있었고 무엇이 뽑혔는지 보세요.

 a | 후보 (dp[a-동전]+1)                 | dp[a] | 마지막 동전
 1 | 동전1: dp[0]+1=1  | 1 | 1원
 2 | 동전1: dp[1]+1=2  | 2 | 1원
 3 | 동전1: dp[2]+1=3  동전3: dp[0]+1=1  | 1 | 3원
 4 | 동전1: dp[3]+1=2  동전3: dp[1]+1=2  동전4: dp[0]+1=1  | 1 | 4원
 5 | 동전1: dp[4]+1=2  동전3: dp[2]+1=3  동전4: dp[1]+1=2  | 2 | 1원
 6 | 동전1: dp[5]+1=3  동전3: dp[3]+1=2  동전4: dp[2]+1=3  | 2 | 3원
역추적: 3원(dp[6]) -> 3원(dp[3]) -> 0

6원 칸을 보세요. 마지막 동전으로 1원을 쓰면 dp[5]+1 = 3, 3원을 쓰면 dp[3]+1 = 2, 4원을 쓰면 dp[2]+1 = 3. 최소는 3원을 썼을 때의 2입니다. 탐욕은 “6원에서 제일 큰 4원부터”라고 한 갈래만 갔지만, DP는 마지막 동전이 될 수 있는 모든 후보를 비교했습니다. 그리고 dp[5], dp[3], dp[2] 자체가 이미 각각의 최적이므로, 그중 최선을 고른 dp[6]도 최적입니다. 이것이 최적 부분 구조입니다.

4.4 역추적: choice[] 한 줄로 “무엇을”

배낭에서는 표를 비교해서 역추적했습니다. 여기서는 선택을 명시적으로 기록합니다. choice[a]에 “금액 a를 만들 때 마지막에 쓴 동전”을 적어 뒀으니, 거꾸로 따라가면 됩니다.

    for (int a = amount; a > 0; a -= coins[choice[a]]) {
        used[choice[a]]++;
    }

위 표의 마지막 줄이 그 과정입니다. 6원의 마지막 동전은 3원 → 남은 3원의 마지막 동전도 3원 → 남은 0원. 3원 2개. 반복문 조건에 a > 0이 있어서 0에 닿으면 멈춥니다.

두 역추적 방식을 비교하면 이렇습니다. 표 비교(배낭)는 메모리를 아끼고, 명시적 기록(동전)은 코드가 단순하고 빠릅니다. 둘 다 흔히 쓰이니 둘 다 익혀 두세요.

4.5 INF의 정체와 INT_MAX의 함정

INF로 초기화하는 것이 불가능 판정의 열쇠입니다. 어떤 동전으로도 만들 수 없으면 dp[a]가 INF로 남고, 그것이 곧 “불가능”입니다. dp[amount] >= INF면 −1을 돌려줍니다.

그런데 왜 INF가 999999일까요? 2주차에서 배운 INT_MAX(약 21억)를 쓰면 더 확실하지 않을까요? 실험해 봤습니다.

동전 {3,7}, 11원 (불가능한 금액)
INF = 999999 : dp[11] = 999999  (INF 이상이면 불가능)
INF = INT_MAX: dp[11] = -2147483647  (INT_MAX + 1 이 넘쳐서 음수 -> '가능'으로 오판)

dp[a − 동전]이 INT_MAX(불가능)일 때 거기에 + 1을 하면 2주차의 오버플로가 일어나 음수가 됩니다. 음수는 어떤 값보다 작으니 < dp[a] 조건이 참이 되어 “불가능한 금액을 −21억 개의 동전으로 만들 수 있다”는 답이 나옵니다. 14주차 플로이드-워셜에서 “INF에 INF를 더하면 안 된다”고 했던 것과 같은 함정입니다.

그래서 INF는 “실제 가능한 최댓값보다는 크되, 더하기를 몇 번 해도 넘치지 않는 값” 으로 잡습니다. 동전 개수는 아무리 많아도 금액(2000)을 넘을 수 없으니 999999면 충분합니다.

4.6 배열 범위 방어

    if (amount > MAX_AMOUNT) return -1;      /* 배열 범위 방어! */

이 한 줄에는 사연이 있습니다. 이 예제를 만들면서 실제로 겪은 버그입니다. 처음에는 배열을 dp[1001]로 잡아 두고 1,780원을 넣었습니다. dp[1780]에 쓰는 순간 배열 범위를 넘어 인접 메모리(choice 배열)를 덮어썼고, 역추적 루프가 엉뚱한 값을 따라가며 무한 루프에 빠졌습니다.

4주차에서 배운 대로 C에서 배열 범위 초과는 컴파일러도 런타임도 알려 주지 않습니다. 그냥 옆 메모리를 조용히 망가뜨리죠. 그리고 증상은 전혀 다른 곳(역추적 루프)에서 나타납니다. 그때 4주차에서 쓴 AddressSanitizer(-fsanitize=address)가 있었다면 첫 줄에서 잡혔을 겁니다.

DP를 작성할 때는 배열 크기부터 확인하세요. 입력의 상한을 명시하고, 넘으면 거부하거나 동적 할당(7주차)으로 바꾸세요. DP는 배열 인덱스를 격렬하게 다루므로 특히 위험합니다.

4.7 이번 주의 철학

동전 예제가 이번 주 전체의 철학을 압축합니다.

탐욕이 최적인지는 감이 아니라 증명의 문제다.

같은 문제인데 동전계에 따라 탐욕이 되기도, 안 되기도 합니다. 그러니 “이 정도면 탐욕으로 되겠지”라는 직관을 믿으면 안 됩니다. 증명하거나, 작은 입력에서 DP와 비교해 반례를 찾아보거나, 아니면 그냥 DP를 쓰세요. 9절에서는 반대로 탐욕이 증명된 무대를 봅니다.

실험: 바꾸면 어떻게 될까

INF를 INT_MAX로 바꿔 실제로 위의 오판을 재현해 보세요. #include <limits.h>가 필요합니다. 컴파일러는 -Wall로도 경고하지 않습니다. 부호 있는 정수의 오버플로는 정의되지 않은 동작이라, 최적화 옵션에 따라 다른 결과가 나올 수도 있습니다.
“최소 개수” 대신 “만드는 방법의 가짓수” 를 세어 보세요. dp[a] += dp[a − 동전], dp[0] = 1로 점화식을 바꾸면 됩니다. 그런데 두 반복문의 순서에 따라 답이 달라집니다.

동전 바깥 루프: 4가지 (순서 무시: 1x6, 1x3+3, 1x2+4, 3+3)
금액 바깥 루프: 9가지 (순서 구분: 3+3, 1+1+4, 1+4+1, 4+1+1, ...)

동전을 바깥에 두면 “1원짜리를 다 쓴 다음 3원짜리를 쓴다”처럼 동전 종류의 순서가 고정되어 {1,1,4}와 {4,1,1}이 같은 것으로 세어집니다. 금액을 바깥에 두면 매 금액마다 모든 동전을 다시 고려하므로 순서가 다른 것을 따로 셉니다. 반복문 순서가 문제의 정의를 바꿉니다. 12절 심화 문제 7번이 이것입니다.

MAX_AMOUNT를 1000으로 줄이고 방어 줄을 지운 뒤 1,780원을 넣어 보세요. 위에서 말한 무한 루프가 재현되는지, 아니면 다른 증상이 나오는지 확인하세요(메모리 배치에 따라 다릅니다). Ctrl + C로 끊을 수 있습니다.

5. 백트래킹: 가보고, 막히면 돌아온다

5.1 N-Queens

미로에서 길을 찾을 때 우리는 어떻게 할까요? 갈림길에서 하나를 골라 가 보고, 막다른 길이면 갈림길로 되돌아와 다른 길을 고릅니다. 이것을 그대로 코드로 옮긴 것이 백트래킹(backtracking) 입니다. “되돌아가기”라는 이름 그대로입니다. 14주차 DFS와 16주차 정규식 엔진에서 이미 만났죠.

교과서적인 예제가 N-Queens입니다. N×N 체스판에 퀸 N개를 서로 공격할 수 없게 배치하는 문제입니다. 체스의 퀸은 가로, 세로, 대각선으로 몇 칸이든 움직일 수 있어서, 같은 행·열·대각선에 다른 퀸이 있으면 안 됩니다.

무식하게 풀면 어떻게 될까요? 8×8 판에 퀸 8개를 놓는 모든 경우를 만들어 놓고 하나씩 검사하는 것입니다. 행마다 퀸을 하나씩 놓는다고 해도 8⁸ = 1,677만 가지입니다. 백트래킹은 이것을 1만 5천 번으로 줄입니다. 어떻게 하는지 봅시다.

examples/nqueens.c:

/*
 * nqueens.c - N-Queens: 백트래킹의 교과서
 * 17주차: 고급 알고리즘과 최적화
 *
 * NxN 체스판에 퀸 N개를 서로 공격 못 하게 배치하라.
 * (퀸은 가로/세로/대각선 무제한 이동)
 *
 * 백트래킹 = "한 줄씩 놓아보고, 막히면 되돌아와 다른 칸"
 * 무식한 전수조사와의 차이: 유망하지 않은 가지를 즉시 자른다(가지치기).
 *
 * 8-Queens: 전수조사는 1677만 판을 다 만들어 검사, 백트래킹은 1만 5천 번 놓아 보고 끝!
 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 14

static int col_of[MAX_N];        /* col_of[row] = 그 행의 퀸이 놓인 열 */
static long attempts;            /* 놓아본 횟수 (가지치기 효과 측정) */
static int solutions;

/* (row, col)에 놓아도 되는가? 이전 행들의 퀸과 충돌 검사 */
int is_safe(int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = col_of[r];
        if (c == col) return 0;                  /* 같은 열 */
        if (abs(row - r) == abs(col - c)) return 0;  /* 대각선 */
    }
    return 1;                    /* 같은 행은 애초에 불가능 (행마다 하나) */
}

void print_board(int n) {
    printf("  [해 %d]\n", solutions);
    for (int r = 0; r < n; r++) {
        printf("  ");
        for (int c = 0; c < n; c++) {
            printf("%s", (col_of[r] == c) ? " Q" : " .");
        }
        printf("\n");
    }
    printf("\n");
}

/* row행부터 퀸을 놓는다 */
void solve(int n, int row, int max_print) {
    if (row == n) {              /* 모든 행 완료 = 해 발견! */
        solutions++;
        if (solutions <= max_print) print_board(n);
        return;
    }

    for (int col = 0; col < n; col++) {
        attempts++;
        if (!is_safe(row, col)) continue;    /* 가지치기: 여기서 끊는다 */

        col_of[row] = col;       /* 선택 */
        solve(n, row + 1, max_print);        /* 다음 행으로 전진 */
        /* 돌아왔다 = 이 선택으로는 끝까지 못 갔거나 다 세어봤다.
         * col_of[row]는 다음 반복에서 덮어쓰므로 명시적 취소 불필요 */
    }
}

/* 비교용: 가지치기 없이 끝까지 가서 검사하는 전수조사 */
static long brute_attempts;      /* 완성한 판의 수 */
static long brute_placements;    /* 퀸을 놓아 본 횟수 (백트래킹의 attempts 와 같은 단위) */

int all_safe(int n) {
    for (int r = 1; r < n; r++) {
        for (int p = 0; p < r; p++) {
            if (col_of[p] == col_of[r] ||
                abs(r - p) == abs(col_of[r] - col_of[p])) return 0;
        }
    }
    return 1;
}

int brute(int n, int row) {
    if (row == n) {
        brute_attempts++;
        return all_safe(n) ? 1 : 0;
    }
    int count = 0;
    for (int col = 0; col < n; col++) {
        brute_placements++;
        col_of[row] = col;
        count += brute(n, row + 1);
    }
    return count;
}

int main(void) {
    printf("=== 4-Queens: 백트래킹 과정 감각 잡기 ===\n");
    solutions = 0;
    attempts = 0;
    solve(4, 0, 2);
    printf("해 %d개, 배치 시도 %ld번 (전체 경우 4^4=256)\n",
           solutions, attempts);

    printf("\n=== 8-Queens: 가지치기의 위력 ===\n");
    solutions = 0;
    attempts = 0;
    solve(8, 0, 1);              /* 첫 해만 출력 */
    printf("해 %d개 발견\n", solutions);
    printf("백트래킹 시도: %ld번\n", attempts);

    brute_attempts = brute_placements = 0;
    int bs = brute(8, 0);
    printf("전수조사     : %ld번 놓아 봄, %ld판 완성 후 검사 (해 %d개로 일치)\n",
           brute_placements, brute_attempts, bs);
    printf("-> 가지치기가 %.0f배 절약! (막힌 길은 초입에서 끊으니까)\n",
           (double)brute_placements / attempts);

    printf("\n=== N을 키우면? (해의 개수 폭발) ===\n");
    printf("   N   해 개수      시도 횟수\n");
    for (int n = 4; n <= 11; n++) {
        solutions = 0;
        attempts = 0;
        solve(n, 0, 0);
        printf("  %2d  %8d  %12ld\n", n, solutions, attempts);
    }
    printf("(시도가 급증하지만 지수 전체 탐색보다는 훨씬 얌전하다)\n");

    printf("\n백트래킹 3요소 (모든 백트래킹 문제의 뼈대):\n");
    printf("1. 선택   : 이번 행의 열 고르기\n");
    printf("2. 제약   : is_safe - 유망하지 않으면 그 즉시 포기\n");
    printf("3. 목표   : 모든 행 채움 -> 해 기록\n");
    printf("'선택 -> 재귀 -> 취소'의 리듬을 기억하세요!\n");
    return 0;
}

$ ./build/nqueens
=== 4-Queens: 백트래킹 과정 감각 잡기 ===
  [해 1]
   . Q . .
   . . . Q
   Q . . .
   . . Q .

  [해 2]
   . . Q .
   Q . . .
   . . . Q
   . Q . .

해 2개, 배치 시도 60번 (전체 경우 4^4=256)

=== 8-Queens: 가지치기의 위력 ===
  [해 1]
   Q . . . . . . .
   . . . . Q . . .
   . . . . . . . Q
   . . . . . Q . .
   . . Q . . . . .
   . . . . . . Q .
   . Q . . . . . .
   . . . Q . . . .

해 92개 발견
백트래킹 시도: 15720번
전수조사     : 19173960번 놓아 봄, 16777216판 완성 후 검사 (해 92개로 일치)
-> 가지치기가 1220배 절약! (막힌 길은 초입에서 끊으니까)

=== N을 키우면? (해의 개수 폭발) ===
   N   해 개수      시도 횟수
   4         2            60
   5        10           220
   6         4           894
   7        40          3584
   8        92         15720
   9       352         72378
  10       724        348150
  11      2680       1806706
...

N-퀸

N-퀸

5.2 판을 어떻게 저장하나: 자료구조가 제약 하나를 없앤다

코드에서 먼저 볼 것은 판을 2차원 배열로 저장하지 않는다는 점입니다.

static int col_of[MAX_N];        /* col_of[row] = 그 행의 퀸이 놓인 열 */

col_of[2] = 5는 “2번 행의 퀸은 5번 열에 있다”입니다. 8×8 판이 아니라 숫자 8개입니다. 왜 이렇게 할까요?

퀸은 가로로 무제한 움직이니, 한 행에 퀸이 두 개 있을 수 없습니다. 그렇다면 답은 반드시 “행마다 정확히 하나”입니다. 행마다 하나라면 각 행의 퀸이 몇 번 열에 있는지만 기록하면 판이 완전히 정해집니다. 그리고 이 표현을 쓰면 “같은 행 충돌”이라는 검사가 아예 필요 없어집니다. 구조상 불가능하니까요.

이 선택 하나로 탐색 공간이 달라집니다. 64칸 중 8칸을 고르는 방법은 약 44억 가지인데, 행마다 열 하나를 고르는 방법은 8⁸ = 1,677만 가지입니다. 알고리즘을 짜기 전에 자료구조로 문제를 줄이는 것, 이것이 첫 번째 교훈입니다.

5.3 is_safe: 제약 검사

int is_safe(int row, int col) {
    for (int r = 0; r < row; r++) {              /* 이미 놓은 윗행들만 검사 */
        int c = col_of[r];
        if (c == col) return 0;                  /* 같은 열 */
        if (abs(row - r) == abs(col - c)) return 0;  /* 대각선 */
    }
    return 1;
}

“(row, col)에 놓아도 되는가?”를 답하는 함수입니다. 검사 대상은 이미 놓인 윗행들뿐입니다. 아랫행에는 아직 아무것도 없으니까요.

같은 열: 윗행의 퀸이 같은 열에 있으면 세로로 공격당합니다.
대각선: 두 칸이 대각선 위에 있다는 것은 “행 차이와 열 차이가 같다”는 뜻입니다. (2, 3)과 (5, 6)은 행이 3, 열이 3 차이니 대각선입니다. (2, 3)과 (5, 0)도 행 3, 열 −3이라 반대 방향 대각선입니다. abs()(절댓값, stdlib.h)로 방향을 무시하고 크기만 비교합니다. 체스판 문제에서 자주 쓰는 관용구니 외워 두세요.

5.4 solve: 선택 → 재귀 → 취소

void solve(int n, int row, int max_print) {
    if (row == n) {                          /* 목표: 모든 행에 놓았다 = 해 */
        solutions++;
        if (solutions <= max_print) print_board(n);
        return;
    }

    for (int col = 0; col < n; col++) {      /* 선택지: 이번 행의 열 0..n-1 */
        attempts++;
        if (!is_safe(row, col)) continue;    /* 제약: 안 되면 다음 열로 (가지치기) */

        col_of[row] = col;                   /* 선택 */
        solve(n, row + 1, max_print);        /* 재귀: 다음 행으로 */
                                             /* (취소는 다음 반복이 덮어쓰므로 생략) */
    }
}

row번 행에 퀸을 놓는 함수입니다. 0번 열부터 차례로 “여기 놓아도 되나?”를 묻고, 되면 놓은 뒤 다음 행을 맡은 자기 자신을 부릅니다. 그 호출이 돌아왔다는 것은 “이 선택으로 끝까지 가 봤다(해를 찾았든 못 찾았든)”는 뜻이고, 그러면 다음 열을 시도합니다. 모든 열을 시도하고 나면 함수가 끝나면서 윗행으로 되돌아갑니다. 이것이 백트래킹입니다.

프로젝트 1의 시각화 도구가 이 과정을 6×6 판으로 그려 줍니다. 실제 출력의 앞부분입니다.

    0행 0열에 놓아본다...
     Q . . . . .
     . . . . . .
     ...
    1행 2열에 놓아본다...
     Q . . . . .
     . . Q . . .
     ...
    2행 4열에 놓아본다...
    3행 1열에 놓아본다...
    4행 3열에 놓아본다...
     Q . . . . .
     . . Q . . .
     . . . . Q .
     . Q . . . .
     . . . Q . .
     . . . . . .

    4행 3열은 막다른 길! 백트래킹
    3행 1열은 막다른 길! 백트래킹
    2행 4열은 막다른 길! 백트래킹

0, 2, 4, 1, 3열로 다섯 행을 채웠는데 5행에는 놓을 곳이 없습니다. 그래서 4행의 퀸을 치우고(4행에서 3열 뒤로 놓을 곳이 없으니) 3행으로, 3행의 퀸도 치우고 2행으로 되돌아갑니다. 되돌아간 뒤 2행에서 5열을 시도하는 식으로 계속됩니다. “놓고, 막히고, 되돌아오는” 리듬이 보이시나요?

5.5 가지치기의 위력을 숫자로

숫자를 보세요. 8-Queens에서 백트래킹은 1만 5,720번 놓아 봤고, 전수조사는 1,917만 번 놓아 보고 1,677만 판을 완성해 검사했습니다. 같은 단위(놓아 본 횟수)로 비교하면 1,220배 차이입니다.

비결은 가지치기(pruning) 입니다. 전수조사는 8개를 다 놓고 나서 “올바른가?”를 검사합니다. 백트래킹은 놓는 순간마다 검사해서, 이미 틀린 배치라면 그 아래를 전부 건너뜁니다.

        if (!is_safe(row, col)) continue;    /* 가지치기: 여기서 끊는다 */

1행에서 이미 충돌이 났다면, 2~7행에 퀸을 놓는 조합 8⁶ = 26만 가지를 아예 시도하지 않습니다. 탐색 나무에서 가지를 통째로 자르는 것이죠. 자를수록 위쪽(뿌리 근처)에서 자를수록 절약이 큽니다.

전수조사 코드의 brute_placements: 배수를 “완성한 판 수 × 8″로 어림잡으면 8,538배가 나옵니다. 하지만 실제로 퀸을 놓은 횟수를 세면 8 + 8² + … + 8⁸ = 19,173,960번이고, 배수는 1,220배입니다. 어림셈 대신 같은 단위로 직접 센 값으로 비교해야 합니다.

5.6 백트래킹 3요소와 리듬

모든 백트래킹 문제는 세 요소로 이루어집니다.

선택(choice): 이번 단계에서 고를 수 있는 후보들. N-Queens에서는 “이번 행의 열”.
제약(constraint): 후보가 유효한가. is_safe.
목표(goal): 언제 완성인가. 모든 행을 채웠을 때.

그리고 코드의 리듬은 언제나 같습니다.

선택 → 재귀 → 취소

N-Queens에서는 col_of[row]를 다음 반복에서 덮어쓰므로 취소가 생략됐지만, 개념적으로는 항상 세 박자입니다. 6절의 순열 생성에서 취소를 빼먹으면 어떻게 되는지 직접 보게 됩니다.

5.7 지수 폭발의 벽

표의 마지막 열을 보세요. N이 커질수록 시도 횟수가 급증합니다. N=11에서 이미 180만 번입니다. 시간도 재 봤습니다.

  N   해 개수      시도 횟수   시간(ms)  직전 대비
  8       92          15720       0.3
  9      352          72378       1.3  x4.5배
 10      724         348150       6.8  x5.1배
 11     2680        1806706      35.1  x5.2배
 12    14200       10103868     200.4  x5.7배
 13    73712       59815314    1208.6  x6.0배

N이 1 커질 때마다 약 5~6배씩 느려집니다. 가지치기가 1,220배를 절약했지만, 그래도 여전히 지수적입니다. 밑이 작아졌을 뿐 지수는 그대로인 것이죠. 이 추세면 N=20은 13에서 7단계, 5.5⁷ ≈ 15만 배로 약 50시간이 걸립니다.

백트래킹은 n이 작을 때의 무기입니다. 이 한계를 기억해 두세요. 문제 규모가 크면 DP, 탐욕, 또는 근사 알고리즘으로 방향을 바꿔야 합니다.

실험: 바꾸면 어떻게 될까

is_safe에서 대각선 검사 줄을 지우고 8-Queens를 돌려 보세요. “해”가 훨씬 많이 나오는데, 전부 대각선으로 공격당하는 틀린 해입니다. 제약이 빠지면 백트래킹은 틀린 답을 자신 있게 내놓습니다. 검증용 all_safe로 확인하는 습관이 필요한 이유입니다.
solve 안의 attempts++를 if (!is_safe(...)) 뒤로 옮겨 보세요. 그러면 “놓아 본 횟수”가 아니라 “실제로 놓은 횟수”를 세게 됩니다. 8-Queens에서 얼마가 나오는지 확인하고, 두 숫자의 차이가 무엇을 뜻하는지 생각해 보세요.
MAX_N을 넘는 N(예: 15)을 solve에 넣으면 col_of[14]에 쓰는 순간 배열 밖입니다. 4절에서 본 그 문제입니다. 실행 전에 n <= MAX_N을 검사하는 줄을 추가해 보세요.

6. 조합 생성 3종 세트

6.1 모든 백트래킹의 뼈대

부분집합, 조합, 순열. 이 세 가지 생성 패턴은 백트래킹 문제의 기본 골격입니다. “비밀번호를 전부 시도한다”, “메뉴 조합을 전부 만든다”, “방문 순서를 전부 만든다”가 모두 이 셋 중 하나입니다. 그리고 셋의 코드가 거의 같습니다. 차이는 제약 하나뿐이죠.

examples/combinations.c:

/*
 * combinations.c - 백트래킹 3종: 부분집합, 조합, 순열
 * 17주차: 고급 알고리즘과 최적화
 *
 * 모든 백트래킹 문제의 뼈대가 되는 세 가지 생성 패턴입니다.
 * 전부 "선택 -> 재귀 -> 취소"의 같은 리듬이라는 것에 주목!
 *
 * 부분집합: 각 원소를 "넣거나/말거나"     -> 2^n개
 * 조합    : n개 중 k개 고르기 (순서 무시)  -> nCk개
 * 순열    : n개를 줄 세우기 (순서 중요)    -> n!개
 */
#include <stdio.h>

#define N 4
static const char items[N] = {'A', 'B', 'C', 'D'};

static int count;

/* ---------- 1. 부분집합: 원소마다 2갈래 ---------- */
static int in_set[N];

void subsets(int index) {
    if (index == N) {                        /* 모든 원소 결정 완료 */
        count++;
        printf("  {");
        for (int i = 0; i < N; i++) {
            if (in_set[i]) printf(" %c", items[i]);
        }
        printf(" }\n");
        return;
    }

    in_set[index] = 1;           /* 갈래 1: 넣는다 */
    subsets(index + 1);
    in_set[index] = 0;           /* 취소하고 */
    subsets(index + 1);          /* 갈래 2: 안 넣는다 */
}

/* ---------- 2. 조합: k개 고르기 (start로 중복 순서 방지) ---------- */
static int chosen[N];

void combinations(int start, int picked, int k) {
    if (picked == k) {
        count++;
        printf("  {");
        for (int i = 0; i < picked; i++) printf(" %c", items[chosen[i]]);
        printf(" }\n");
        return;
    }

    for (int i = start; i < N; i++) {
        chosen[picked] = i;              /* 선택 */
        combinations(i + 1, picked + 1, k);  /* i 다음부터만 (순서 방지!) */
        /* 취소는 덮어쓰기로 자동 */
    }
}

/* ---------- 3. 순열: 아직 안 쓴 원소를 자리마다 ---------- */
static int used[N];
static int order[N];

void permutations(int pos) {
    if (pos == N) {
        count++;
        printf("  ");
        for (int i = 0; i < N; i++) printf("%c", items[order[i]]);
        printf("\n");
        return;
    }

    for (int i = 0; i < N; i++) {
        if (used[i]) continue;           /* 제약: 이미 쓴 원소 */
        used[i] = 1;                     /* 선택 */
        order[pos] = i;
        permutations(pos + 1);           /* 재귀 */
        used[i] = 0;                     /* 취소! (다음 갈래를 위해) */
    }
}

int main(void) {
    printf("원소: {A, B, C, D}\n");
    printf("=====================================\n");

    printf("\n=== 1. 모든 부분집합 (2^4 = 16개) ===\n");
    count = 0;
    subsets(0);
    printf("총 %d개\n", count);

    printf("\n=== 2. 4개 중 2개 조합 (4C2 = 6개) ===\n");
    count = 0;
    combinations(0, 0, 2);
    printf("총 %d개\n", count);

    printf("\n=== 3. 모든 순열 (4! = 24개) ===\n");
    count = 0;
    permutations(0);
    printf("총 %d개\n", count);

    printf("\n=== 세 패턴의 공통 리듬 ===\n");
    printf("  선택   (in_set=1 / chosen에 추가 / used=1)\n");
    printf("  재귀   (다음 단계로)\n");
    printf("  취소   (in_set=0 / 덮어쓰기 / used=0)  <- 백트래킹!\n");

    printf("\n=== 차이는 '제약' 하나 ===\n");
    printf("  부분집합: 제약 없음 (2갈래씩)\n");
    printf("  조합: start 이후만 (순서 다른 중복 방지)\n");
    printf("  순열: used 검사 (같은 원소 재사용 방지)\n");

    printf("\n=== 크기 감각 (지수 폭발 주의보) ===\n");
    printf("  n=10: 부분집합 1024, 순열 362만\n");
    printf("  n=20: 부분집합 100만, 순열 2해(10^18)!!\n");
    printf("  -> 백트래킹은 n이 작을 때의 무기. 크면 DP/탐욕/근사를 찾아라\n");
    return 0;
}

$ ./build/combinations
원소: {A, B, C, D}
=====================================

=== 1. 모든 부분집합 (2^4 = 16개) ===
  { A B C D }
  { A B C }
  { A B D }
  { A B }
  { A C D }
  { A C }
  { A D }
  { A }
  { B C D }
  { B C }
  { B D }
  { B }
  { C D }
  { C }
  { D }
  { }
총 16개

=== 2. 4개 중 2개 조합 (4C2 = 6개) ===
  { A B }
  { A C }
  { A D }
  { B C }
  { B D }
  { C D }
총 6개

=== 3. 모든 순열 (4! = 24개) ===
  ABCD
  ABDC
  ACBD
  ...
  DCBA
총 24개
...

6.2 부분집합: 넣거나, 말거나

void subsets(int index) {
    if (index == N) { /* 출력 */ return; }   /* 목표: 모든 원소에 대해 결정했다 */

    in_set[index] = 1;           /* 갈래 1: index번 원소를 넣는다 */
    subsets(index + 1);
    in_set[index] = 0;           /* 취소하고 */
    subsets(index + 1);          /* 갈래 2: 안 넣는다 */
}

원소마다 “넣거나 말거나” 두 갈래로 갈라집니다. 제약이 없습니다. 원소 4개면 2×2×2×2 = 2⁴ = 16개. 출력 순서를 보면 규칙이 보입니다. A를 넣은 것들이 먼저(갈래 1이 먼저 실행되니까), 그 안에서 B를 넣은 것들이 먼저… 마지막이 빈 집합 { }입니다.

“선택 → 재귀 → 취소 → 재귀”의 가장 순수한 형태입니다. 여기서 취소(in_set[index] = 0)는 단순히 “다음 갈래를 시작하기 전에 원상복구”입니다.

6.3 조합: start 하나로 순서 중복 없애기

void combinations(int start, int picked, int k) {
    if (picked == k) { /* 출력 */ return; }  /* 목표: k개 골랐다 */

    for (int i = start; i < N; i++) {        /* start 이전 원소는 후보에서 제외 */
        chosen[picked] = i;                  /* 선택 */
        combinations(i + 1, picked + 1, k);  /* 다음은 i 다음부터만 */
    }
}

조합은 순서를 구분하지 않습니다. {A, B}와 {B, A}는 같은 조합입니다. 그런데 아무 생각 없이 “아직 안 고른 것 중 하나”를 고르면 둘 다 나옵니다. 이 중복을 막는 장치가 start입니다.

다음 원소를 항상 i + 1부터 고르게 하면, 뽑히는 인덱스가 항상 증가합니다. {A, B}(0, 1)는 나오지만 {B, A}(1, 0)는 나올 수 없습니다. 그래서 각 조합이 정확히 한 번씩만 나옵니다. 4개 중 2개면 ₄C₂ = 6개입니다.

“취소”가 없는 것도 보세요. chosen[picked]는 다음 반복에서 덮어쓰므로 N-Queens처럼 생략됐습니다.

6.4 순열: used 검사, 그리고 취소를 빼먹으면

void permutations(int pos) {
    if (pos == N) { /* 출력 */ return; }     /* 목표: 모든 자리를 채웠다 */

    for (int i = 0; i < N; i++) {            /* 모든 원소가 후보 */
        if (used[i]) continue;               /* 제약: 이미 쓴 원소는 건너뜀 */
        used[i] = 1;                         /* 선택 */
        order[pos] = i;
        permutations(pos + 1);               /* 재귀 */
        used[i] = 0;                         /* 취소! */
    }
}

순열은 순서를 구분하니 모든 위치에서 모든 원소가 후보입니다. 단, 이미 쓴 원소는 제외해야 하니 used[]로 표시합니다. 4개면 4! = 4×3×2×1 = 24개.

여기서는 취소 used[i] = 0이 명시적으로 필요합니다. 이걸 빼먹으면 어떻게 될까요? 원소 3개 {A, B, C}로 실험해 봤습니다.

[취소 있음]
  ABC
  ACB
  BAC
  BCA
  CAB
  CBA
총 6개

[취소 없음: used[i]=0 을 빼먹음]
  ABC
총 1개

ABC 하나만 나오고 끝납니다. 첫 순열을 만드는 동안 A, B, C가 전부 used = 1이 됐고, 되돌아온 뒤에도 아무도 풀어 주지 않으니 두 번째 자리부터는 고를 원소가 하나도 남지 않은 것입니다. 오류 메시지도 없이 조용히 답이 줄어듭니다. 백트래킹에서 가장 흔한 버그입니다. “선택했으면 반드시 취소한다”를 리듬으로 외워 두세요.

정리하면 이렇습니다.

	제약	개수	n=20일 때
부분집합	없음	2ⁿ	약 100만
조합 (k=10)	`start` 이후만	ₙCₖ	약 18만
순열	`used` 검사	n!	약 2.4 × 10¹⁸

6.5 크기 감각을 몸에 익히기

마지막 출력이 중요한 경고를 담고 있습니다.

n=10: 부분집합 1024, 순열 362만
n=20: 부분집합 100만, 순열 2해(10^18)!!

n=20의 순열은 약 2.4×10¹⁸개입니다. 1초에 10억 개를 처리해도 77년이 걸립니다. 컴퓨터가 빨라져도 해결되지 않는 규모죠.

알고리즘을 고를 때 이 감각이 있어야 합니다. 1초에 약 10⁸~10⁹번의 간단한 연산을 한다고 보고, 대략 이렇게 기억하세요.

복잡도	1초 안에 가능한 n (대략)	이번 강좌의 예
O(n!)	10~11	순열 생성, TSP 전수 탐색
O(2ⁿ)	20~25	부분집합, 순수 재귀 피보나치
O(n³)	수백	플로이드-워셜
O(n²)	수만	버블 정렬, LCS
O(n log n)	수백만	병합 정렬, 퀵 정렬
O(n)	수억	선형 탐색, 테이블 DP

문제를 보고 n의 크기를 확인하면 쓸 수 있는 알고리즘의 범위가 먼저 좁혀집니다. “n이 20 이하”라는 조건이 보이면 출제자가 지수 시간 풀이를 허락한 것이고, “n이 10만”이면 O(n log n) 이하를 요구하는 것이죠. 코딩 테스트에서 특히 유용한 판단법입니다.

실험: 바꾸면 어떻게 될까

combinations의 재귀 호출에서 i + 1을 start로 바꿔 보세요. 같은 원소를 다시 고를 수 있게 되어 {A, A}, {A, B}, … 같은 중복 조합이 나옵니다. 몇 개인지 세고, 왜 그 수인지 생각해 보세요(₅C₂ = 10개입니다).
i + 1을 0으로 바꾸면 순서까지 구분하는 중복 순열이 됩니다. 4² = 16개가 나옵니다. 매개변수 하나가 “조합 / 중복 조합 / 중복 순열”을 가릅니다.
N을 10으로 바꾸고 순열을 출력 없이 세어 보세요(출력 줄을 주석 처리). 362만 개를 세는 데 시간이 얼마나 걸리는지 재고, N=11, 12로 늘리며 몇 배씩 늘어나는지 확인하세요. n!의 성장을 몸으로 느끼는 실험입니다.

7. 미로: 백트래킹 vs BFS 재대결

같은 문제를 두 방법으로 풀면 각자의 성격이 선명해집니다. 14주차의 BFS와 이번 주의 백트래킹을 미로에서 맞붙여 봅시다.

examples/maze_backtrack.c:

/*
 * maze_backtrack.c - 미로 탐색: 백트래킹과 BFS의 재회
 * 17주차: 고급 알고리즘과 최적화
 *
 * 미로에서 입구 -> 출구 길찾기를 두 방법으로:
 *
 * 1. 백트래킹(DFS): 아무 길이나 가보고 막히면 되돌아온다
 *    -> "길이 있는가?" + 아무 경로 하나. 메모리 절약.
 * 2. BFS(14주차): 가까운 곳부터 물결처럼
 *    -> "최단" 경로 보장!
 *
 * 같은 미로에서 두 경로를 비교하면 차이가 한눈에 보입니다.
 */
#include <stdio.h>
#include <string.h>

#define H 10
#define W 19

/* #=벽, 공백=길, S=입구, E=출구 */
static const char *maze_src[H] = {
    "S            #    #",
    "#### # # ### # ## #",
    "#    # # # # #  # #",
    "# ###### # # ## # #",
    "#      # # #  # # #",
    "###### # # ## # # #",
    "#    #   #  # #   #",
    "# ## # # ## # ### #",
    "#  #   #    #     E",
    "###################",
};

static char grid[H][W + 1];
static int visited[H][W];
static int path_mark[H][W];

static const int dr[] = {-1, 1, 0, 0};
static const int dc[] = {0, 0, -1, 1};

void reset(void) {
    for (int r = 0; r < H; r++) strcpy(grid[r], maze_src[r]);
    memset(visited, 0, sizeof(visited));
    memset(path_mark, 0, sizeof(path_mark));
}

void print_maze(const char *title) {
    printf("%s\n", title);
    for (int r = 0; r < H; r++) {
        printf("  ");
        for (int c = 0; c < W; c++) {
            if (grid[r][c] == 'S' || grid[r][c] == 'E') {
                printf("%c", grid[r][c]);
            } else if (path_mark[r][c]) {
                printf("o");                 /* 경로 표시 */
            } else {
                printf("%c", grid[r][c] == '#' ? '#' : ' ');
            }
        }
        printf("\n");
    }
}

static long steps;

/* ---------- 1. 백트래킹 (DFS): 되면 1, 막히면 0 ---------- */
int solve_dfs(int r, int c) {
    if (r < 0 || r >= H || c < 0 || c >= W) return 0;
    if (grid[r][c] == '#' || visited[r][c]) return 0;

    steps++;
    visited[r][c] = 1;
    path_mark[r][c] = 1;                     /* 일단 경로에 넣어본다 */

    if (grid[r][c] == 'E') return 1;         /* 출구! */

    for (int d = 0; d < 4; d++) {
        if (solve_dfs(r + dr[d], c + dc[d])) return 1;
    }

    path_mark[r][c] = 0;                     /* 막다른 길: 경로에서 취소! */
    return 0;                                /* <- 이것이 백트래킹 */
}

/* ---------- 2. BFS: 최단 경로 (14주차 재활용) ---------- */
int solve_bfs(int sr, int sc) {
    typedef struct { int r, c; } Pos;
    Pos queue[H * W];
    Pos parent[H][W];
    int front = 0, rear = 0;

    memset(visited, 0, sizeof(visited));
    visited[sr][sc] = 1;
    queue[rear++] = (Pos){sr, sc};
    parent[sr][sc] = (Pos){-1, -1};

    int er = -1, ec = -1;
    while (front < rear) {
        Pos p = queue[front++];
        steps++;
        if (grid[p.r][p.c] == 'E') { er = p.r; ec = p.c; break; }

        for (int d = 0; d < 4; d++) {
            int nr = p.r + dr[d], nc = p.c + dc[d];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (grid[nr][nc] == '#' || visited[nr][nc]) continue;
            visited[nr][nc] = 1;
            parent[nr][nc] = p;
            queue[rear++] = (Pos){nr, nc};
        }
    }
    if (er < 0) return 0;

    /* 경로 복원 */
    for (int r = er, c = ec; r != -1; ) {
        path_mark[r][c] = 1;
        Pos p = parent[r][c];
        r = p.r; c = p.c;
    }
    return 1;
}

int path_length(void) {
    int len = 0;
    for (int r = 0; r < H; r++)
        for (int c = 0; c < W; c++) len += path_mark[r][c];
    return len;
}

int main(void) {
    printf("미로 탐색: 백트래킹 vs BFS\n");
    printf("=====================================\n\n");

    reset();
    print_maze("[원본 미로] S=입구, E=출구");

    printf("\n");
    reset();
    steps = 0;
    if (solve_dfs(0, 0)) {
        char title[80];
        snprintf(title, sizeof(title),
                 "[백트래킹] 경로 길이 %d, 방문 %ld칸 (아무 경로나 하나)",
                 path_length(), steps);
        print_maze(title);
    } else {
        printf("[백트래킹] 길 없음!\n");
    }

    printf("\n");
    reset();
    steps = 0;
    if (solve_bfs(0, 0)) {
        char title[80];
        int len = path_length();
        snprintf(title, sizeof(title),
                 "[BFS] 경로 길이 %d, 방문 %ld칸 (최단 보장!)", len, steps);
        print_maze(title);
    }

    printf("\n비교 정리:\n");
    printf("1. 백트래킹(DFS): 찾으면 즉시 종료. 경로가 최단이란 보장 없음\n");
    printf("   - path_mark 취소(=0)가 백트래킹의 핵심 동작!\n");
    printf("2. BFS: 층층이 퍼져서 처음 닿은 것이 곧 최단 (14주차 성질)\n");
    printf("3. 용도: 존재 여부/모든 해 -> 백트래킹, 최단 -> BFS\n");
    printf("4. 게임 AI 길찾기(A*)는 BFS + 방향 힌트의 확장판\n");
    return 0;
}

$ ./build/maze_backtrack
미로 탐색: 백트래킹 vs BFS
=====================================

[원본 미로] S=입구, E=출구
  S            #    #
  #### # # ### # ## #
  #    # # # # #  # #
  # ###### # # ## # #
  #      # # #  # # #
  ###### # # ## # # #
  #    #   #  # #   #
  # ## # # ## # ### #
  #  #   #    #     E
  ###################

[백트래킹] 경로 길이 45, 방문 81칸 (아무 경로나 하나)
  Soooo   ooooo#    #
  ####o# #o###o# ## #
  #oooo# #o# #o#  # #
  #o######o# #o## # #
  #oooooo#o# #oo# # #
  ######o#o# ##o# # #
  #    #ooo#  #o#   #
  # ## # # ## #o### #
  #  #   #    #oooooE
  ###################

[BFS] 경로 길이 27, 방문 73칸 (최단 보장!)
  Soooooooooooo#    #
  #### # # ###o# ## #
  #    # # # #o#  # #
  # ###### # #o## # #
  #      # # #oo# # #
  ###### # # ##o# # #
  #    #   #  #o#   #
  # ## # # ## #o### #
  #  #   #    #oooooE
  ###################
...

백트래킹으로 미로 풀기

백트래킹으로 미로 풀기

그림이 모든 것을 말해 줍니다. 백트래킹은 왼쪽 아래로 한참 돌아가는 45칸짜리 경로를 찾았고, BFS는 위쪽으로 곧장 가는 27칸짜리 최단 경로를 찾았습니다. 둘 다 “길을 찾았다”는 점은 같습니다.

7.1 백트래킹의 상징적인 한 줄

int solve_dfs(int r, int c) {
    if (r < 0 || r >= H || c < 0 || c >= W) return 0;   /* 판 밖 */
    if (grid[r][c] == '#' || visited[r][c]) return 0;    /* 벽이거나 이미 온 곳 */

    steps++;
    visited[r][c] = 1;
    path_mark[r][c] = 1;                     /* 일단 경로에 넣어본다 */

    if (grid[r][c] == 'E') return 1;         /* 출구! 성공을 위로 전파 */

    for (int d = 0; d < 4; d++) {            /* 상, 하, 좌, 우 */
        if (solve_dfs(r + dr[d], c + dc[d])) return 1;
    }

    path_mark[r][c] = 0;                     /* 막다른 길: 경로에서 취소! */
    return 0;                                /* <- 이것이 백트래킹 */
}

path_mark[r][c] = 0; 이 한 줄이 백트래킹의 정체입니다. “여기로 와 봤는데 출구로 못 가더라. 경로에서 빼자.”

함수의 반환값이 “성공(1)/실패(0)”인 점을 보세요. 네 방향 중 하나라도 성공하면 즉시 1을 돌려주고, 그러면 그 위의 호출도 1을 돌려주고… 성공이 입구까지 전파됩니다. 네 방향 모두 실패했을 때만 자기 칸의 표시를 지우고 0을 돌려줍니다. 그래서 마지막에 path_mark가 1로 남은 칸들은 실제로 출구까지 이어진 칸들뿐입니다. 막다른 길로 들어갔다 나온 흔적은 전부 지워졌죠. 출력에서 o 표시가 깔끔한 한 줄로 나오는 이유입니다.

dr[], dc[] 배열은 14주차에서 쓴 방향 표입니다. d = 0이면 위(-1, 0), 1이면 아래(1, 0), 2면 왼쪽, 3이면 오른쪽. 네 개의 if를 쓰는 대신 반복문 하나로 네 방향을 도는 관용구입니다.

7.2 visited와 path_mark를 따로 두는 이유

visited: 한 번 가 본 칸. 취소하지 않습니다. 이미 실패한 칸을 다시 시도할 이유가 없고, 취소하면 같은 자리를 빙빙 도는 무한 루프에 빠집니다.
path_mark: 현재 경로에 포함된 칸. 실패하면 취소합니다.

“탐색 기록”과 “현재 상태”를 분리하는 전형적인 설계입니다. 백트래킹 문제를 짤 때 “이 표시는 되돌려야 하나?”를 항상 자문하세요. 되돌리면 안 되는 것(방문 기록)과 되돌려야 하는 것(현재 선택)이 섞이면 무한 루프 아니면 오답입니다.

7.3 언제 무엇을 쓸까

	백트래킹 (DFS)	BFS
찾는 것	아무 경로 하나	최단 경로
종료	찾으면 즉시	최단 확정 시
메모리	경로 깊이만큼 (재귀 스택)	한 층의 칸 수만큼 (큐)
확장성	모든 해 열거, 제약 추가 용이	최단 보장

“길이 있는가?” → 둘 다 가능. 백트래킹이 메모리를 덜 씁니다.
“최단 경로는?” → BFS (14주차의 그 성질).
“모든 경로를 나열하라” → 백트래킹.
“조건을 만족하는 경로만” → 백트래킹 (제약을 가지치기로 넣기 쉬움).

게임의 길찾기에 쓰이는 A* 알고리즘은 BFS에 “목적지 방향”이라는 힌트를 더한 확장판입니다. 14주차 다익스트라의 우선순위 큐에 휴리스틱(어림 거리)을 더한 것이죠.

실험: 바꾸면 어떻게 될까

dr[], dc[]의 순서를 바꿔 오른쪽을 먼저 시도하게 해 보세요. dr[] = {0, 0, -1, 1}, dc[] = {1, -1, 0, 0}(오른쪽, 왼쪽, 위, 아래 순)으로 바꾸면 백트래킹이 27칸 경로를 27칸만 방문하고 찾습니다. 이 미로에서는 출구가 오른쪽 아래에 있어서 오른쪽부터 가면 헤매지 않기 때문입니다. 반대로 아래를 먼저 시도하면({1, -1, 0, 0}, {0, 0, 1, -1}) 88칸을 헤맵니다. 백트래킹의 경로는 탐색 순서에 따라 달라진다는 것을 확인하는 실험입니다. BFS의 경로 길이는 순서를 바꿔도 27로 같습니다.
path_mark[r][c] = 0; 줄을 지우고 실행해 보세요. 출구까지 이어진 경로뿐 아니라 들렀던 막다른 길까지 전부 o로 찍힙니다. 경로 길이도 방문 칸 수(81)와 같아집니다.
미로의 출구 E를 벽 #으로 바꿔 보세요. 두 알고리즘 모두 “길 없음”을 판정합니다. 이때 방문 칸 수를 보면 둘 다 갈 수 있는 모든 칸을 다 가 봐야 한다는 것을 알 수 있습니다. 답이 없을 때는 백트래킹도 BFS도 전수 탐색이 됩니다.

8. 분할 정복: 반으로 쪼개는 수학

8.1 이미 만난 패러다임

분할 정복(divide and conquer) 은 이미 여러 번 만났습니다. 병합 정렬은 배열을 반으로 나눠 각각 정렬한 뒤 합쳤고, 이진 탐색은 범위를 반으로 줄여 가며 찾았습니다. “문제를 같은 모양의 작은 문제로 쪼개고, 각각 풀고, 합친다”가 분할 정복입니다. 1절에서 말했듯 부분 문제가 겹치지 않는다는 점이 DP와 다릅니다.

오늘은 이것을 계산에 적용합니다. 3의 45제곱을 구하려면 곱셈이 몇 번 필요할까요? 45번? 아닙니다. 10번이면 됩니다.

examples/divide_conquer.c:

/*
 * divide_conquer.c - 분할 정복: 빠른 거듭제곱과 행렬의 마법
 * 17주차: 고급 알고리즘과 최적화
 *
 * 분할 정복 = 문제를 반으로 쪼개 각각 풀고 합치기.
 * 이미 병합 정렬(15주차)과 이진 탐색에서 만났습니다.
 * 오늘은 "계산"에 적용합니다:
 *
 * 1. 빠른 거듭제곱: x^n을 O(log n)에
 *    x^10 = (x^5)^2, x^5 = x * (x^2)^2 ... 절반씩!
 *
 * 2. 행렬 거듭제곱으로 피보나치 O(log n)!
 *    [F(n+1) F(n)]   [1 1]^n
 *    [F(n) F(n-1)] = [1 0]     <- 거듭제곱이니 위 기법 적용!
 *
 * 3. 마스터 정리: 분할 정복의 시간복잡도 공식
 */
#include <stdio.h>

#define MOD 1000000007ULL        /* 큰 결과는 나머지로 (오버플로우 방지) */

static long multiply_count;

/* ---------- 1. 빠른 거듭제곱 ---------- */
unsigned long long slow_pow(unsigned long long x, unsigned long long n) {
    unsigned long long result = 1;
    for (unsigned long long i = 0; i < n; i++) {
        result = (result * x) % MOD;
        multiply_count++;
    }
    return result;
}

unsigned long long fast_pow(unsigned long long x, unsigned long long n) {
    if (n == 0) return 1;
    unsigned long long half = fast_pow(x, n / 2);    /* 반으로 분할! */
    multiply_count++;
    unsigned long long result = (half * half) % MOD;
    if (n % 2 == 1) {
        multiply_count++;
        result = (result * x) % MOD;
    }
    return result;
}

/* ---------- 2. 2x2 행렬 거듭제곱 피보나치 ---------- */
typedef struct {
    unsigned long long a, b, c, d;   /* [a b; c d] */
} Mat2;

Mat2 mat_mul(Mat2 x, Mat2 y) {
    multiply_count++;
    return (Mat2){
        (x.a * y.a + x.b * y.c) % MOD,
        (x.a * y.b + x.b * y.d) % MOD,
        (x.c * y.a + x.d * y.c) % MOD,
        (x.c * y.b + x.d * y.d) % MOD,
    };
}

Mat2 mat_pow(Mat2 m, unsigned long long n) {
    if (n == 1) return m;
    Mat2 half = mat_pow(m, n / 2);
    Mat2 result = mat_mul(half, half);
    if (n % 2 == 1) result = mat_mul(result, m);
    return result;
}

unsigned long long fib_matrix(unsigned long long n) {
    if (n == 0) return 0;
    Mat2 base = {1, 1, 1, 0};
    Mat2 result = mat_pow(base, n);
    return result.b;             /* [1 1;1 0]^n의 b 자리 = F(n) */
}

int main(void) {
    printf("=== 1. 빠른 거듭제곱: 3^45 (mod 큰 소수) ===\n");

    multiply_count = 0;
    unsigned long long s = slow_pow(3, 45);
    printf("반복 곱셈: %llu (곱셈 %ld번)\n", s, multiply_count);

    multiply_count = 0;
    unsigned long long f = fast_pow(3, 45);
    printf("분할 정복: %llu (곱셈 %ld번!)\n", f, multiply_count);
    printf("일치: %s\n", s == f ? "OK" : "버그!");

    printf("\n지수가 커지면?\n");
    multiply_count = 0;
    fast_pow(7, 1000000000ULL);
    printf("7^10억: 곱셈 딱 %ld번 (반복이면 10억 번!)\n", multiply_count);
    printf("(RSA 암호가 이 기법 없이는 불가능)\n");

    printf("\n=== 2. 행렬로 피보나치 O(log n) ===\n");
    printf("이번 주 첫 예제에서 DP로 O(n)까지 왔는데, 더 갈 수 있다!\n\n");
    printf("   [F(n+1) F(n)  ]   [1 1]^n\n");
    printf("   [F(n)   F(n-1)] = [1 0]\n\n");

    for (int n = 10; n <= 90; n += 40) {
        multiply_count = 0;
        unsigned long long fib = fib_matrix(n);
        printf("F(%2d) mod p = %-12llu (행렬 곱 %ld번)\n",
               n, fib, multiply_count);
    }
    multiply_count = 0;
    unsigned long long huge = fib_matrix(1000000000000000000ULL);
    /* 계산을 먼저 끝내고 printf 에 넘긴다. 인자 안에서 부르면 multiply_count 를
     * 계산 전에 읽을 수도 있다 (인자 평가 순서는 정해져 있지 않다 - 9주차 file_seek) */
    printf("F(10^18) mod p = %llu (행렬 곱 %ld번!!)\n", huge, multiply_count);
    printf("(10^18번째 피보나치를 눈 깜짝할 새에 - 분할 정복의 극한)\n");

    printf("\n=== 3. 마스터 정리: 분할 정복의 시간 공식 ===\n");
    printf("T(n) = a*T(n/b) + O(n^d)  \"a개로 쪼개고, 합치는 데 n^d\"\n\n");
    printf("  a=1, b=2, d=0 (이진 탐색)     -> O(log n)\n");
    printf("  a=2, b=2, d=1 (병합 정렬)     -> O(n log n)\n");
    printf("  a=1, b=2, d=0 (빠른 거듭제곱)  -> O(log n)\n");
    printf("  a=7, b=2, d=2 (슈트라센 행렬곱)-> O(n^2.81)\n");
    printf("  a=3, b=2, d=1 (카라추바 곱셈) -> O(n^1.58)\n");
    printf("\n(빠른 거듭제곱은 절반 '하나'만 재귀하므로 a=1. 두 번 부르면 a=2가 되어 O(n)!)\n");

    printf("\n심화 예고 - 곱셈도 쪼갤 수 있다:\n");
    printf("카라추바: 큰 수 곱셈을 4번 대신 3번의 반쪽 곱셈으로\n");
    printf("(x1*B+x0)(y1*B+y0)에서 (x1+x0)(y1+y0)를 재활용하는 트릭.\n");
    printf("암호학의 큰 수 연산 라이브러리가 실제로 쓰는 기법입니다.\n");
    return 0;
}

$ ./build/divide_conquer
=== 1. 빠른 거듭제곱: 3^45 (mod 큰 소수) ===
반복 곱셈: 644897553 (곱셈 45번)
분할 정복: 644897553 (곱셈 10번!)
일치: OK

지수가 커지면?
7^10억: 곱셈 딱 43번 (반복이면 10억 번!)
(RSA 암호가 이 기법 없이는 불가능)

=== 2. 행렬로 피보나치 O(log n) ===
이번 주 첫 예제에서 DP로 O(n)까지 왔는데, 더 갈 수 있다!

   [F(n+1) F(n)  ]   [1 1]^n
   [F(n)   F(n-1)] = [1 0]

F(10) mod p = 55           (행렬 곱 4번)
F(50) mod p = 586268941    (행렬 곱 7번)
F(90) mod p = 210345902    (행렬 곱 9번)
F(10^18) mod p = 209783453 (행렬 곱 82번!!)
(10^18번째 피보나치를 눈 깜짝할 새에 - 분할 정복의 극한)

=== 3. 마스터 정리: 분할 정복의 시간 공식 ===
T(n) = a*T(n/b) + O(n^d)  "a개로 쪼개고, 합치는 데 n^d"

  a=1, b=2, d=0 (이진 탐색)     -> O(log n)
  a=2, b=2, d=1 (병합 정렬)     -> O(n log n)
  a=1, b=2, d=0 (빠른 거듭제곱)  -> O(log n)
  a=7, b=2, d=2 (슈트라센 행렬곱)-> O(n^2.81)
  a=3, b=2, d=1 (카라추바 곱셈) -> O(n^1.58)
...

8.2 빠른 거듭제곱

unsigned long long fast_pow(unsigned long long x, unsigned long long n) {
    if (n == 0) return 1;                            /* 기저: x^0 = 1 */
    unsigned long long half = fast_pow(x, n / 2);    /* x^(n/2) 을 한 번만 계산 */
    unsigned long long result = (half * half) % MOD; /* 제곱하면 x^(n/2*2) */
    if (n % 2 == 1) {                                /* n이 홀수면 x 하나가 모자라니 */
        result = (result * x) % MOD;                 /* 한 번 더 곱한다 */
    }
    return result;
}

핵심 아이디어는 중학교 지수법칙입니다. x¹⁰ = (x⁵)²이고 x⁵ = (x²)² × x입니다. 지수가 짝수면 절반의 제곱, 홀수면 절반의 제곱에 x 하나를 더 곱합니다. 3⁴⁵를 이 방법으로 계산하면 이렇게 됩니다.

호출	n	하는 일	곱셈
fast_pow(3, 45)	45 (홀수)	(3²²)² × 3	2번
fast_pow(3, 22)	22 (짝수)	(3¹¹)²	1번
fast_pow(3, 11)	11 (홀수)	(3⁵)² × 3	2번
fast_pow(3, 5)	5 (홀수)	(3²)² × 3	2번
fast_pow(3, 2)	2 (짝수)	(3¹)²	1번
fast_pow(3, 1)	1 (홀수)	(3⁰)² × 3	2번
fast_pow(3, 0)	0	1 (기저)	0번

합쳐서 10번입니다. 재귀 한 단계마다 n이 절반이 되니 단계 수는 log₂ n이고, 단계마다 곱셈이 많아야 2번이니 전체는 O(log n) 입니다. 7^10억은 log₂(10⁹) ≈ 30단계에 곱셈 43번입니다. 반복문이었다면 10억 번이었을 계산이죠.

half를 변수에 담는 것이 이 함수의 전부라고 해도 과언이 아닙니다. 만약 이렇게 썼다면 어떻게 될까요?

    result = (fast_pow(x, n / 2) * fast_pow(x, n / 2)) % MOD;   /* 같은 계산을 두 번! */

직접 세어 봤습니다.

n = 2^20 = 1048576
half 를 변수에 담음      : 650380217, 곱셈 22번
fast_pow 를 두 번 호출   : 650380217, 곱셈 3145727번 (n 과 비슷! O(n) 으로 후퇴)

답은 같지만 곱셈이 22번에서 314만 번이 됐습니다. 단계마다 호출이 2배씩 늘어 2^(log n) = n번이 되기 때문입니다. 1절의 순수 재귀 피보나치와 똑같은 함정입니다. “한 번 계산한 것은 변수에 담는다”, DP의 정신이 여기서도 적용됩니다.

% MOD를 매 단계 적용하는 이유도 보세요. 거듭제곱은 순식간에 천문학적 크기가 되므로 1.6절 실험에서 본 오버플로가 바로 일어납니다. 그런데 모듈러 산술에는 (a × b) mod m = ((a mod m) × (b mod m)) mod m이라는 성질이 있어서, 중간중간 나머지를 취해도 최종 나머지는 같습니다. MOD가 10억 7(약 2³⁰)이라 나머지끼리 곱해도 2⁶⁰ 정도라 unsigned long long(2⁶⁴)에 들어갑니다. 1000000007은 소수이면서 이 조건을 만족해서 경시대회와 암호학에서 관습적으로 쓰는 값입니다.

이 기법이 RSA 암호의 기반입니다. RSA는 메시지^지수 mod n을 계산하는데, 지수가 수백 비트짜리 거대한 수입니다. 빠른 거듭제곱이 없으면 암호화 한 번에 우주의 나이가 걸립니다. 24주차 보안 프로그래밍에서는 RSA 자체를 구현하지는 않고, 해시와 HMAC 같은 암호 도구를 올바르게 쓰는 법을 다룹니다.

8.3 행렬로 피보나치를 O(log n)에

이 예제의 백미입니다. 1절에서 피보나치를 O(2ⁿ)에서 O(n)까지 개선했는데, 더 갈 수 있습니다.

[F(n+1) F(n)  ]   [1 1]^n
[F(n)   F(n-1)] = [1 0]

이 항등식이 성립합니다(n에 대한 귀납법으로 증명됩니다. n=1일 때 [1 1; 1 0]이 [F(2) F(1); F(1) F(0)] = [1 1; 1 0]으로 맞고, 한 번 더 곱하면 다음 항이 나옵니다). 그렇다면 피보나치 계산이 행렬의 거듭제곱이 되고, 거듭제곱은 방금 배운 대로 O(log n)입니다.

mat_pow는 fast_pow와 구조가 같습니다. 숫자 대신 2×2 행렬을 제곱할 뿐입니다. mat_mul이 행렬 곱 한 번(숫자 곱셈 8번)입니다.

F(10^18) mod p = 209783453 (행렬 곱 82번!!)

10¹⁸번째 피보나치 수의 나머지를 행렬 곱 82번으로 계산합니다. log₂(10¹⁸) ≈ 60단계에 단계마다 1~2번이니 맞는 숫자입니다.

함정: 이 줄은 원래 “행렬 곱 0번”을 찍었습니다. 예제를 처음 만들었을 때 출력이 “행렬 곱 0번!!”이었습니다. 원인은 printf("...", fib_matrix(...), multiply_count)처럼 함수 호출과 변수를 같은 인자 목록에 넣은 것입니다. C는 인자를 어떤 순서로 계산할지 정해 두지 않아서, GCC는 multiply_count(아직 0)를 먼저 읽고 나서 fib_matrix를 불렀습니다. 9주차 file_seek에서 fgetc와 ftell을 한 printf에 넣어 겪은 것과 같은 버그입니다. 그래서 이 예제는 계산 결과를 변수에 먼저 받고 printf에 넘깁니다.

여기서 배울 교훈이 있습니다.

같은 문제라도 더 좋은 구조를 찾으면 또 빨라진다.

피보나치는 O(2ⁿ) → O(n) → O(log n)으로 세 번 개선됐습니다. “이 정도면 최적이겠지”라고 멈추지 않는 태도가 알고리즘 설계의 자세입니다.

8.4 마스터 정리

분할 정복 알고리즘의 시간 복잡도를 구하는 공식이 마스터 정리(master theorem) 입니다.

T(n) = a·T(n/b) + O(n^d)

a: 몇 개의 부분 문제로 쪼개는가
b: 각 부분 문제의 크기는 몇 분의 1인가
n^d: 쪼개고 합치는 데 드는 비용

세 경우로 나뉩니다.

d > log_b(a) → O(n^d) (합치는 비용이 지배)
d = log_b(a) → O(n^d log n) (균형)
d < log_b(a) → O(n^(log_b a)) (쪼개는 비용이 지배)

우리가 배운 알고리즘들을 넣어 봅시다.

알고리즘	a	b	d	log_b(a)	경우	결과
이진 탐색	1	2	0	0	d = log	O(log n)
병합 정렬	2	2	1	1	d = log	O(n log n)
빠른 거듭제곱	1	2	0	0	d = log	O(log n)
슈트라센 행렬 곱	7	2	2	2.81	d < log	O(n^2.81)
카라추바 곱셈	3	2	1	1.58	d < log	O(n^1.58)

병합 정렬의 O(n log n) 을 직접 확인해 보세요. a=2(반으로 쪼개 둘 다 재귀), b=2, d=1(병합이 O(n))입니다. log₂(2) = 1 = d이므로 두 번째 경우, O(n¹ log n)입니다. 15주차에 “반으로 나누니까 log n 단계, 각 단계가 O(n)”이라고 설명했던 것을 공식으로 확인한 셈이죠.

빠른 거듭제곱은 a=1입니다. 절반 크기 문제를 하나만 재귀하니까요. 위 실험에서 fast_pow를 두 번 부른 버전은 a=2가 되어, log₂(2) = 1 > d = 0이니 O(n^1) = O(n)입니다. 마스터 정리가 “왜 314만 번이 됐는지”를 정확히 예측합니다.

표의 아래 두 줄이 흥미롭습니다. 슈트라센은 행렬 곱의 부분 곱셈을 8번에서 7번으로 줄여 O(n³)을 O(n^2.81)로 낮췄고, 카라추바는 큰 수 곱셈을 4번에서 3번으로 줄여 O(n²)을 O(n^1.58)로 낮췄습니다. 곱셈 횟수 하나를 줄인 것이 지수를 바꿉니다. a가 지수 자리에 들어가기 때문이죠. 마스터 정리를 알면 이런 개선의 가치를 정량적으로 볼 수 있습니다.

실험: 바꾸면 어떻게 될까

slow_pow(3, 45)의 % MOD를 빼고 결과를 보세요. 3⁴⁵ ≈ 2.95×10²¹는 unsigned long long의 최댓값(약 1.8×10¹⁹)을 넘습니다. 부호 없는 정수라 2주차에서 배운 대로 오류 없이 2⁶⁴으로 나눈 나머지가 됩니다. 나머지 연산을 매 단계 하는 이유입니다.
fast_pow의 half를 위의 “두 번 호출” 형태로 바꾸고 7^10억을 돌려 보세요. 곱셈이 10억 번이 되어 몇 초가 걸립니다. 마스터 정리로 예측한 대로 O(n)입니다.
fib_matrix(93)의 나머지를 구하지 않도록 MOD를 아주 크게(예: 1ULL << 63) 바꿔 보세요. 1.6절에서 본 오버플로가 행렬 안에서 일어납니다. 나머지 없이 정확한 F(93)을 구하려면 unsigned long long으로도 부족하고, 10주차 이후 배운 동적 배열이나 연결 리스트로 큰 수를 자릿수 단위로 직접 표현해야 합니다.

9. 탐욕법: 증명된 무대에서만 최강

9.1 동전에서 배신을 봤지만

4절에서 탐욕이 배신하는 것을 봤습니다. 그렇다고 탐욕이 나쁜 알고리즘은 아닙니다. 증명된 무대에서는 최강입니다. 구현이 단순하고, 빠르고, 메모리도 적게 쓰니까요.

우리는 이미 탐욕법의 성공 사례를 여럿 만났습니다. 다익스트라(14주차), 크루스칼과 프림(14주차), 허프만(16주차). 전부 탐욕이고, 전부 최적해를 보장합니다.

examples/greedy.c:

/*
 * greedy.c - 탐욕법이 정답인 문제들
 * 17주차: 고급 알고리즘과 최적화
 *
 * 탐욕법 = 매 순간 가장 좋아 보이는 것을 선택.
 * 동전 예제에서 배신을 봤지만, "증명된 무대"에선 최강입니다:
 *
 * 1. 활동 선택: 회의실 하나에 겹치지 않게 최다 회의 배정
 *    -> "가장 빨리 끝나는 것부터" 가 항상 최적 (교환 논증으로 증명됨)
 *
 * 2. 분수 배낭: 물건을 쪼갤 수 있다면
 *    -> "가치/무게 순"이 항상 최적 (0/1과의 결정적 차이!)
 *
 * 탐욕이 통하는 조건: 탐욕 선택 속성 + 최적 부분 구조
 */
#include <stdio.h>

/* ---------- 1. 활동 선택 문제 ---------- */
typedef struct {
    const char *name;
    int start, end;
} Meeting;

/* 끝나는 시간 오름차순 정렬 (삽입 정렬) */
void sort_by_end(Meeting m[], int n) {
    for (int i = 1; i < n; i++) {
        Meeting key = m[i];
        int j = i - 1;
        while (j >= 0 && m[j].end > key.end) {
            m[j + 1] = m[j];
            j--;
        }
        m[j + 1] = key;
    }
}

void activity_selection(void) {
    Meeting m[] = {
        {"기획 회의",   1, 4},
        {"디자인 리뷰", 3, 5},
        {"주간 보고",   0, 6},
        {"면접",       5, 7},
        {"코드 리뷰",   3, 9},
        {"팀 회식 준비", 5, 9},
        {"고객 미팅",   6, 10},
        {"채용 회의",   8, 11},
        {"회고",       8, 12},
        {"전체 회의",   2, 14},
        {"1:1 면담",   12, 16},
    };
    int n = 11;

    printf("회의 %d개 신청 (시작~끝):\n", n);
    for (int i = 0; i < n; i++) {
        printf("  %-12s %2d ~ %2d\n", m[i].name, m[i].start, m[i].end);
    }

    sort_by_end(m, n);           /* 1. 끝나는 시간순 정렬 */

    printf("\n[탐욕: 가장 빨리 끝나는 것부터, 겹치면 건너뛰기]\n");
    int count = 0, last_end = 0;
    for (int i = 0; i < n; i++) {
        if (m[i].start >= last_end) {        /* 2. 안 겹치면 선택 */
            printf("  채택: %-12s %2d ~ %2d\n", m[i].name, m[i].start, m[i].end);
            last_end = m[i].end;
            count++;
        }
    }
    printf("총 %d개 배정 (이보다 많이는 불가능 - 증명된 최적!)\n", count);

    printf("\n왜 '빨리 끝나는 것'인가? (교환 논증의 감각)\n");
    printf("어떤 최적해가 있든, 첫 회의를 '가장 빨리 끝나는 것'으로\n");
    printf("바꿔치기해도 손해가 없다 (더 일찍 끝나 뒤가 더 여유로우니까).\n");
    printf("-> 탐욕 선택을 포함하는 최적해가 반드시 존재!\n");
}

/* ---------- 2. 분수 배낭 ---------- */
typedef struct {
    const char *name;
    double weight, value;
} Goods;

void fractional_knapsack(void) {
    Goods g[] = {
        {"금가루",   2.0, 100.0},    /* kg당 50 */
        {"은괴",     5.0, 150.0},    /* kg당 30 */
        {"구리",    10.0, 200.0},    /* kg당 20 */
        {"향신료",   4.0, 160.0},    /* kg당 40 */
    };
    int n = 4;
    double cap = 12.0;

    printf("\n\n=== 분수 배낭 (용량 %.0fkg, 쪼개기 가능!) ===\n", cap);
    printf("  %-8s %6s %6s %8s\n", "물건", "무게", "가치", "가치/kg");
    for (int i = 0; i < n; i++) {
        printf("  %-8s %5.0fkg %6.0f %8.1f\n",
               g[i].name, g[i].weight, g[i].value, g[i].value / g[i].weight);
    }

    /* 가치/무게 내림차순 정렬 */
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[j].value / g[j].weight > g[i].value / g[i].weight) {
                Goods t = g[i]; g[i] = g[j]; g[j] = t;
            }
        }
    }

    printf("\n[탐욕: 단가 높은 것부터, 마지막은 잘라서]\n");
    double remaining = cap, total = 0;
    for (int i = 0; i < n && remaining > 0; i++) {
        if (g[i].weight <= remaining) {
            printf("  %-8s 전부 (%.0fkg, 가치 %.0f)\n",
                   g[i].name, g[i].weight, g[i].value);
            remaining -= g[i].weight;
            total += g[i].value;
        } else {
            double frac = remaining / g[i].weight;
            printf("  %-8s %.0f%%만! (%.1fkg, 가치 %.0f)\n",
                   g[i].name, frac * 100, remaining, g[i].value * frac);
            total += g[i].value * frac;
            remaining = 0;
        }
    }
    printf("총 가치: %.0f (증명된 최적)\n", total);

    printf("\n0/1 배낭과의 결정적 차이:\n");
    printf("쪼갤 수 있으면 '단가 순 채우기'에 빈틈이 없다 -> 탐욕 최적\n");
    printf("쪼갤 수 없으면 마지막 빈 공간이 문제 -> DP 필요 (knapsack.c!)\n");
}

int main(void) {
    printf("탐욕법이 '증명된' 문제들\n");
    printf("=====================================\n\n");

    activity_selection();
    fractional_knapsack();

    printf("\n\n=== 탐욕법 총정리 ===\n");
    printf("탐욕이 정답인 문제 (증명 있음):\n");
    printf("  활동 선택, 분수 배낭, 허프만(16주차), MST(14주차), 다익스트라\n");
    printf("탐욕이 함정인 문제:\n");
    printf("  0/1 배낭, 일반 동전계 거스름돈, 외판원 문제\n");
    printf("\n판별법:\n");
    printf("1. 탐욕 선택 속성: 지금의 최선이 미래를 망치지 않는가?\n");
    printf("2. 반례 사냥: 작은 입력으로 DP/전수조사와 비교해 보라\n");
    printf("3. 증명 없이 탐욕을 믿지 마라. 증명이 있으면 최강의 무기!\n");
    return 0;
}

$ ./build/greedy
탐욕법이 '증명된' 문제들
=====================================

회의 11개 신청 (시작~끝):
  기획 회의  1 ~  4
  디자인 리뷰  3 ~  5
  주간 보고  0 ~  6
  면접        5 ~  7
  코드 리뷰  3 ~  9
  팀 회식 준비  5 ~  9
  고객 미팅  6 ~ 10
  채용 회의  8 ~ 11
  회고        8 ~ 12
  전체 회의  2 ~ 14
  1:1 면담   12 ~ 16

[탐욕: 가장 빨리 끝나는 것부터, 겹치면 건너뛰기]
  채택: 기획 회의  1 ~  4
  채택: 면접        5 ~  7
  채택: 채용 회의  8 ~ 11
  채택: 1:1 면담   12 ~ 16
총 4개 배정 (이보다 많이는 불가능 - 증명된 최적!)
...

=== 분수 배낭 (용량 12kg, 쪼개기 가능!) ===
  물건   무게 가치 가치/kg
  금가루     2kg    100     50.0
  은괴       5kg    150     30.0
  구리      10kg    200     20.0
  향신료     4kg    160     40.0

[탐욕: 단가 높은 것부터, 마지막은 잘라서]
  금가루 전부 (2kg, 가치 100)
  향신료 전부 (4kg, 가치 160)
  은괴   전부 (5kg, 가치 150)
  구리   10%만! (1.0kg, 가치 20)
총 가치: 430 (증명된 최적)
...

9.2 활동 선택: 왜 “빨리 끝나는 것”인가

회의실 하나에 겹치지 않게 최대한 많은 회의를 배정하는 문제입니다. “매 순간 하나를 고른다”는 탐욕의 틀은 정해졌는데, 무엇을 기준으로 고를지가 문제입니다. 세 가지 후보를 같은 11개 회의에 실제로 적용해 봤습니다.

 끝나는 시간 빠른 순:
   기획(1~4) 면접(5~7) 채용(8~11) 면담(12~16) => 4개
 시작 시간 빠른 순  :
   주간보고(0~6) 고객미팅(6~10) 면담(12~16) => 3개
 짧은 회의 순       :
   디자인(3~5) 면접(5~7) 채용(8~11) 면담(12~16) => 4개

“일찍 시작하는 것부터”는 실패합니다. 0시에 시작하는 주간 보고(0~6)를 먼저 집었더니 그 시간에 들어갈 수 있었던 기획 회의(1~4)와 면접(5~7)이 막혀 3개에 그쳤습니다.

“짧은 것부터”는 이 데이터에서는 4개로 정답과 같습니다. 그러면 이것도 맞는 전략일까요? 4절의 교훈대로 반례를 사냥해 봅시다.

[짧은 순이 지는 반례: A 1~5, B 5~9, C 4~6]
 끝나는 시간 빠른 순:
   A(1~5) B(5~9) => 2개
 짧은 회의 순       :
   C(4~6) => 1개

짧은 회의 C(4~6)가 A와 B의 경계에 걸쳐 있어서, C를 고르는 순간 둘 다 못 넣습니다. 짧은 것부터는 한 데이터에서 우연히 맞았을 뿐 보장이 없는 전략입니다. 이렇게 “한 번 맞았다”와 “항상 맞는다”는 다릅니다.

그럼 “빨리 끝나는 것부터”는 왜 항상 맞을까요? 교환 논증(exchange argument) 이라는 증명 기법을 감각적으로 따라가 봅시다.

어떤 최적해가 있다고 하자. 그 최적해에서 제일 먼저 하는 회의를 X라고 하자. X를 전체에서 가장 빨리 끝나는 회의 G로 바꿔치기해도 손해가 없다. G는 X보다 늦게 끝나지 않으므로(G가 가장 빨리 끝나니까), X 뒤에 오던 회의들은 G 뒤에도 그대로 들어간다. 회의 수는 그대로다. 따라서 탐욕 선택 G를 포함하는 최적해가 반드시 존재한다. G를 고른 뒤 남은 회의들에 같은 논리를 반복하면, 탐욕이 만든 해 전체가 최적임이 따라온다.

이것이 탐욕법 증명의 전형적인 형태입니다. “탐욕 선택을 해도 최적해를 잃지 않는다”를 보이는 것이죠. “일찍 시작하는 것”이나 “짧은 것”으로는 이 논증이 성립하지 않습니다. 바꿔치기했을 때 뒤의 회의가 밀려날 수 있으니까요.

구현은 놀랍도록 단순합니다.

    sort_by_end(m, n);           /* 끝나는 시간 오름차순 */
    int last_end = 0;
    for (int i = 0; i < n; i++) {
        if (m[i].start >= last_end) {    /* 직전에 채택한 회의가 끝난 뒤 시작하면 */
            /* 채택 */
            last_end = m[i].end;
        }
    }

정렬 한 번 + 한 번 훑기. DP라면 O(n²) 표를 채워야 할 문제가 O(n log n)에 끝납니다. 이것이 “증명된 무대에서 탐욕이 최강”인 이유입니다. >=인 이유도 보세요. 4시에 끝나는 회의 다음에 4시에 시작하는 회의는 겹치지 않는 것으로 칩니다. >로 바꾸면 딱 붙은 회의를 버리게 됩니다.

9.3 분수 배낭: 제약 하나가 바꾸는 것

2절의 0/1 배낭에서 탐욕이 졌습니다. 그런데 물건을 쪼갤 수 있다면 이야기가 달라집니다. 금가루, 향신료처럼 원하는 만큼 덜어 담을 수 있는 물건이라면요.

  금가루 전부 (2kg, 가치 100)      <- 단가 50, 1등
  향신료 전부 (4kg, 가치 160)      <- 단가 40
  은괴   전부 (5kg, 가치 150)      <- 단가 30
  구리   10%만! (1.0kg, 가치 20)   <- 단가 20, 남은 1kg만큼만
총 가치: 430 (증명된 최적)

단가(가치/무게)가 높은 것부터 넣고, 마지막에 공간이 모자라면 잘라서 채웁니다. 그리고 이것이 항상 최적입니다.

왜 0/1에서는 실패하고 분수에서는 성공할까요?

쪼갤 수 있으면 배낭에 빈 공간이 남지 않습니다.

0/1 배낭에서 탐욕이 진 이유는 “비율 좋은 것을 담았더니 4kg이라는 어중간한 공간이 남아 버려졌다”였습니다. 쪼갤 수 있으면 그 4kg도 다음으로 단가 높은 물건으로 꽉 채울 수 있으니, 낭비되는 공간이 없어 탐욕에 빈틈이 생기지 않습니다. 교환 논증으로 말하면, 어떤 최적해든 단가 낮은 물건 1kg을 단가 높은 물건 1kg으로 바꿔치기하면 손해가 없으므로 단가 순이 최적입니다.

코드에서 else 가지가 그 “잘라서”입니다.

        } else {
            double frac = remaining / g[i].weight;     /* 남은 공간 / 물건 무게 = 담을 비율 */
            total += g[i].value * frac;                /* 가치도 그 비율만큼 */
            remaining = 0;                             /* 배낭이 꽉 찼다 */
        }

제약 하나(쪼갤 수 있는가)가 최적 알고리즘을 바꿉니다. 문제를 볼 때 제약을 정확히 읽어야 하는 이유입니다.

9.4 탐욕 판별법

정리하면 이렇습니다.

탐욕이 정답인 문제 (증명 있음)

활동 선택 (이번 절)
분수 배낭 (이번 절)
허프만 코딩 (16주차)
최소 신장 트리 — 크루스칼, 프림 (14주차)
다익스트라 최단 경로 (14주차, 단 간선 가중치가 음수가 아닐 때)

탐욕이 함정인 문제

0/1 배낭 (2절)
일반 동전계 거스름돈 (4절)
외판원 문제(TSP). 프로젝트 2에서 봅니다

실전 판별법 세 가지

탐욕 선택 속성을 따져 본다: 지금의 최선이 미래의 선택지를 망가뜨리지 않는가? 교환 논증이 되는가?
반례를 사냥한다: 작은 입력을 여럿 만들어 DP나 전수조사와 비교해 봅니다. 위의 “짧은 회의 순”처럼 반례 하나면 탐욕은 탈락입니다.
증명 없이 믿지 않는다: 확신이 없으면 DP를 쓰세요. 느려도 정답이 낫습니다.

그리고 반대 방향의 실수도 조심하세요. 증명된 문제에 DP를 쓰는 것도 낭비입니다. 활동 선택을 DP로 풀면 O(n²)인데 탐욕은 O(n log n)이니까요.

실험: 바꾸면 어떻게 될까

if (m[i].start >= last_end)의 >=를 >로 바꿔 보세요. 기획 회의(1~4)가 끝나는 4시에 시작하는 회의가 있다면 버려집니다. 이 데이터에는 없지만, 채용 회의를 (11, 13)으로 바꿔 넣고 확인해 보세요.
분수 배낭의 용량을 21kg으로 바꿔 보세요. 모든 물건(2+5+10+4 = 21kg)이 다 들어가서 “잘라서”가 필요 없어집니다. 22kg이면 어떻게 될까요? remaining > 0인 채로 반복문이 끝나므로 총 가치는 610에서 멈춥니다.
분수 배낭에 “쪼갤 수 없다”는 제약을 넣어(else 가지를 지우고 건너뛰기) 같은 데이터를 돌려 보세요. 탐욕이 410(금가루+향신료+은괴, 11kg)을 내는데, 0/1 배낭 DP로 풀면 어떤 답이 나올까요? 2절의 knapsack에 이 데이터를 넣어 확인해 보세요.

10. 실습 프로젝트

projects/ 폴더에는 이번 주의 종합 작품 세 개가 있습니다. 특히 프로젝트 3은 Part 2 전체의 졸업 작품입니다.

$ cd week17
$ make
$ ./build/algo_visualizer    # 또는 optimizer, algo_library

프로젝트 1: 알고리즘 시각화 도구 (`algo_visualizer.c`)

알고리즘의 움직임을 터미널 글자로 보여 줍니다. 숫자 표가 아니라 그림으로 보면 이해가 완전히 달라집니다. 세 가지를 시각화합니다.

#define BARS 12
void draw_bars(const int arr[], int n, int hi1, int hi2, const char *msg);
void visual_bubble(int arr[], int n);                    /* 거품이 떠오른다 */
void visual_quick(int arr[], int low, int high, int n, int depth);
void draw_queens(int rows_placed, const char *msg);
int  visual_nqueens(int row);                            /* 놓고, 막히고, 되돌아옴 */
void visual_edit_distance(const char *a, const char *b); /* DP 표의 물결 */

정렬 (15주차 복습): 막대 그래프가 단계별로 정렬됩니다. 버블 정렬은 큰 값이 조금씩 오른쪽으로 밀려가고(거품), 퀵 정렬은 피벗이 한 번에 제자리에 꽂히며 구간이 쪼개집니다.

                      ##       ##
          ##          ##       ##    ##
          ##    ##    ##       ##    ##
          ##    ##    ##    ## ##    ##
    ##    ##    ##    ##    ## ##    ##
    ##    ##    ##    ## ## ## ##    ##
    ##    ##    ## ## ## ## ## ##    ##
    ## ## ##    ## ## ## ## ## ## ## ##
    ## ## ## ## ## ## ## ## ## ## ## ##
    -- -- -- -- -- -- -- -- ^^ ^^ -- --   9와 6 교환 (패스 1)

^^가 지금 교환한 두 막대입니다. draw_bars가 그림을 그리는 방법이 재미있습니다.

    for (int level = 9; level >= 1; level--) {       /* 제일 높은 층부터 */
        for (int i = 0; i < n; i++) {
            printf("%s ", arr[i] >= level ? "##" : "  ");   /* 그 층에 닿으면 칠한다 */
        }
        printf("\n");
    }

터미널은 위에서 아래로만 출력할 수 있으니, 막대그래프를 높은 층부터 그립니다. 9층에서는 값이 9인 막대만 칠해지고, 1층에서는 전부 칠해집니다. “값이 이 층보다 크거나 같으면 칠하고 아니면 비운다”, 세로 막대그래프를 글자로 그리는 고전적인 방법입니다.

N-Queens (5절): 퀸이 놓이고, 막히고, 사라지는 과정을 6×6 판으로 봅니다. 5.4절에 실은 그 화면입니다.

편집 거리 (16주차): DP 표가 한 행씩 채워지는 과정입니다. 완성된 표만 봤다면, 이번엔 채워지는 순서를 봅니다.

  [1행까지]       c  a  r  t
               0  1  2  3  4
            c  1  0  1  2  3

  [2행까지]       c  a  r  t
               0  1  2  3  4
            c  1  0  1  2  3
            a  2  1  0  1  2

  [3행까지]       c  a  r  t
               0  1  2  3  4
            c  1  0  1  2  3
            a  2  1  0  1  2
            t  3  2  1  1  1

  오른쪽 아래 1 = 최소 편집 횟수. 물결처럼 채워졌다!

“위와 왼쪽과 대각선이 이미 채워져 있어야 현재 칸을 계산할 수 있다”는 DP의 계산 순서가 눈에 들어옵니다. 3절 LCS 표도 정확히 같은 순서로 채워집니다.

“막히면 그림을 그려라”는 이 강좌의 조언을 도구로 만든 셈입니다.

확장 아이디어: ANSI 색상 코드로 강조, usleep으로 한 장면씩 애니메이션(18주차 예고), 병합 정렬·힙 정렬 추가, 입력 크기를 명령줄 인자로 받기.

프로젝트 2: 최적화 문제 해결기 (`optimizer.c`)

한 스타트업의 하루입니다. 실전 문제 세 개에 각각 맞는 무기를 꽂습니다. 문제를 읽고 “이건 어느 절의 문제지?”를 먼저 맞혀 보세요.

/* 문제 1: 회의실 배정 -> 탐욕 */
typedef struct { const char *team; int start, end; } Booking;
void solve_meetings(void);

/* 문제 2: 마케팅 예산 배분 -> DP (0/1 배낭) */
typedef struct { const char *name; int cost, reach; } Campaign;
void solve_budget(void);

/* 문제 3: 거래처 방문 경로 -> 백트래킹 + 분기한정 (TSP) */
static const int dist[CITIES][CITIES];
void tsp(int pos, int count, int cost, int use_bound);
void solve_route(void);

$ ./build/optimizer
최적화 문제 해결기: 작은 회사의 하루
=====================================

################ 문제 1: 회의실 배정 ################
회의실은 하나. 신청은 9건. 최대 몇 건 소화할까?

전략: 탐욕 - 빨리 끝나는 회의부터 (증명된 최적)

   9:00~11:00  개발팀
  11:00~13:00  마케팅
  13:00~14:00  인사팀
  14:00~16:00  영업2
  16:00~18:00  교육

=> 5건 배정! (경영진의 9~17시 독점 신청은 자연 탈락)

################ 문제 2: 마케팅 예산 배분 ################
예산 1000만원. 캠페인은 통째로만 집행 가능. 효과 최대는?

  캠페인      비용 예상 고객
  검색 광고     3백만       40명
  SNS 캠페인     4백만       55명
  유튜브 광고    5백만       70명
  오프라인 행사    6백만       75명
  인플루언서    2백만       30명

전략: DP (0/1 배낭 - 쪼갤 수 없으니 탐욕 금지!)

  선정된 캠페인:
    - 인플루언서 (2백만, +30명)
    - 유튜브 광고 (5백만, +70명)
    - 검색 광고 (3백만, +40명)

=> 총 10백만 지출, 예상 140명 (수학적 최적!)

################ 문제 3: 거래처 방문 경로 ################
본사에서 출발, 거래처 6곳을 모두 돌고 복귀. 최단 시간은?
(그 유명한 외판원 문제! 6곳이면 경로 6! = 720가지)

순수 백트래킹    : 탐색 1957노드
분기한정(B&B)    : 탐색 1174노드, 가지치기 603회

=> 최단 경로 (157분):
   본사 -> 성수 -> 송파 -> 강남 -> 판교 -> 구로 -> 마포 -> 본사 (복귀)
...

최적화 기법 비교

최적화 기법 비교

그림은 글을 쓴 뒤 다시 돌린 결과입니다. 벤치마크라서 본문 표와 수치가 몇 % 다릅니다. 배속과 순서가 같은지를 보세요 — 절대값이 아니라 그게 이 측정이 말하려는 것입니다.

문제 1, 회의실 배정 (탐욕): 9절의 활동 선택 그대로입니다. 9건 중 5건을 배정합니다. 흥미로운 것은 “경영진의 9~17시 독점 신청”이 자연스럽게 탈락한다는 점입니다. 가장 빨리 끝나는 것부터 고르는 규칙이 긴 회의를 알아서 배제하니까요. 9절의 실험에서 “일찍 시작하는 것부터”였다면 경영진 회의를 먼저 잡아 1건으로 끝났을 겁니다.

문제 2, 마케팅 예산 배분 (DP): 1,000만원으로 캠페인을 고릅니다. 캠페인은 통째로만 집행할 수 있으니 0/1 배낭입니다. “고객/비용 단가가 좋은 것부터”라는 탐욕의 유혹이 있지만, 2절에서 배운 대로 예산이 딱 떨어지지 않으면 손해를 봅니다. 단가(명/백만)로 줄을 세우면 인플루언서 15, 유튜브 14, SNS 13.75, 검색 13.3, 오프라인 12.5입니다. 답을 보면 1위와 2위는 뽑혔지만 3위 SNS는 빠지고 4위 검색이 뽑혔습니다. 2+5+4 = 11백만이라 SNS까지는 못 담고, 남은 3백만에 딱 맞는 검색 광고가 들어간 것입니다. 조합의 문제라 단가 순위와 답이 다릅니다. 쪼갤 수 없는 자원 배분은 DP입니다.

문제 3, 거래처 방문 경로 (백트래킹 + 분기한정): 이것이 이 프로젝트의 별입니다. 그 유명한 외판원 문제(TSP, Traveling Salesman Problem) 죠. 본사에서 출발해 6곳을 한 번씩 들르고 돌아오는 가장 짧은 순서를 찾습니다. 6곳의 방문 순서는 6! = 720가지이니 전부 시도하면 됩니다. 6절의 순열 생성이 그대로 쓰입니다.

void tsp(int pos, int count, int cost, int use_bound) {
    if (use_bound && cost >= best_cost) {    /* 한정(bound): 미리 자르기! */
        nodes_pruned++;
        return;
    }
    nodes_explored++;

    if (count == CITIES) {                   /* 모두 방문 -> 본사 복귀 */
        int total = cost + dist[pos][0];
        if (total < best_cost) { best_cost = total; /* 경로 저장 */ }
        return;
    }

    for (int next = 1; next < CITIES; next++) {
        if (visited[next]) continue;         /* 제약: 이미 간 도시 */
        visited[next] = 1;                   /* 선택 */
        cur_route[count] = next;
        tsp(next, count + 1, cost + dist[pos][next], use_bound);   /* 재귀 */
        visited[next] = 0;                   /* 취소 (백트래킹) */
    }
}

6절 순열의 used[]가 visited[]로, “자리”가 “몇 번째 방문”으로 바뀌었을 뿐 뼈대가 같습니다. 그리고 맨 위의 세 줄이 분기한정(branch and bound) 입니다. 아이디어는 이렇습니다.

“이미 찾은 최선(157분)보다 벌써 오래 걸린 경로는, 끝까지 가볼 필요도 없다.”

한 줄입니다. 그런데 이 한 줄이 탐색 노드를 1,957개에서 1,174개로 줄였습니다.

5절의 가지치기와 무엇이 다를까요? N-Queens의 가지치기는 “규칙을 위반했으니 자른다”(정답이 될 수 없음)였습니다. 분기한정은 “이미 찾은 답보다 나쁘니 자른다”(정답일 수는 있지만 최적은 아님)입니다. 후자는 지금까지의 최선값(bound)이 필요하고, 그래서 이름이 branch and bound입니다.

여기서 중요한 성질이 나옵니다. 좋은 해를 일찍 찾을수록 칼이 날카로워집니다. best_cost가 작아질수록 더 많은 가지가 잘리니까요. 그래서 실전 분기한정은 “그럴듯한 순서로 먼저 탐색”하는 휴리스틱을 함께 씁니다.

도시 수를 늘리면 어떻게 될까요? 같은 알고리즘에 무작위 거리를 넣고 도시 수를 5에서 11까지 늘려 봤습니다.

 도시 수   경로 수 (n-1)!    순수 백트래킹 노드    분기한정 노드   시간(ms, 분기한정)
     5               24                   65              62            0.0
     6              120                  326             206            0.0
     7              720                 1957             885            0.0
     8             5040                13700            3747            0.1
     9            40320               109601           17640            0.7
    10           362880               986410           87586            3.3
    11          3628800              9864101          451441           24.1

(도시 7개일 때 순수 백트래킹 1957노드가 optimizer와 정확히 같습니다. 거리와 상관없이 순열의 개수로 정해지는 값이니까요.)

두 가지가 보입니다. 첫째, 분기한정의 효과는 n이 클수록 커집니다. 7개에서는 2배 남짓이었는데 11개에서는 22배입니다. 둘째, 그래도 노드 수는 n마다 4~5배씩 늘어납니다. (n−1)!의 성장을 완전히 이기지는 못합니다. 도시 20개면 19! ≈ 1.2×10¹⁷가지라, 분기한정으로 1만 분의 1로 줄여도 10¹³개입니다.

TSP는 NP-난해 문제입니다. 다항 시간 알고리즘이 알려져 있지 않고, 아마 없을 것이라고 여겨집니다. 실무에서는 근사 알고리즘(정확한 답 대신 “충분히 좋은 답”을 빠르게)을 씁니다. 이 프로젝트의 분기한정은 “정확한 답을 조금 더 빠르게”이지, 지수 시간을 벗어나지는 못합니다.

확장 아이디어: TSP의 하한(bound)을 더 똑똑하게 계산하기(현재 비용에 “남은 도시들을 최소한 얼마에 돌 수 있는지”를 더해서 비교하면 가지치기가 훨씬 강해집니다), 근사 알고리즘(최근접 이웃, 2-opt)을 구현해 정답과 얼마나 차이 나는지 비교, 12절 심화 10번의 비트마스크 DP.

프로젝트 3: 종합 알고리즘 라이브러리 (`algo_library.c`)

Part 2의 졸업 작품입니다. 10~17주차의 핵심을 재사용 가능한 함수 20여 개로 정리하고, 자체 테스트로 전부 검증합니다.

/* [수학] */
long long alg_gcd(long long a, long long b);
long long alg_lcm(long long a, long long b);
long long alg_fast_pow(long long x, long long n, long long mod);

/* [검색] 15주차 */
int alg_lower_bound(const int arr[], int n, int target);
int alg_binary_search(const int arr[], int n, int target);

/* [정렬] 15주차 - 3-way 퀵 + 삽입 하이브리드 */
void alg_sort(int arr[], int n);

/* [DP] 16-17주차 */
long long alg_fib(int n);
int alg_knapsack(const int weight[], const int value[], int n, int cap);
int alg_edit_distance(const char *a, const char *b);
int alg_lcs_len(const char *a, const char *b);

/* [탐욕] 17주차 */
int alg_activity_count(const int start[], const int end[], int n);

/* [백트래킹] 17주차 */
int alg_nqueens_count(int n);

$ ./build/algo_library
종합 알고리즘 라이브러리 - Part 2 졸업 시험
=====================================

[수학]
  [통과] gcd(48, 36) == 12
  [통과] gcd(17, 5) == 1
  [통과] lcm(4, 6) == 12
  [통과] 3^45 mod p (분할 정복)
  [통과] 2^10 mod 1000 == 24

[검색]
  [통과] binary_search(8) == 4
  [통과] binary_search(9) == -1
  [통과] lower_bound(5) == 1
  [통과] lower_bound(9) == 5

[정렬]
  [통과] 난수 100개 정렬
  [통과] 중복 데이터 정렬

[DP]
  [통과] fib(10) == 55
  [통과] fib(50) (long long)
  [통과] 배낭(캠핑, 15kg) == 130
  [통과] 배낭(탐욕 함정) == 90
  [통과] edit(kitten,sitting)==3
  [통과] lcs(ABCBDAB,BDCABA)==4

[탐욕]
  [통과] 활동 선택 == 4

[백트래킹]
  [통과] 4-Queens 해 == 2
  [통과] 8-Queens 해 == 92

=====================================
결과: 20 / 20 통과
=====================================
...

8-Queens의 해가 92개라는 것은 널리 알려진 값입니다(참고 자료의 OEIS). 이렇게 정답이 알려진 값으로 테스트하는 것이 알고리즘 검증의 기본입니다. 직접 센 값을 정답으로 삼으면 버그가 있어도 알 수 없으니까요. 5절 실험 1에서 대각선 검사를 지웠을 때 이 테스트가 바로 잡아냅니다.

TEST 매크로도 보세요.

#define TEST(name, cond) do {                                    \
    tests_run++;                                                 \
    if (cond) { tests_passed++; printf("  [통과] %s\n", name); } \
    else      { printf("  [실패] %s (줄 %d)\n", name, __LINE__); } \
} while (0)

11주차에서 배운 함수형 매크로입니다. 실패하면 __LINE__(1주차 sysinfo의 그 미리 정의된 이름)으로 어느 줄의 테스트인지 알려 줍니다. do { } while (0)으로 감싼 이유는 if (x) TEST(...); else ...처럼 써도 문법이 깨지지 않게 하려는 관용구입니다.

눈여겨볼 점: 배낭의 1차원 최적화.

int alg_knapsack(const int weight[], const int value[], int n, int cap) {
    static int dp[1024];             /* 2차원이 아니라 1차원! */
    memset(dp, 0, (cap + 1) * sizeof(int));

    /* 1차원 최적화 버전: 뒤에서 앞으로! (같은 물건 중복 방지) */
    for (int i = 0; i < n; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int candidate = dp[w - weight[i]] + value[i];
            if (candidate > dp[w]) dp[w] = candidate;
        }
    }
    return dp[cap];
}

2절의 dp[i][w]에서 i 차원이 사라졌습니다. 1.5절에서 본 상태 공간 최적화의 실전판이죠. dp[i][w]는 dp[i-1][...], 즉 바로 윗행만 참조하므로, 행 하나를 덮어쓰며 진행할 수 있습니다.

그런데 반드시 w를 뒤에서 앞으로 순회해야 합니다. 앞에서부터 하면 어떻게 될까요? 실제로 돌려 봤습니다.

캠핑 배낭(15kg): 뒤에서 앞으로 = 130, 앞에서 뒤로 = 225
반례(10kg)     : 뒤에서 앞으로 = 90, 앞에서 뒤로 = 90
랜턴 하나(15kg): 뒤에서 앞으로 = 15, 앞에서 뒤로 = 225  (15개 담은 값!)

마지막 줄이 원인을 보여 줍니다. 물건이 랜턴(1kg, 가치 15) 하나뿐인데 앞에서부터 순회하니 225, 즉 랜턴을 15개 담은 값이 나왔습니다. dp[1]을 15로 갱신한 직후 dp[2]를 계산할 때 dp[2 - 1] = dp[1]이 이미 이번 물건을 반영한 값이라, 같은 랜턴을 또 담은 셈이 되기 때문입니다. 0/1 배낭이 아니라 무한 배낭(같은 물건을 여러 개 담을 수 있는 문제)의 답입니다.

뒤에서부터 순회하면 dp[w - weight[i]]가 아직 이번 물건을 반영하지 않은 “윗행”의 값이므로 올바릅니다. 캠핑 배낭에서도 130(정답) 대 225(랜턴을 여러 개 담음)로 갈립니다. 반례 데이터에서는 우연히 90으로 같은데, 한 데이터에서 같다고 맞는 코드가 아니라는 것은 9절에서 배웠습니다. 순회 방향 하나가 문제의 정의를 바꾸는 유명한 예입니다. 거꾸로, 무한 배낭을 풀고 싶다면 일부러 앞에서부터 순회하면 됩니다.

dp[1024]라는 크기도 보세요. cap이 1023을 넘으면 4.6절의 그 문제가 됩니다. 라이브러리로 쓰려면 cap 검사나 동적 할당을 넣어야 합니다. 12절 연습 문제로 남겨 둡니다.

이 파일을 5주차 모듈화 스타일로 algo.h / algo.c로 분리하면 여러분만의 알고리즘 라이브러리가 됩니다. 코딩 테스트 준비의 무기고로 쓰기 좋습니다.

확장 아이디어: 헤더/소스 분리 + Makefile, 제네릭 인터페이스(void *, 10주차)로 확장, 그래프 알고리즘(14주차) 추가, 문자열 알고리즘(16주차) 추가, alg_knapsack의 용량 상한 검사.

11. 자주 하는 실수와 함정

이번 주 실험에서 직접 재현한 것들입니다. 절 번호를 따라가면 실제 화면을 볼 수 있습니다.

1. DP 없이 재귀. fib(38)이 1억 2천만 번 호출됩니다(1.1절). “같은 인자로 두 번 불리는가?”를 항상 자문하세요.

2. 메모 판정에 답 자체를 사용. memo[n] != 0으로 판정하면 답이 진짜 0인 부분 문제가 매번 다시 계산됩니다(1.3절 실험). 별도의 computed[] 플래그나 -1 초기화를 쓰세요.

3. 배낭 1차원 최적화에서 앞에서 순회. 랜턴 하나로 225가 나옵니다(프로젝트 3). 반드시 뒤에서 앞으로.

4. 백트래킹에서 취소 누락. used[i] = 0을 빼먹으면 순열 24개 중 1개만 나옵니다(6.4절). “선택 → 재귀 → 취소”.

5. DP 배열 크기 넘는 입력. dp[1001]에 1,780원을 넣어 인접 배열이 망가지고 무한 루프에 빠졌습니다(4.6절). DP 배열은 입력 상한 검증부터.

6. 재귀 결과를 변수에 안 담기. fast_pow(x, n/2) * fast_pow(x, n/2)는 곱셈이 22번에서 314만 번이 됩니다(8.2절). O(log n)이 O(n)이 되죠.

7. 탐욕을 증명 없이 신뢰. 동전계 {1,3,4}(4절)와 “짧은 회의 순”(9.2절)이 영원한 경고입니다. 한 데이터에서 맞은 것은 증명이 아닙니다.

8. 지수 폭발 무시. 백트래킹은 N-Queens 13에서 1.2초, 20이면 50시간입니다(5.7절). 크면 DP·탐욕·근사로 전환하세요.

9. 역추적 잊기. “최댓값”만 구하고 “무엇을”을 못 구하면 반쪽짜리입니다. 표 비교(2.5절)나 choice[] 배열(4.4절)이면 됩니다.

10. INF에 INT_MAX. INF + 1이 넘쳐 음수가 되어 불가능한 금액이 “가능”으로 판정됩니다(4.5절). 14주차부터 반복되는 함정입니다.

11. 함수 호출과 카운터를 같은 printf 인자에. printf("%d %ld", f(), counter)에서 counter가 f() 전에 읽힐 수 있습니다(8.3절). 인자 평가 순서는 정해져 있지 않습니다.

12. 연습 문제

기본 문제

계단 오르기: 한 번에 1칸 또는 2칸씩 오를 때 n칸 계단을 오르는 방법의 수를 구하세요. (힌트: 피보나치와 같은 점화식입니다. n칸에 도달하는 마지막 걸음은 1칸 아니면 2칸이니까요.)
최대 부분합: 배열에서 연속된 구간의 합이 최대가 되는 값을 구하세요(카데인 알고리즘). dp[i] = “i에서 끝나는 구간 중 최대 합”으로 정의해 보세요. 점화식은 max(dp[i-1] + a[i], a[i])입니다. 왜 그런지 설명해 보세요.
LIS(최장 증가 부분 수열): 배열에서 증가하는 가장 긴 부분 수열의 길이를 구하세요. O(n²) DP로 먼저, 여유가 되면 15주차의 lower_bound를 써서 O(n log n)으로.
부분집합 합: 배열에서 합이 정확히 K가 되는 부분집합이 있는지 판정하세요. 배낭의 사촌입니다. dp[i][s] = “앞 i개로 합 s를 만들 수 있는가”로 정의해 보세요.
조합 nCk 계산: 파스칼의 삼각형 C(n,k) = C(n-1,k-1) + C(n-1,k)를 DP로 채워 nCk를 구하세요. 메모이제이션과 테이블 두 가지로.
alg_knapsack 방어: 프로젝트 3의 alg_knapsack에 cap >= 1024일 때의 방어를 넣거나, 7주차의 malloc으로 cap + 1 크기를 동적 할당하도록 고치세요.

심화 문제

동전 경우의 수: 4.7절 실험 2를 완성하세요. “최소 개수”가 아니라 거스름돈을 만드는 방법의 가짓수를 구하되, 순서를 무시하는 버전과 구분하는 버전을 둘 다 만들고 왜 반복문 순서가 답을 바꾸는지 설명하세요.
스도쿠 풀이기: 백트래킹으로 스도쿠를 푸세요. 가지치기를 얼마나 잘하느냐가 성능을 가릅니다. “빈칸을 왼쪽 위부터”와 “후보가 가장 적은 칸부터”의 탐색 노드 수를 비교해 보세요.
행렬 연쇄 곱셈: 행렬 여러 개를 곱할 때 괄호를 어떻게 치면 곱셈 횟수가 최소인지 DP로 구하세요. dp[i][j] = “i번째부터 j번째 행렬까지 곱하는 최소 비용”인 구간 DP의 대표 문제입니다.
TSP 비트마스크 DP: 프로젝트 2의 TSP를 dp[방문한 도시 집합][현재 위치] 형태의 DP로 바꾸세요. 집합은 3주차의 비트 연산으로 정수 하나에 담습니다. O(n!)이 O(2ⁿ × n²)이 됩니다. 도시 11개에서 분기한정(45만 노드)과 노드 수를 비교하세요.
카라추바 곱셈: 큰 수(문자열로 표현된) 곱셈을 분할 정복으로 구현하고, 단순 O(n²) 곱셈과 시간을 비교하세요. 3.6절처럼 n을 2배씩 늘리며 표를 만들면 지수 1.58이 보입니다.

마치며: Part 2 완결

이번 주에 배운 것을 정리합니다.

DP: 상태-점화식-기저의 3단 레시피, 하향식/상향식, 역추적, 공간 최적화. 그리고 “적어 두기”가 1억 번을 75번으로 만드는 것을 눈으로 봤습니다.
백트래킹: 선택-재귀-취소의 리듬 + 가지치기, 분기한정으로 진화. 가지치기가 1,220배를 절약하지만 지수는 지수라는 것도 봤습니다.
분할 정복: 절반의 마법. 마스터 정리로 복잡도를 계산하고, 변수 하나를 빼먹으면 O(n)으로 돌아가는 것도 세어 봤습니다.
탐욕: 증명된 무대에선 최강, 아니면 함정. 반례를 직접 만들어 봤습니다.

그리고 이번 주의 진짜 메시지는 이것입니다.

문제의 구조가 알고리즘을 정한다.

프로젝트 2에서 본 그대로입니다. “겹침 없이 최다 선택”은 탐욕, “쪼갤 수 없는 자원 배분”은 DP, “순서와 경로의 전수 탐색”은 백트래킹. 문제를 읽고 구조를 알아보는 것이 알고리즘을 외우는 것보다 훨씬 중요합니다.

또 하나. 이번 주에는 직접 세고 재는 것을 많이 했습니다. 호출 횟수, 곱셈 횟수, 탐색 노드 수, n을 2배로 했을 때의 시간. 복잡도 표기는 그 숫자들의 요약일 뿐입니다. “O(n²)”이라고 외우는 것보다 “n을 2배로 하니 4배 느려지더라”를 한 번 재 본 것이 오래 남습니다.

Part 2 (10~17주차) 완주를 축하합니다!

8주 전, malloc과 씨름하며 연결 리스트를 만들던 때를 기억하시나요? 지금 여러분의 손에는 이것들이 있습니다.

자료구조

동적 배열, 연결 리스트 (10주차)
스택, 큐, 덱, 우선순위 큐 (11주차)
이진 탐색 트리, AVL 트리, 힙 (12주차)
해시 테이블, B-트리, 트라이 (13주차)
그래프, 인접 행렬과 리스트 (14주차)

알고리즘

정렬 10종과 검색 (15주차)
문자열 검색·압축·편집 거리 (16주차)
DP, 백트래킹, 분할 정복, 탐욕 (17주차)

프로젝트 24개: 계산기, 주소록, 텍스트 에디터 버퍼, 미로 탐색, 파일 트리, 키-값 저장소, 문서 검색 엔진, 자동 완성, GPS 내비게이션, 소셜 네트워크 분석, 네트워크 라우팅, 정렬 라이브러리, 외부 정렬, 벤치마크, grep 클론, 허프만 압축기, 정규식 엔진, 알고리즘 시각화, 최적화 해결기, 종합 라이브러리…

이것들은 전부 여러분이 직접 만든 것입니다. 라이브러리를 가져다 쓴 것이 아니라 밑바닥부터요. 그래서 이제 어떤 언어의 어떤 자료구조를 써도 그 안에서 무슨 일이 벌어지는지 보입니다.

다음 주부터는 Part 3: 시스템 프로그래밍입니다.

지금까지 우리 프로그램은 자기 세계 안에서만 놀았습니다. 메모리를 할당하고, 계산하고, 출력하고. 이제 그 울타리를 넘어 운영체제와 직접 대화하기 시작합니다. 프로세스를 만들고, 시그널을 주고받고, 파일 디스크립터를 다루고, 나중에는 네트워크로 다른 컴퓨터와 이야기합니다.

1주차에서 man 2가 “운영체제 기능을 부르는 함수”라고만 했던 것 기억하시나요? printf 밑에 무엇이 있는지, 터미널에 명령을 치면 무슨 일이 일어나는지, 프로그램이 여러 개 동시에 도는 것이 어떻게 가능한지. 그 답을 다음 주부터 직접 코드로 확인하게 됩니다.

알고리즘이라는 무기를 들고 운영체제의 세계로 들어갑니다. 재미있어질 겁니다.

수고하셨습니다. 정말로요.

체크리스트

각 항목을 설명할 수 있으면 체크합니다.

[ ] DP의 두 조건(겹치는 부분 문제, 최적 부분 구조)을 말할 수 있다
[ ] DP 3단계 레시피(상태-점화식-기저)로 문제를 정리할 수 있다
[ ] 메모이제이션과 테이블 방식을 각각 구현할 수 있다
[ ] 순수 재귀 피보나치의 호출 횟수가 왜 지수적인지 호출 나무로 설명할 수 있다
[ ] 메모 판정에 별도 플래그가 필요한 이유를 안다
[ ] fib를 O(1) 공간으로 줄이는 이유(직전 둘만 참조)를 안다
[ ] 0/1 배낭 점화식(담기/말기)과 역추적을 구현할 수 있다
[ ] 물건 3개, 용량 5의 배낭 표를 손으로 채울 수 있다
[ ] 0/1 배낭에서 탐욕이 지는 반례를 설명할 수 있다
[ ] LCS와 편집 거리의 점화식 차이(min+1 vs max, +1)를 안다
[ ] 줄 단위 LCS가 diff가 되는 원리를 안다
[ ] n을 2배로 하면 O(n²)이 4배 느려지는 것을 직접 재 봤다
[ ] 탐욕이 배신하는 동전계 반례를 들 수 있다
[ ] DP가 “불가능”까지 정확히 판정하는 원리(INF)와 INT_MAX의 함정을 안다
[ ] 백트래킹 3요소(선택/제약/목표)와 리듬(선택-재귀-취소)을 안다
[ ] N-Queens의 is_safe 가지치기 효과를 수치로 설명할 수 있다
[ ] 대각선 판정 abs(행차) == abs(열차)를 안다
[ ] 부분집합/조합/순열 생성의 차이(제약 하나)를 안다
[ ] 취소를 빼먹으면 순열이 1개만 나오는 이유를 안다
[ ] 복잡도별로 1초 안에 가능한 n의 크기 감각이 있다
[ ] 미로에서 visited와 path_mark를 분리하는 이유를 안다
[ ] 빠른 거듭제곱 O(log n)을 구현할 수 있다
[ ] 재귀 결과를 변수에 담아야 하는 이유를 곱셈 횟수로 설명할 수 있다
[ ] 마스터 정리로 병합 정렬의 O(n log n)을 유도할 수 있다
[ ] 활동 선택의 탐욕 증명 감각(교환 논증)을 이해했고, “짧은 것부터”의 반례를 안다
[ ] 분수 배낭과 0/1 배낭의 무기가 다른 이유를 안다
[ ] 분기한정이 일반 가지치기와 다른 점(bound로 미리 자름)을 안다
[ ] 배낭 1차원 최적화에서 뒤에서 순회하는 이유를 실험 결과로 설명할 수 있다
[ ] algo_library의 20개 테스트 전부 통과를 확인했다
[ ] (도전) TSP 하한 개선, 비트마스크 DP, 시각화 애니메이션을 추가해 봤다

참고 자료

CLRS(Introduction to Algorithms) Chapter 15(DP), 16(탐욕), 4(분할 정복), 34-35(NP와 근사)
OEIS A000170, N-Queens 해의 개수: 4→2, 5→10, 6→4, 7→40, 8→92, 9→352, 10→724, 11→2680, 12→14200, 13→73712
마스터 정리 (Wikipedia)
Bellman의 회고: “dynamic programming”이라는 이름은 연구비를 승인받기 위해 “수학 연구”처럼 안 들리게 지은 작명이었다는 유명한 일화가 있습니다
다음 주차: 18주차 POSIX 시스템 프로그래밍 (Part 3 시작!)

학습 목표

들어가며

준비

1. 동적 계획법 입문: 피보나치 4단 진화

1.1 같은 문제를 네 번 풀기

1.2 왜 이런 차이가 나는가

1.3 메모이제이션: 재귀에 노트 세 줄 붙이기

computed[] 배열이 따로 필요한 이유

1.4 테이블: 재귀 없이 작은 것부터

1.5 상태 공간 최적화: 배열 100칸에서 변수 2개로

1.6 DP 3단계 레시피

실험: 바꾸면 어떻게 될까

2. 0/1 배낭: DP의 대표 선수

2.1 문제

2.2 상태 정의: 표의 한 칸에 무엇을 적을까

2.3 점화식: 담거나, 말거나

2.4 표를 직접 채워 보기

2.5 역추적: “얼마”에서 “무엇을”로

2.6 탐욕이 지는 이유

실험: 바꾸면 어떻게 될까

3. LCS: diff의 심장

3.1 최장 공통 부분 수열

3.2 표 읽기: 한 칸이 뜻하는 것

3.3 편집 거리와 나란히 놓기

3.4 역추적으로 LCS 문자열 복원하기

3.5 미니 diff: git이 하는 일

3.6 O(n×m)을 실측하기

실험: 바꾸면 어떻게 될까

4. 동전 거스름돈: 탐욕과 DP의 갈림길

4.1 같은 문제, 다른 답

4.2 다섯 시나리오가 말하는 것

4.3 점화식과 표 채우기

4.4 역추적: choice[] 한 줄로 “무엇을”

4.5 INF의 정체와 INT_MAX의 함정

4.6 배열 범위 방어

4.7 이번 주의 철학

실험: 바꾸면 어떻게 될까

5. 백트래킹: 가보고, 막히면 돌아온다

5.1 N-Queens

5.2 판을 어떻게 저장하나: 자료구조가 제약 하나를 없앤다

5.3 is_safe: 제약 검사

5.4 solve: 선택 → 재귀 → 취소

5.5 가지치기의 위력을 숫자로

5.6 백트래킹 3요소와 리듬

5.7 지수 폭발의 벽

실험: 바꾸면 어떻게 될까

6. 조합 생성 3종 세트

6.1 모든 백트래킹의 뼈대

6.2 부분집합: 넣거나, 말거나

6.3 조합: start 하나로 순서 중복 없애기

6.4 순열: used 검사, 그리고 취소를 빼먹으면

6.5 크기 감각을 몸에 익히기

실험: 바꾸면 어떻게 될까

7. 미로: 백트래킹 vs BFS 재대결

7.1 백트래킹의 상징적인 한 줄

7.2 visited와 path_mark를 따로 두는 이유

7.3 언제 무엇을 쓸까

실험: 바꾸면 어떻게 될까

8. 분할 정복: 반으로 쪼개는 수학

8.1 이미 만난 패러다임

8.2 빠른 거듭제곱

8.3 행렬로 피보나치를 O(log n)에

8.4 마스터 정리

실험: 바꾸면 어떻게 될까

9. 탐욕법: 증명된 무대에서만 최강

9.1 동전에서 배신을 봤지만

9.2 활동 선택: 왜 “빨리 끝나는 것”인가

9.3 분수 배낭: 제약 하나가 바꾸는 것

9.4 탐욕 판별법

실험: 바꾸면 어떻게 될까

10. 실습 프로젝트

프로젝트 1: 알고리즘 시각화 도구 (algo_visualizer.c)

프로젝트 2: 최적화 문제 해결기 (optimizer.c)

프로젝트 3: 종합 알고리즘 라이브러리 (algo_library.c)

11. 자주 하는 실수와 함정

12. 연습 문제

기본 문제

심화 문제

마치며: Part 2 완결

Part 2 (10~17주차) 완주를 축하합니다!

프로젝트 1: 알고리즘 시각화 도구 (`algo_visualizer.c`)

프로젝트 2: 최적화 문제 해결기 (`optimizer.c`)

프로젝트 3: 종합 알고리즘 라이브러리 (`algo_library.c`)