학습 목표
이번 주차를 마치면 다음을 할 수 있습니다:
- 브루트포스 검색의 비교 횟수를 손으로 세고, 최악의 입력이 언제 생기는지 설명할 수 있다
- KMP의 실패 함수를 종이에 계산하고, 텍스트 포인터가 왜 뒤로 가지 않는지 안다
- 라빈-카프의 롤링 해시를 십진수로 설명하고, 해시 충돌이 왜 위험한지 실험으로 확인한다
- 보이어-무어가 텍스트를 건너뛰는 과정을 한 단계씩 그릴 수 있고,
grep이 빠른 이유를 안다 - Z 알고리즘으로 검색·주기·접두사-접미사 문제를 풀 수 있다
- 접미사 배열과 LCP로 반복 부분 문자열을 찾을 수 있다
- RLE와 허프만 코딩으로 압축의 원리(패턴과 빈도)를 설명하고, 압축이 안 되는 데이터가 왜 있는지 안다
- 편집 거리의 DP 표를 손으로 채우고, 같은 문제를 재귀로 풀면 왜 안 되는지 숫자로 안다
- 바이트 단위 알고리즘이 한글(UTF-8)에서 어떻게 어긋나는지 안다
- 백트래킹 정규식 엔진의 동작과 한계(ReDoS)를 안다
들어가며
에디터에서 Ctrl + F를 누르고 단어를 치면 수백만 줄짜리 파일에서도 결과가 그 자리에서 나옵니다. 검색창에 오타를 치면 “혹시 이것을 찾으셨나요?”라고 되묻습니다. 100MB짜리 텍스트를 ZIP으로 묶으면 30MB가 됩니다. 어떻게 그럴 수 있을까요? 컴퓨터가 빨라서? 아닙니다. 이번 주에 만드는 알고리즘들이 그 안에서 돌고 있기 때문입니다.
4주차에서 문자열은 “\0으로 끝나는 char 배열”일 뿐이라고 배웠습니다. 그렇게 단순한 것에 왜 따로 알고리즘이 필요할까요? 패턴 때문입니다. 텍스트에는 반복과 구조가 있습니다. 같은 단어가 다시 나오고, 알파벳마다 쓰이는 빈도가 다르고, 한 번 본 부분은 다시 볼 필요가 없습니다. 이 구조를 읽어 내는 순간, 아무 생각 없이 처음부터 비교하는 방법보다 수십 배, 때로는 수천 배 빨라집니다. 이번 주 내내 반복될 한 문장이 이것입니다.
문자열의 구조를 읽어 내는 쪽이 이긴다.
지난 주차의 재료도 총출동합니다. 13주차 해시는 라빈-카프가 되고, 12주차 힙과 트리는 허프만 코딩이 되고, 15주차 이진 탐색은 접미사 배열이 되고, 14주차 백트래킹은 정규식 엔진이 됩니다. 새로 배우는 것보다 이미 아는 도구를 새 곳에 쓰는 주차입니다.
이 글은 깁니다. 알고리즘마다 작은 예로 한 단계씩 손으로 따라가는 표, 실제로 컴파일해 얻은 출력, 그리고 “이걸 바꾸면 어떻게 될까” 실험이 붙어 있습니다. 표를 눈으로만 훑지 말고 종이에 직접 써 보세요. 문자열 알고리즘은 종이 위에서 한 번 굴려 본 사람과 안 굴려 본 사람의 이해 깊이가 완전히 다릅니다.
예제 코드는 week16/examples/와 week16/projects/에 있습니다. 이번 주부터는 예제가 많으니 make로 한꺼번에 빌드합니다.
$ cd week16
$ make
컴파일: examples/boyer_moore.c
컴파일: examples/edit_distance.c
...
✓ 모든 파일 빌드 완료!
$ ls build
boyer_moore compress_tool edit_distance huffman mini_grep mini_regex
naive_vs_kmp rabin_karp rle_compress suffix_array z_algorithm
5주차에서 배운 Makefile이 examples/*.c와 projects/*.c를 전부 build/ 아래의 실행 파일로 만듭니다. 파일 하나만 다시 만들고 싶으면 1주차 기본 명령을 그대로 쓰면 됩니다.
$ gcc -Wall -Wextra -std=c11 -g examples/naive_vs_kmp.c -o build/naive_vs_kmp
이 글의 모든 출력은 이 명령으로 만든 실행 파일을 실제로 돌려 얻은 것입니다. 측정 시간은 이 글을 쓴 컴퓨터(x86-64, GCC 13)의 값이라 여러분 컴퓨터에서는 숫자가 다를 수 있습니다. 숫자 자체보다 비율과 경향을 보세요.
1. 문제 설정: 브루트포스는 무엇이 문제인가
이번 주 전반부의 문제는 딱 하나입니다.
길이 n인 텍스트에서 길이 m인 패턴이 나타나는 모든 위치를 찾아라.
Ctrl + F가 하는 일이 바로 이것입니다. 텍스트는 파일 전체, 패턴은 여러분이 친 단어입니다.
1.1 가장 단순한 해법
떠오르는 대로 짜면 이렇게 됩니다. 텍스트의 모든 시작 위치 i에 패턴을 갖다 대고, 앞에서부터 한 글자씩 비교합니다.
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m && text[i + j] == pattern[j]) j++;
if (j == m) 발견(i);
}
이것을 브루트포스(brute force, 무식한 힘) 또는 단순 검색이라고 부릅니다. i + m <= n 조건은 “패턴이 텍스트 끝을 넘어가지 않는 시작 위치까지만”이라는 뜻입니다. 4주차에서 배열 범위를 넘어 읽으면 무슨 일이 생기는지 봤죠. 이 조건이 없으면 text[i + j]가 \0 너머를 읽습니다.
1.2 손으로 따라가기
작은 예로 실제로 무슨 일이 일어나는지 봅시다. 텍스트는 ABABDABACDABABCABAB(19글자), 패턴은 ABABC(5글자)입니다. 시작 위치는 0부터 14까지 15개이고, 각 위치에서 비교한 글자 쌍(텍스트 글자와 패턴 글자)을 전부 적으면 이렇습니다.
i 비교한 글자 쌍 결과
0 AA BB AA BB DC 실패 (5번째에서)
1 BA 첫 글자에서 실패
2 AA BB DA 실패 (3번째에서)
3 BA 첫 글자에서 실패
4 DA 첫 글자에서 실패
5 AA BB AA CB 실패 (4번째에서)
6 BA 첫 글자에서 실패
7 AA CB 실패 (2번째에서)
8 CA 첫 글자에서 실패
9 DA 첫 글자에서 실패
10 AA BB AA BB CC 발견!
11 BA 첫 글자에서 실패
12 AA BB CA 실패 (3번째에서)
13 BA 첫 글자에서 실패
14 CA 첫 글자에서 실패
총 비교 31회 (시작 위치 15개)
두 가지가 보입니다.
첫째, 대부분의 위치는 첫 글자에서 끝납니다. 15개 위치 중 9개가 비교 한 번으로 끝났습니다. 일상 텍스트에서 브루트포스가 생각보다 빠른 이유입니다.
둘째, 위치 0을 보세요. ABAB까지 4글자를 맞추고 5번째에서 실패했습니다. 그런데 위치 1로 넘어가서 다시 처음부터 비교합니다. 방금 확인한 사실을 전부 버립니다. 위치 0에서 텍스트가 ABAB로 시작한다는 것을 알았으면, 위치 2에서 AB가 이미 맞는다는 것도 아는 셈인데 말이죠.
1.3 최악은 언제 오는가
이 낭비가 얼마나 커질 수 있을까요? 시간 복잡도로 말하면 최악 O(n × m)입니다. 시작 위치 n개마다 m글자를 다 비교하는 경우죠. 그 최악은 불일치가 늦게 발견될 때 일어납니다. 텍스트가 AAAAAAAAAA...이고 패턴이 AAAAAAAAAB라면, 매 위치에서 A를 9개 맞춰 보고 10번째에서 실패하고, 한 칸 옮겨서 또 A를 9개 맞춰 봅니다.
naive_vs_kmp.c(2절)가 이 상황을 만들어 셉니다. A 10,000개짜리 텍스트에서 AAAAAAAAAB를 찾으면 비교가 99,910회입니다. 왜 이 숫자일까요? 시작 위치는 10,000 − 10 + 1 = 9,991개이고, 매 위치에서 10번씩 비교하니(A 9개 일치 + B에서 불일치) 9,991 × 10 = 99,910입니다. 계산이 딱 맞습니다.
패턴을 더 길게 하면 어떻게 될까요? 텍스트를 A 100만 개로 늘리고 패턴 길이를 바꿔 가며 재 봤습니다.
텍스트: A x 1000000
패턴 길이 m 브루트포스 비교(회) 시간(ms) KMP 비교(회) 시간(ms)
10 9999910 15.7 1999991 3.6
100 99990100 129.3 1999901 3.9
1000 999001000 1204.6 1999001 3.6
10000 9900010000 11937.9 1990001 3.9
브루트포스는 패턴이 10배 길어질 때마다 시간이 10배씩 늘어 12초까지 갑니다. 오른쪽의 KMP는 패턴 길이와 상관없이 4ms입니다. 이 표 하나가 이번 주 전반부를 배우는 이유입니다.
1.4 네 가지 해법
앞으로 볼 네 알고리즘은 각자 다른 방식으로 이 낭비를 없앱니다.
| 알고리즘 | 낭비를 없애는 방법 | 한 줄 비유 |
|---|---|---|
| KMP | 패턴의 자기 유사성을 미리 계산해 둔다 | 실패에서 배운다 |
| 라빈-카프 | 창 하나를 숫자 하나로 바꿔 비교한다 | 지문으로 대조한다 |
| 보이어-무어 | 볼 필요 없는 곳은 아예 건너뛴다 | 뒤에서부터 보고 점프한다 |
| Z 알고리즘 | 이미 계산한 일치 구간을 재활용한다 | 복사해서 출발한다 |
2. KMP: 실패에서 배운다
2.1 실패 함수 — 손으로 계산하기
KMP(Knuth-Morris-Pratt, 세 발명자의 이름)의 통찰은 이렇습니다.
불일치가 났을 때, 지금까지 일치한 부분에는 정보가 있다.
그 정보를 표로 만든 것이 실패 함수(failure function)입니다. 부분 일치 표, LPS(Longest Prefix Suffix) 배열이라고도 부릅니다. 정의는 이렇습니다.
fail[i]= 패턴의 앞i+1글자(pattern[0..i])에서, “진접두사이면서 동시에 접미사인 문자열”의 최대 길이
“진접두사”는 문자열 전체가 아닌 접두사라는 뜻입니다. 정의만 읽으면 어렵지만, 손으로 한 번 계산하면 바로 감이 옵니다. 패턴 ABABC로 해 봅시다.
| i | 앞 i+1글자 | 그것의 접두사들 | 그것의 접미사들 | 양쪽에 다 있는 것 | fail[i] |
|---|---|---|---|---|---|
| 0 | A |
(없음) | (없음) | (없음) | 0 |
| 1 | AB |
A |
B |
(없음) | 0 |
| 2 | ABA |
A, AB |
A, BA |
A |
1 |
| 3 | ABAB |
A, AB, ABA |
B, AB, BAB |
AB |
2 |
| 4 | ABABC |
A, AB, ABA, ABAB |
C, BC, ABC, BABC |
(없음) | 0 |
그래서 ABABC의 실패 함수는 0 0 1 2 0입니다.
fail[3] = 2의 의미가 KMP의 전부입니다. “ABAB까지 일치하고 다음 글자에서 실패했다면, 텍스트의 마지막 두 글자 AB는 패턴의 첫 두 글자 AB와 같다. 그러니 패턴을 두 칸 위치까지 옮겨 놓고 이어서 비교하면 된다.” 텍스트를 되돌아갈 필요가 없습니다.
1.2절의 표에서 위치 0의 실패를 다시 보세요. ABAB를 맞추고 D에서 실패했습니다. 브루트포스는 위치 1로 가서 B와 A를 비교했지만(뻔히 실패), KMP는 fail[3] = 2를 보고 “텍스트의 D 앞 두 글자 AB는 이미 패턴의 AB와 맞다”고 판단해, D를 패턴의 3번째 글자 A와 바로 비교합니다.
직접 해 보기: 패턴
AABAACAABAA의 실패 함수를 위 표처럼 계산해 보세요. 답은 2.4절에서 프로그램이 알려 줍니다. 종이에 먼저 하세요.
2.2 예제: naive_vs_kmp.c
examples/naive_vs_kmp.c:
/*
* naive_vs_kmp.c - 브루트포스 vs KMP 문자열 검색
* 16주차: 문자열 알고리즘
*
* 문제: 텍스트(길이 n)에서 패턴(길이 m) 찾기.
*
* 브루트포스: 모든 위치에서 처음부터 다시 비교. 최악 O(n*m)
*
* KMP의 통찰: "실패에서 배우자!"
* 불일치가 났을 때, 지금까지 일치한 부분에는 정보가 있다.
* 패턴의 "접두사 = 접미사" 정보를 미리 계산해 두면(실패 함수)
* 텍스트 포인터를 절대 뒤로 물리지 않는다. O(n + m)!
*/
#include <stdio.h>
#include <string.h>
static long comparisons;
/* ---------- 브루트포스 ---------- */
int naive_search(const char *text, const char *pattern, int print) {
int n = (int)strlen(text);
int m = (int)strlen(pattern);
int found = 0;
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m) {
comparisons++;
if (text[i + j] != pattern[j]) break;
j++;
}
if (j == m) {
if (print) printf(" 위치 %d에서 발견\n", i);
found++;
}
}
return found;
}
/* ---------- KMP ---------- */
/* 실패 함수(failure/lps): fail[i] = pattern[0..i]에서
* "진접두사이면서 접미사인 것"의 최대 길이
*
* 예: ABABC
* fail[0]=0 (A)
* fail[1]=0 (AB)
* fail[2]=1 (ABA: 'A')
* fail[3]=2 (ABAB: 'AB')
* fail[4]=0 (ABABC)
*/
void build_failure(const char *pattern, int m, int fail[]) {
fail[0] = 0;
int len = 0; /* 현재 일치 중인 접두사 길이 */
for (int i = 1; i < m; i++) {
/* 불일치면 더 짧은 접두사로 후퇴 (재귀적 후퇴!) */
while (len > 0 && pattern[i] != pattern[len]) {
len = fail[len - 1];
}
if (pattern[i] == pattern[len]) {
len++;
}
fail[i] = len;
}
}
int kmp_search(const char *text, const char *pattern, int print) {
int n = (int)strlen(text);
int m = (int)strlen(pattern);
int fail[256];
build_failure(pattern, m, fail);
int found = 0;
int j = 0; /* 패턴에서 일치한 길이 */
for (int i = 0; i < n; i++) { /* i는 절대 뒤로 안 간다! */
while (j > 0) {
comparisons++;
if (text[i] == pattern[j]) break;
j = fail[j - 1]; /* 실패 함수로 점프 */
}
if (j == 0) comparisons++;
if (text[i] == pattern[j]) {
j++;
}
if (j == m) { /* 완전 일치! */
if (print) printf(" 위치 %d에서 발견\n", i - m + 1);
found++;
j = fail[j - 1]; /* 겹치는 다음 매치를 위해 */
}
}
return found;
}
int main(void) {
printf("=== 기본 동작 확인 ===\n");
const char *text = "ABABDABACDABABCABAB";
const char *pattern = "ABABC";
printf("텍스트: %s\n패턴 : %s\n", text, pattern);
int fail[16];
build_failure(pattern, 5, fail);
printf("실패 함수: ");
for (int i = 0; i < 5; i++) printf("%d ", fail[i]);
printf("(ABAB까지 일치 후 실패하면 AB(2)만큼은 살릴 수 있다는 뜻)\n");
comparisons = 0;
kmp_search(text, pattern, 1);
printf("\n=== 겹치는 매치도 놓치지 않는다 ===\n");
printf("텍스트: AAAA에서 패턴 AA 찾기\n");
kmp_search("AAAA", "AA", 1);
printf("\n=== 최악의 입력: KMP가 빛나는 순간 ===\n");
/* AAAA...AB 텍스트에서 AAAB 찾기: 브루트포스의 악몽 */
static char bad_text[10001];
memset(bad_text, 'A', 10000);
bad_text[10000] = '\0';
const char *bad_pattern = "AAAAAAAAAB"; /* A 9개 + B */
printf("텍스트: A x 10000, 패턴: A x 9 + B (일치 없음)\n");
comparisons = 0;
naive_search(bad_text, bad_pattern, 0);
printf("브루트포스: 비교 %ld회 (매 위치에서 9번씩 속는다!)\n", comparisons);
comparisons = 0;
kmp_search(bad_text, bad_pattern, 0);
printf("KMP : 비교 %ld회 (텍스트를 한 번만 훑는다)\n", comparisons);
printf("\n=== 일상 텍스트에선? ===\n");
const char *normal =
"the quick brown fox jumps over the lazy dog and the cat";
comparisons = 0;
int c1 = naive_search(normal, "the", 0);
long naive_cmp = comparisons;
comparisons = 0;
int c2 = kmp_search(normal, "the", 0);
printf("'the' 찾기(%d개): 브루트포스 %ld회, KMP %ld회 (별 차이 없다)\n",
c1, naive_cmp, comparisons);
(void)c2;
printf("\n정리:\n");
printf("1. KMP의 무기 = 실패 함수 (실패해도 배운 것을 버리지 않는다)\n");
printf("2. 텍스트 포인터가 후진하지 않으므로 스트림에도 사용 가능\n");
printf("3. 반복 패턴이 많은 데이터(DNA, 바이너리)에서 진가 발휘\n");
printf("4. 일상 텍스트에선 브루트포스도 나쁘지 않다 (불일치가 빨리 남)\n");
return 0;
}
$ ./build/naive_vs_kmp
=== 기본 동작 확인 ===
텍스트: ABABDABACDABABCABAB
패턴 : ABABC
실패 함수: 0 0 1 2 0 (ABAB까지 일치 후 실패하면 AB(2)만큼은 살릴 수 있다는 뜻)
위치 10에서 발견
=== 겹치는 매치도 놓치지 않는다 ===
텍스트: AAAA에서 패턴 AA 찾기
위치 0에서 발견
위치 1에서 발견
위치 2에서 발견
=== 최악의 입력: KMP가 빛나는 순간 ===
텍스트: A x 10000, 패턴: A x 9 + B (일치 없음)
브루트포스: 비교 99910회 (매 위치에서 9번씩 속는다!)
KMP : 비교 19991회 (텍스트를 한 번만 훑는다)
=== 일상 텍스트에선? ===
'the' 찾기(3개): 브루트포스 59회, KMP 55회 (별 차이 없다)
정리:
1. KMP의 무기 = 실패 함수 (실패해도 배운 것을 버리지 않는다)
2. 텍스트 포인터가 후진하지 않으므로 스트림에도 사용 가능
3. 반복 패턴이 많은 데이터(DNA, 바이너리)에서 진가 발휘
4. 일상 텍스트에선 브루트포스도 나쁘지 않다 (불일치가 빨리 남)
단순 탐색 vs KMP
그림은 글을 쓴 뒤 다시 돌린 결과입니다. 벤치마크라서 본문 표와 수치가 몇 % 다릅니다. 배속과 순서가 같은지를 보세요 — 절대값이 아니라 그게 이 측정이 말하려는 것입니다.
프로그램이 계산한 실패 함수 0 0 1 2 0이 2.1절에서 손으로 구한 것과 같습니다. 코드를 하나씩 봅시다.
2.3 실패 함수 만드는 코드 — 한 줄씩
void build_failure(const char *pattern, int m, int fail[]) {
fail[0] = 0;
int len = 0; /* 현재 일치 중인 접두사 길이 */
for (int i = 1; i < m; i++) {
/* 불일치면 더 짧은 접두사로 후퇴 (재귀적 후퇴!) */
while (len > 0 && pattern[i] != pattern[len]) {
len = fail[len - 1];
}
if (pattern[i] == pattern[len]) {
len++;
}
fail[i] = len;
}
}
| 부분 | 뜻 |
|---|---|
fail[0] = 0 |
한 글자짜리 문자열은 진접두사가 없으니 0 |
int len = 0 |
“지금까지 찾은 접두사-접미사의 길이”. 동시에 “다음에 비교할 패턴 글자의 위치”이기도 합니다 |
for (int i = 1; ...) |
두 번째 글자부터 차례로 fail[i]를 채웁니다 |
pattern[i] != pattern[len] |
새 글자 pattern[i]가, 지금까지의 접두사 바로 다음 글자 pattern[len]과 같은가? |
len = fail[len - 1] |
다르면 더 짧은 접두사-접미사로 후퇴. 이 한 줄이 KMP에서 가장 어려운 부분입니다 |
if (같으면) len++ |
같으면 접두사가 한 글자 길어집니다 |
fail[i] = len |
기록 |
len이 두 가지 뜻을 동시에 가진다는 점을 꼭 붙잡으세요. len = 2는 “길이 2짜리 접두사-접미사가 있다”는 뜻이고, 동시에 “그 접두사 다음 글자는 pattern[2]다”라는 뜻입니다. 그래서 pattern[i]를 pattern[len]과 비교하는 것입니다.
정말 그렇게 도는지 len의 변화를 한 단계씩 찍어 봤습니다. 먼저 ABABC입니다.
패턴 ABABC
i p[i] len(전) 후퇴 과정 p[i]==p[len]? len(후)=fail[i]
1 B 0 (없음) N (B vs A) 0
2 A 0 (없음) Y (A vs A) 1
3 B 1 (없음) Y (B vs B) 2
4 C 2 2->fail[1]=0 N (C vs A) 0
fail = 0 0 1 2 0
i = 4를 보세요. len = 2인 상태에서 C와 pattern[2] = A가 다릅니다. 그래서 len = fail[1] = 0으로 후퇴하고, C와 pattern[0] = A를 다시 비교합니다. 역시 다르니 len = 0으로 끝납니다.
이제 2.1절의 연습 문제 AABAACAABAA입니다.
패턴 AABAACAABAA
i p[i] len(전) 후퇴 과정 p[i]==p[len]? len(후)=fail[i]
1 A 0 (없음) Y (A vs A) 1
2 B 1 1->fail[0]=0 N (B vs A) 0
3 A 0 (없음) Y (A vs A) 1
4 A 1 (없음) Y (A vs A) 2
5 C 2 2->fail[1]=1 1->fail[0]=0 N (C vs A) 0
6 A 0 (없음) Y (A vs A) 1
7 A 1 (없음) Y (A vs A) 2
8 B 2 (없음) Y (B vs B) 3
9 A 3 (없음) Y (A vs A) 4
10 A 4 (없음) Y (A vs A) 5
fail = 0 1 0 1 2 0 1 2 3 4 5
i = 5가 핵심 장면입니다. len = 2(접두사 AA)인데 C가 pattern[2] = B와 다릅니다. fail[1] = 1로 후퇴하니 이번엔 C를 pattern[1] = A와 비교합니다. 또 다르니 fail[0] = 0으로 한 번 더 후퇴합니다. 후퇴가 두 번 연달아 일어났습니다. 그래서 이 후퇴는 if가 아니라 while이어야 합니다.
2.4 실험: while을 if로 바꾸면?
“한 번만 후퇴해도 되지 않나?”라는 생각이 들 수 있습니다. 직접 바꿔서 비교해 봤습니다.
AAAAB if판: 01232 while판: 01230 <-- 다르다!
ABABABC if판: 0012342 while판: 0012340 <-- 다르다!
AABAABAAC if판: 010123452 while판: 010123450 <-- 다르다!
ABCABDABCABC if판: 000120123453 while판: 000120123453 같음
AAABAAAB if판: 01212334 while판: 01201234 <-- 다르다!
어떤 패턴에서는 같고, 어떤 패턴에서는 다릅니다. “대부분의 테스트를 통과하면서 특정 패턴에서만 조용히 틀리는” 버그의 전형입니다. 틀린 실패 함수로 검색하면 무슨 일이 생길까요? AAAAB를 텍스트 AAAABAAB에서 찾아 봤습니다.
if판 fail = 0 1 2 3 2
while판 fail= 0 1 2 3 0
텍스트 "AAAABAAB" 에서 "AAAAB" 찾기
if판:
위치 0: "AAAAB"
위치 3: "ABAAB" <-- 가짜!
while판:
위치 0: "AAAAB"
if 버전은 없는 곳에서 매치를 찾았다고 보고합니다. 위치 0에서 매치한 뒤 j = fail[4]로 되돌리는데, 그 값이 2(틀림)라서 “AA는 이미 맞다”고 착각한 채 이어 가기 때문입니다. 이런 버그는 컴파일러가 잡아 주지 않고, 테스트 몇 개로도 안 잡힙니다. 알고리즘의 “왜”를 이해해야만 막을 수 있습니다.
왜 fail[len-1]로 후퇴하는 것이 맞을까요? 길이 len짜리 접두사-접미사가 안 통한다면, 그다음 후보는 “그 접두사 안에서의 접두사-접미사”입니다. 그리고 그 값이 바로 fail[len-1]입니다. 실패 함수가 자기 자신을 이용해 만들어지는 이 구조가 처음엔 어지럽지만, “안 되면 더 짧은 후보로 내려간다, 될 때까지”라는 한 문장으로 요약됩니다. 될 때까지이니 while입니다.
2.5 검색 코드 — 텍스트 포인터는 후진하지 않는다
int kmp_search(const char *text, const char *pattern, int print) {
int n = (int)strlen(text);
int m = (int)strlen(pattern);
int fail[256];
build_failure(pattern, m, fail);
int found = 0;
int j = 0; /* 패턴에서 일치한 길이 */
for (int i = 0; i < n; i++) { /* i는 절대 뒤로 안 간다! */
while (j > 0) {
comparisons++;
if (text[i] == pattern[j]) break;
j = fail[j - 1]; /* 실패 함수로 점프 */
}
if (j == 0) comparisons++;
if (text[i] == pattern[j]) {
j++;
}
if (j == m) { /* 완전 일치! */
if (print) printf(" 위치 %d에서 발견\n", i - m + 1);
found++;
j = fail[j - 1]; /* 겹치는 다음 매치를 위해 */
}
}
return found;
}
build_failure와 구조가 똑같습니다. 다만 이번에는 pattern[i] 대신 text[i]를 pattern[j]와 비교하고, 후퇴할 때 fail[j-1]을 씁니다. i는 for 루프에서 1씩 늘어날 뿐 되돌아가는 코드가 없습니다. 불일치가 나면 패턴 쪽 위치 j만 실패 함수를 따라 뒤로 갑니다.
comparisons 변수는 알고리즘의 일부가 아니라, 비교 횟수를 세어 출력하려고 붙인 계측 코드입니다. if (j == 0) comparisons++는 while을 한 번도 안 돌았을 때의 한 번 비교를 세는 것입니다. 이런 계측은 알고리즘의 동작을 눈으로 확인하는 좋은 습관입니다.
1.2절과 같은 예를 KMP로 따라가면 이렇습니다. i는 텍스트 위치, j는 “지금까지 일치한 패턴 글자 수”입니다.
i text[i] j(전) 동작 j(후)
0 A 0 A==A -> j++ 1
1 B 1 B==B -> j++ 2
2 A 2 A==A -> j++ 3
3 B 3 B==B -> j++ 4
4 D 4 D!=C -> j=fail[3]=2; D!=A -> j=fail[1]=0; D!=A 0
5 A 0 A==A -> j++ 1
6 B 1 B==B -> j++ 2
7 A 2 A==A -> j++ 3
8 C 3 C!=B -> j=fail[2]=1; C!=B -> j=fail[0]=0; C!=A 0
9 D 0 D!=A 0
10 A 0 A==A -> j++ 1
11 B 1 B==B -> j++ 2
12 A 2 A==A -> j++ 3
13 B 3 B==B -> j++ 4
14 C 4 C==C -> j++ 5 <- 발견
==> 위치 10에서 발견, j=fail[4]=0
15 A 0 A==A -> j++ 1
16 B 1 B==B -> j++ 2
17 A 2 A==A -> j++ 3
18 B 3 B==B -> j++ 4
총 비교 23회
i = 4에서 D를 만났을 때를 보세요. 브루트포스라면 i를 1로 되돌려 다시 시작했을 텐데, KMP는 i = 4에 머문 채 j만 4 → 2 → 0으로 줄이며 D를 세 번 비교했습니다. 그리고 i는 5로 넘어갑니다. 텍스트의 한 글자는 한 번 지나가면 끝입니다. 같은 예에서 브루트포스는 31회, KMP는 23회를 비교했습니다.
이 성질이 두 가지 결과를 낳습니다.
첫째, O(n + m)이 보장됩니다. i가 n번 전진합니다. j는 전진한 만큼만 후퇴할 수 있으니(0 아래로는 못 내려가므로) 후퇴 총량도 n을 넘지 못합니다. 실패 함수 계산이 같은 논리로 O(m)이니 전체가 O(n + m)입니다. 1.3절의 표에서 KMP의 비교 횟수가 항상 200만 근처였던 이유입니다. 텍스트 100만 글자를 한 번 훑으며 글자마다 많아야 두 번 비교한 것이죠.
둘째, 스트림 처리가 가능합니다. 텍스트를 되돌아 읽을 필요가 없으니, 네트워크 소켓이나 표준 입력처럼 한 번 지나가면 끝인 데이터에서도 검색할 수 있습니다. 파일 전체를 메모리에 올릴 수 없는 대용량 로그 처리에서 중요합니다. 다른 알고리즘들은 이게 안 됩니다. 보이어-무어는 아예 패턴 끝에서부터 봐야 하니까요.
2.6 실험: 매치 뒤에 j = 0으로 리셋하면?
if (j == m) { /* 완전 일치! */
...
j = fail[j - 1]; /* 겹치는 다음 매치를 위해 */
}
매치를 찾은 뒤 “이제 새로 시작하니 j = 0“이라고 쓰고 싶어집니다. 그렇게 바꿔서 AAAA에서 AA를 찾아 봤습니다.
j = 0 으로 리셋:
위치 0
위치 2
-> 2개
j = fail[j-1]:
위치 0
위치 1
위치 2
-> 3개
j = 0으로 리셋하면 위치 1을 놓칩니다. 위치 0에서 AA를 찾고 완전히 리셋하면 텍스트의 두 번째 A는 이미 지나간 뒤라 다시 못 씁니다. fail[j-1]로 되돌리면 “방금 매치의 뒷부분 A는 다음 매치의 앞부분 A로 살려 둔” 상태가 되어 위치 1도 찾습니다. 겹치는 매치가 필요 없는 상황(예: 단어 개수 세기)이라면 j = 0도 틀린 건 아니지만, 정의대로 “모든 위치”를 찾으려면 이렇게 해야 합니다.
2.7 정직한 관찰
실행 결과의 마지막 부분이 중요합니다.
'the' 찾기(3개): 브루트포스 59회, KMP 55회 (별 차이 없다)
영어 문장에서는 브루트포스도 충분히 빠릅니다. 1.2절 표에서 봤듯 불일치가 대개 첫 글자나 둘째 글자에서 나기 때문입니다. 브루트포스의 최악 O(n × m)은 일상 텍스트에서는 거의 일어나지 않습니다.
그렇다면 KMP를 왜 배울까요?
- 최악이 보장됩니다. 1.3절의 12초짜리 입력에서도 4ms입니다. 사용자가 입력하는 패턴을 검색하는 서버라면, 악의적인 입력에도 느려지지 않는다는 보장이 필요합니다.
- 반복 많은 데이터에서 진가를 발휘합니다. DNA 서열(ACGT 네 글자뿐), 바이너리 데이터, 로그의 반복 패턴처럼 “비슷한 것이 계속 나오는” 데이터입니다.
- 스트림 처리가 됩니다. 2.5절에서 본 성질입니다.
- 실패 함수 자체가 유용합니다. 문자열의 주기 찾기 같은 문제에 그대로 쓰입니다(5절 Z 알고리즘에서 그 형제를 만납니다).
“이론적으로 더 빠른 알고리즘이 실전에서 항상 빠른 것은 아니다.” 이것을 숫자로 정직하게 확인하는 것도 공부입니다. 6절에서 네 알고리즘을 실제로 경주시켜 보면 더 분명해집니다.
작은 한계 하나: 예제의
int fail[256];은 패턴이 256글자를 넘으면 배열 밖에 씁니다(4주차에서 본 바로 그 사고). 학습용이라 고정 크기로 두었지만, 실전 코드라면malloc으로m칸을 잡거나 길이를 검사해야 합니다. 라빈-카프의p_hash[8], Z 알고리즘의joined[1024]도 같은 종류의 제한입니다.
3. 라빈-카프: 해시로 창문 밀기
3.1 문자열을 숫자로
13주차에서 배운 해시를 문자열 검색에 쓰면 어떻게 될까요? 발상은 단순합니다.
- 패턴의 해시값을 계산한다.
- 텍스트에서 길이 m짜리 창(window)을 한 칸씩 밀면서, 창의 해시값을 패턴의 해시값과 비교한다.
- 해시가 같을 때만 실제 글자를 하나씩 확인한다.
글자 m개를 비교하는 대신 숫자 하나를 비교하니 빠를 것 같습니다. 그런데 문제가 하나 있습니다. 창마다 해시를 새로 계산하면 창 하나에 O(m)이 들고, 창이 n개니 전체가 O(n × m)입니다. 브루트포스와 똑같아집니다. 라빈-카프의 진짜 발명은 이 계산을 O(1)로 줄이는 롤링 해시입니다.
해시를 어떻게 만드는지부터 봅시다. 문자열을 256진법 숫자로 봅니다. 글자 하나가 한 자리이고, 자릿값은 256의 거듭제곱입니다. "abc"라면 이렇습니다.
'a'=97 'b'=98 'c'=99
hash("abc") = 97*256^2 + 98*256 + 99 = 6382179
십진수 123이 1×100 + 2×10 + 3인 것과 같은 구조입니다. 이제 창을 한 칸 밀어 "bcd"의 해시를 구한다고 합시다.
hash("bcd") = 98*256^2 + 99*256 + 100 = 6447972
(hash(abc) - 97*65536) * 256 + 100 = 6447972
두 값이 같습니다. 즉 "bcd"의 해시는 "abc"의 해시에서 앞글자 a의 자릿값을 빼고, 256을 곱하고, 새 글자 d를 더하면 나옵니다. 십진수로 말하면 123에서 234로 가는 방법입니다. 100을 빼고(→ 23), 10을 곱하고(→ 230), 4를 더합니다(→ 234). 처음부터 다시 계산하지 않고 뺄셈 하나, 곱셈 하나, 덧셈 하나로 끝납니다. 이것이 롤링 해시입니다.
숫자가 금방 커진다는 문제만 남습니다. 글자 4개면 256⁴ = 43억이고, 글자 8개면 2⁶⁴를 넘어 unsigned long long에도 안 들어갑니다. 그래서 큰 소수 MOD로 나눈 나머지만 씁니다. 나머지 연산은 덧셈·곱셈과 잘 어울려서((a × b) % M = ((a % M) × (b % M)) % M), 매 단계마다 나머지를 취해도 결과가 같습니다.
3.2 예제: rabin_karp.c
examples/rabin_karp.c:
/*
* rabin_karp.c - 라빈-카프: 해시로 문자열 찾기
* 16주차: 문자열 알고리즘
*
* 13주차 해시의 문자열 검색 응용입니다.
*
* 아이디어:
* 1. 패턴의 해시값을 계산한다
* 2. 텍스트의 모든 "길이 m 창(window)"의 해시와 비교한다
* 3. 해시가 같으면 그때만 실제 문자 비교 (해시 충돌 대비!)
*
* 핵심 기술 = 롤링 해시:
* 창을 한 칸 밀 때 해시를 처음부터 다시 계산하지 않고
* "나가는 문자 빼고, 들어오는 문자 더하기"로 O(1) 갱신!
*
* 특기: 패턴 여러 개를 동시에 찾기 (해시 셋에 넣으면 끝)
*/
#include <stdio.h>
#include <string.h>
#define BASE 256 /* 문자 하나 = 256진법 한 자리 */
#define MOD 1000000007ULL /* 큰 소수로 나눈 나머지 */
static long hash_computes, char_compares;
/* 다항식 해시: s[0]*B^(m-1) + s[1]*B^(m-2) + ... + s[m-1] */
unsigned long long poly_hash(const char *s, int m) {
unsigned long long h = 0;
for (int i = 0; i < m; i++) {
h = (h * BASE + (unsigned char)s[i]) % MOD;
hash_computes++;
}
return h;
}
int rabin_karp(const char *text, const char *pattern, int print) {
int n = (int)strlen(text);
int m = (int)strlen(pattern);
if (m > n) return 0;
unsigned long long p_hash = poly_hash(pattern, m);
unsigned long long t_hash = poly_hash(text, m); /* 첫 창 */
/* B^(m-1) % MOD: 창에서 "나가는 문자"의 자릿값 */
unsigned long long high = 1;
for (int i = 0; i < m - 1; i++) high = (high * BASE) % MOD;
int found = 0;
for (int i = 0; ; i++) {
if (t_hash == p_hash) {
/* 해시 일치 -> 진짜인지 문자로 확인 (충돌 가능성!) */
int j = 0;
while (j < m) {
char_compares++;
if (text[i + j] != pattern[j]) break;
j++;
}
if (j == m) {
if (print) printf(" 위치 %d에서 발견\n", i);
found++;
}
}
if (i + m >= n) break;
/* 롤링: 나가는 문자 빼고, 밀고, 들어오는 문자 더하기 */
unsigned long long out = ((unsigned char)text[i] * high) % MOD;
t_hash = (t_hash + MOD - out) % MOD; /* 음수 방지 +MOD */
t_hash = (t_hash * BASE + (unsigned char)text[i + m]) % MOD;
hash_computes++; /* O(1) 갱신! */
}
return found;
}
/* ---------- 멀티 패턴 검색: 라빈-카프의 특기 ---------- */
void multi_search(const char *text, const char *patterns[], int count, int m) {
/* 같은 길이 m의 패턴 여러 개의 해시를 미리 계산 */
unsigned long long p_hash[8];
for (int p = 0; p < count; p++) {
p_hash[p] = poly_hash(patterns[p], m);
}
int n = (int)strlen(text);
unsigned long long t_hash = poly_hash(text, m);
unsigned long long high = 1;
for (int i = 0; i < m - 1; i++) high = (high * BASE) % MOD;
for (int i = 0; ; i++) {
for (int p = 0; p < count; p++) {
if (t_hash == p_hash[p] &&
strncmp(text + i, patterns[p], m) == 0) {
printf(" 위치 %2d: \"%s\"\n", i, patterns[p]);
}
}
if (i + m >= n) break;
unsigned long long out = ((unsigned char)text[i] * high) % MOD;
t_hash = (t_hash + MOD - out) % MOD;
t_hash = (t_hash * BASE + (unsigned char)text[i + m]) % MOD;
}
}
int main(void) {
printf("=== 라빈-카프 기본 동작 ===\n");
const char *text = "abracadabra abracadabra";
printf("텍스트: %s\n패턴 : abra\n", text);
hash_computes = char_compares = 0;
rabin_karp(text, "abra", 1);
printf("해시 연산 %ld회, 문자 비교 %ld회\n", hash_computes, char_compares);
printf("(문자 비교는 해시가 일치한 곳에서만 일어난다!)\n");
printf("\n=== 롤링 해시 감각 잡기 ===\n");
printf("\"abc\"의 다음 창 \"bcd\"의 해시:\n");
printf(" hash(bcd) = (hash(abc) - 'a'x256^2) x 256 + 'd'\n");
printf(" 처음부터 다시 계산? NO. 갱신은 곱셈 2번 + 덧셈 = O(1)\n");
printf("\n=== 멀티 패턴 동시 검색 (길이 4 단어들) ===\n");
const char *log_text = "user cats love dogs and cats hate rats";
const char *words[] = {"cats", "dogs", "rats"};
printf("텍스트: %s\n", log_text);
printf("패턴 3개 {cats, dogs, rats}를 한 번의 순회로:\n");
multi_search(log_text, words, 3, 4);
printf("\n정리:\n");
printf("1. 평균 O(n + m), 최악(충돌 연발)은 O(n*m) - 큰 소수 MOD로 희박하게\n");
printf("2. 해시 일치 != 발견. 반드시 문자로 재확인!\n");
printf("3. 강점: 멀티 패턴, 2차원 패턴 매칭, 표절 검사(문서 지문)\n");
printf("4. 13주차 해시 + 나머지 연산의 합작품\n");
return 0;
}
$ ./build/rabin_karp
=== 라빈-카프 기본 동작 ===
텍스트: abracadabra abracadabra
패턴 : abra
위치 0에서 발견
위치 7에서 발견
위치 12에서 발견
위치 19에서 발견
해시 연산 27회, 문자 비교 16회
(문자 비교는 해시가 일치한 곳에서만 일어난다!)
=== 롤링 해시 감각 잡기 ===
"abc"의 다음 창 "bcd"의 해시:
hash(bcd) = (hash(abc) - 'a'x256^2) x 256 + 'd'
처음부터 다시 계산? NO. 갱신은 곱셈 2번 + 덧셈 = O(1)
=== 멀티 패턴 동시 검색 (길이 4 단어들) ===
텍스트: user cats love dogs and cats hate rats
패턴 3개 {cats, dogs, rats}를 한 번의 순회로:
위치 5: "cats"
위치 15: "dogs"
위치 24: "cats"
위치 34: "rats"
정리:
1. 평균 O(n + m), 최악(충돌 연발)은 O(n*m) - 큰 소수 MOD로 희박하게
2. 해시 일치 != 발견. 반드시 문자로 재확인!
3. 강점: 멀티 패턴, 2차원 패턴 매칭, 표절 검사(문서 지문)
4. 13주차 해시 + 나머지 연산의 합작품
“해시 연산 27회”는 첫 창 4글자(4회) + 패턴 4글자(4회) + 롤링 19회입니다. 텍스트 23글자에서 창은 20개이고, 첫 창을 뺀 19개를 롤링으로 만들었으니 딱 맞습니다. “문자 비교 16회”는 매치 4개 × 4글자입니다. 즉 해시가 같은데 문자열이 다른 경우(가짜 양성)가 한 번도 없었습니다.
3.3 코드 읽기 — 해시 함수와 롤링
#define BASE 256 /* 문자 하나 = 256진법 한 자리 */
#define MOD 1000000007ULL /* 큰 소수로 나눈 나머지 */
unsigned long long poly_hash(const char *s, int m) {
unsigned long long h = 0;
for (int i = 0; i < m; i++) {
h = (h * BASE + (unsigned char)s[i]) % MOD;
hash_computes++;
}
return h;
}
| 부분 | 뜻 |
|---|---|
BASE 256 |
진법. char가 가질 수 있는 값이 256가지라서 |
MOD 1000000007ULL |
10억 7. 알고리즘 문제에서 관습적으로 쓰는 큰 소수입니다. ULL은 unsigned long long 상수라는 표시(2주차) |
h * BASE + s[i] |
“지금까지 숫자에 한 자리 붙이기”. 12에 3을 붙여 123을 만드는 것과 같습니다 |
(unsigned char)s[i] |
char가 음수일 수 있는 문제(4주차 ctype 함정과 같은 이유)를 막습니다. 한글처럼 128 이상인 바이트가 오면 char로는 음수라서 해시가 어긋납니다 |
% MOD |
매 단계 나머지를 취해 넘침을 막습니다 |
이 함수를 “다항식 해시”라고도 부릅니다. s[0]·B^(m-1) + s[1]·B^(m-2) + ... + s[m-1]이 B에 대한 다항식이기 때문입니다.
롤링은 검색 함수 안에 있습니다.
/* B^(m-1) % MOD: 창에서 "나가는 문자"의 자릿값 */
unsigned long long high = 1;
for (int i = 0; i < m - 1; i++) high = (high * BASE) % MOD;
...
/* 롤링: 나가는 문자 빼고, 밀고, 들어오는 문자 더하기 */
unsigned long long out = ((unsigned char)text[i] * high) % MOD;
t_hash = (t_hash + MOD - out) % MOD; /* 음수 방지 +MOD */
t_hash = (t_hash * BASE + (unsigned char)text[i + m]) % MOD;
high는256^(m-1) % MOD, 즉 창의 맨 앞 글자가 차지하는 자릿값입니다."abc"에서a의 자릿값 256²에 해당합니다. 한 번만 계산해 둡니다.out은 나가는 글자 × 자릿값."abc"→"bcd"에서97 × 65536입니다.t_hash + MOD - out: 빼기. 그런데 왜MOD를 더할까요?t_hash * BASE + text[i + m]: 한 자리 밀고 새 글자 붙이기.
3.4 실험: + MOD를 빼면?
t_hash - out이 음수가 될 수 있습니다. C에서 음수의 나머지는 어떻게 될까요?
-5 % 3 = -2
(-5 % 3 + 3) % 3 = 1
C의 %는 부호를 왼쪽 피연산자에서 가져오므로(3주차) -5 % 3은 -2입니다. 수학에서 기대하는 1이 아닙니다. 해시값이 음수가 되면 패턴 해시(양수)와 절대 같아지지 않으니 매치를 전부 놓칩니다.
그런데 예제의 변수는 unsigned long long입니다. 부호가 없는데 음수가 될 리 없다고요? 부호 없는 타입에서 작은 수에서 큰 수를 빼면 2주차에서 본 감기(wrap-around)가 일어납니다.
t_hash=5, out=9 (unsigned long long)
(t_hash - out) % MOD = 582344004 <- 엉뚱한 값
(t_hash + MOD - out) % MOD = 1000000003 <- 우리가 원한 -4 mod MOD
5 - 9가 -4가 아니라 18446744073709551612가 되고, 그것의 나머지는 아무 의미 없는 숫자입니다. MOD를 먼저 더하면 t_hash와 out이 둘 다 MOD보다 작으므로 t_hash + MOD - out은 항상 양수이고, 나머지를 취하면 원하는 값이 나옵니다. 모듈러 연산으로 뺄셈을 할 때는 항상 (a + MOD - b) % MOD. 이번 주뿐 아니라 앞으로 나머지 연산이 나오는 모든 코드에서 반복될 관용구입니다.
3.5 실험: MOD를 작게 하면 — 충돌
“해시가 같으면 문자열도 같다”는 보장은 없습니다. 서로 다른 문자열이 같은 나머지를 가질 수 있으니까요(13주차의 충돌). 얼마나 자주 일어날까요? MOD를 일부러 작게 해서 같은 검색을 돌려 봤습니다.
작은 MOD 로 충돌 유도:
MOD=7 해시 일치 10회, 진짜 4회, 가짜 양성 6회
MOD=101 해시 일치 4회, 진짜 4회, 가짜 양성 0회
MOD=1009 해시 일치 4회, 진짜 4회, 가짜 양성 0회
MOD=1000000007 해시 일치 4회, 진짜 4회, 가짜 양성 0회
MOD = 7이면 해시값이 0~6, 일곱 가지뿐이라 창 20개 중 10개가 패턴과 같은 해시를 냅니다. 그중 진짜는 4개, 나머지 6개는 가짜 양성입니다. 이때 코드가 문자 비교로 재확인하지 않았다면 6군데를 잘못 보고했을 겁니다.
if (t_hash == p_hash) {
/* 해시 일치 -> 진짜인지 문자로 확인 (충돌 가능성!) */
int j = 0;
while (j < m) {
char_compares++;
if (text[i + j] != pattern[j]) break;
j++;
}
if (j == m) { ... 발견 ... }
}
그래서 이 재확인은 선택이 아니라 필수입니다. 13주차에서 “같은 버킷이어도 strcmp로 확인하라”고 했던 것과 같은 이야기입니다. 큰 소수를 쓰면 가짜 양성이 드물어져 평균 O(n + m)이 되지만, 최악(충돌이 연발하는 악의적 입력)은 여전히 O(n × m)입니다. 정리 첫 줄이 그 뜻입니다.
3.6 라빈-카프의 특기: 멀티 패턴
라빈-카프는 패턴 하나를 찾을 때는 보이어-무어(4절)에 밀립니다. 그런데 대체 불가능한 특기가 있습니다.
for (int i = 0; ; i++) {
for (int p = 0; p < count; p++) {
if (t_hash == p_hash[p] &&
strncmp(text + i, patterns[p], m) == 0) {
printf(" 위치 %2d: \"%s\"\n", i, patterns[p]);
}
}
if (i + m >= n) break;
... 롤링 ...
}
패턴 여러 개를 한 번의 텍스트 순회로 찾습니다. 텍스트 창의 해시를 한 번 계산해 두고, 그것을 패턴 해시 목록과 대조하면 되니까요. 예제는 패턴 3개를 배열에 두고 하나씩 비교하지만, 패턴이 1,000개라면 패턴 해시들을 13주차의 해시 셋에 넣어 O(1)에 대조하면 됩니다. 패턴이 아무리 많아도 텍스트는 한 번만 훑습니다. KMP나 보이어-무어로 같은 일을 하려면 패턴 수만큼 텍스트를 다시 훑어야 합니다.
&&의 왼쪽이 해시 비교, 오른쪽이 strncmp인 순서도 의미가 있습니다. 3주차에서 배운 단락 평가 덕분에, 해시가 다르면 strncmp는 아예 실행되지 않습니다. 비싼 검사를 뒤에 두는 관용구입니다.
실사용처가 분명합니다.
- 표절 검사: 문서를 일정 길이 조각으로 나눠 해시(문서 지문)를 만들고, 다른 문서의 지문과 대조합니다. 실제 표절 검사 서비스의 기본 원리입니다.
- 중복 블록 탐지:
rsync는 파일을 블록으로 나눈 롤링 해시로 “이미 상대에게 있는 블록”을 찾아 바뀐 부분만 전송합니다. - 2차원 패턴 매칭: 이미지에서 부분 이미지 찾기. 행 방향과 열 방향으로 해시를 두 번 롤링합니다.
4. 보이어-무어: 건너뛰기의 미학
4.1 발상의 전환
지금까지의 알고리즘은 전부 텍스트를 한 글자도 빠짐없이 봤습니다. KMP도 텍스트를 한 번은 훑습니다. 그래서 아무리 잘해도 O(n)이 하한입니다.
보이어-무어는 그 하한을 깹니다. 텍스트의 상당 부분을 쳐다보지도 않습니다. 비결은 두 가지 발상의 전환입니다.
- 패턴을 뒤에서부터 비교한다.
- 불일치한 텍스트 글자를 보고 왕창 건너뛴다.
예를 봅시다. 텍스트 HERE IS A SIMPLE EXAMPLE에서 EXAMPLE을 찾습니다. 패턴을 위치 0에 놓고, 패턴의 마지막 글자 E부터 텍스트와 비교합니다.
HERE IS A SIMPLE EXAMPLE
EXAMPLE
^ 패턴 끝의 E vs 텍스트의 S(위치 6). 불일치!
여기서 중요한 관찰이 나옵니다. S는 패턴 EXAMPLE 어디에도 없습니다. 그렇다면 패턴을 오른쪽으로 1칸, 2칸, …, 6칸 옮겨 봐야 어느 위치에서든 이 S와 겹치게 되고, S는 패턴의 어떤 글자와도 맞지 않으니 반드시 실패합니다. 그러니 그 위치들은 시도할 필요조차 없습니다. 패턴을 S 바로 다음으로 통째로 옮깁니다.
HERE IS A SIMPLE EXAMPLE
EXAMPLE <- 7칸 통째로 점프
텍스트의 0~5번 글자는 읽지도 않았습니다. 비교 한 번으로 7칸을 건너뛴 것입니다. 이것이 최선의 경우 O(n/m), 즉 텍스트 길이보다 적게 보는 서브리니어(sublinear) 성능의 비결입니다.
4.2 예제: boyer_moore.c
examples/boyer_moore.c:
/*
* boyer_moore.c - 보이어-무어: 건너뛰기의 미학
* 16주차: 문자열 알고리즘
*
* 실전에서 가장 빠른 축의 검색 알고리즘 (grep의 핵심!).
*
* 두 가지 발상의 전환:
* 1. 패턴을 "뒤에서부터" 비교한다
* 2. 불일치 문자를 보고 패턴을 왕창 "건너뛴다"
*
* 나쁜 문자(bad character) 규칙:
* 텍스트의 불일치 문자가 패턴에 없으면? 패턴 길이만큼 점프!
* 있으면? 그 문자가 정렬되도록 이동.
*
* 결과: 긴 패턴일수록 빨라진다 (텍스트 문자를 안 보고 지나간다!)
* 최선의 경우 O(n/m) - 서브리니어!
*/
#include <stdio.h>
#include <string.h>
#define ALPHABET 256
static long comparisons;
/* 나쁜 문자 표: last[c] = 패턴에서 문자 c의 마지막 위치 (-1 = 없음) */
void build_last(const char *pattern, int m, int last[]) {
for (int c = 0; c < ALPHABET; c++) last[c] = -1;
for (int i = 0; i < m; i++) {
last[(unsigned char)pattern[i]] = i;
}
}
int boyer_moore(const char *text, const char *pattern, int print) {
int n = (int)strlen(text);
int m = (int)strlen(pattern);
int last[ALPHABET];
build_last(pattern, m, last);
int found = 0;
int shift = 0; /* 패턴의 현재 정렬 위치 */
while (shift + m <= n) {
int j = m - 1; /* 뒤에서부터 비교! */
while (j >= 0) {
comparisons++;
if (pattern[j] != text[shift + j]) break;
j--;
}
if (j < 0) {
if (print) printf(" 위치 %d에서 발견\n", shift);
found++;
shift++; /* (단순화: 한 칸 이동. good suffix 규칙은 심화) */
} else {
char bad = text[shift + j];
int last_pos = last[(unsigned char)bad];
/* 나쁜 문자가 패턴의 last_pos에 있다면 그게 정렬되도록 이동.
* 없으면(-1) 불일치 지점 다음으로 통째로 점프! */
int jump = j - last_pos;
if (jump < 1) jump = 1;
shift += jump;
}
}
return found;
}
int naive_count(const char *text, const char *pattern) {
int n = (int)strlen(text), m = (int)strlen(pattern);
int found = 0;
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m) {
comparisons++;
if (text[i + j] != pattern[j]) break;
j++;
}
if (j == m) found++;
}
return found;
}
int main(void) {
printf("=== 건너뛰기 데모 ===\n");
const char *text = "HERE IS A SIMPLE EXAMPLE";
const char *pattern = "EXAMPLE";
printf("텍스트: %s\n패턴 : %s (길이 7)\n\n", text, pattern);
printf("1차 정렬:\n HERE IS A SIMPLE EXAMPLE\n EXAMPLE\n");
printf(" 패턴 끝 'E' vs 텍스트 'S'(위치6) -> 불일치!\n");
printf(" 'S'는 패턴에 없다 -> 7칸 통째로 점프!!\n");
printf(" (텍스트의 0~5번 문자는 쳐다보지도 않았다)\n\n");
comparisons = 0;
boyer_moore(text, pattern, 1);
printf("총 비교: %ld회 (텍스트 길이 %zu인데!)\n",
comparisons, strlen(text));
printf("\n=== 브루트포스와 대결 ===\n");
/* 영어 문장 스타일의 큰 텍스트 */
static char big[100001];
const char *chunk = "the quick brown fox jumps over the lazy dog. ";
int clen = (int)strlen(chunk);
for (int i = 0; i + clen < 100000; i += clen) {
memcpy(big + i, chunk, clen);
}
big[100000] = '\0';
const char *needle = "lazy dog. the quick";
comparisons = 0;
int c1 = naive_count(big, needle);
long naive_cmp = comparisons;
comparisons = 0;
int c2 = boyer_moore(big, needle, 0);
long bm_cmp = comparisons;
printf("텍스트 10만 자에서 \"%s\"(길이 %zu) 찾기\n", needle, strlen(needle));
printf("브루트포스 : %d개 발견, 비교 %ld회\n", c1, naive_cmp);
printf("보이어-무어: %d개 발견, 비교 %ld회 (%.1f배 적게!)\n",
c2, bm_cmp, (double)naive_cmp / bm_cmp);
printf("\n=== 패턴이 길수록 더 빨라진다! (없는 패턴으로 순수 점프력 측정) ===\n");
const char *needles[] = {"zebra", "zebras and pythons", "zebras and pythons make strange friends"};
for (int i = 0; i < 3; i++) {
comparisons = 0;
boyer_moore(big, needles[i], 0);
printf(" 패턴 길이 %2zu: 비교 %7ld회\n",
strlen(needles[i]), comparisons);
}
printf("(패턴이 길수록 한 번에 더 멀리 점프! 다른 알고리즘과 정반대)\n");
printf("\n정리:\n");
printf("1. 뒤에서 비교 + 나쁜 문자 점프 = 텍스트 대부분을 건너뜀\n");
printf("2. 알파벳이 크고(영어 등) 패턴이 길수록 유리\n");
printf("3. grep이 빠른 비밀이 이것 (실제로는 good suffix 규칙도 추가)\n");
printf("4. 약점: 알파벳이 작으면(DNA: 4글자) 점프가 짧다 -> KMP 고려\n");
return 0;
}
$ ./build/boyer_moore
=== 건너뛰기 데모 ===
텍스트: HERE IS A SIMPLE EXAMPLE
패턴 : EXAMPLE (길이 7)
1차 정렬:
HERE IS A SIMPLE EXAMPLE
EXAMPLE
패턴 끝 'E' vs 텍스트 'S'(위치6) -> 불일치!
'S'는 패턴에 없다 -> 7칸 통째로 점프!!
(텍스트의 0~5번 문자는 쳐다보지도 않았다)
위치 17에서 발견
총 비교: 15회 (텍스트 길이 24인데!)
=== 브루트포스와 대결 ===
텍스트 10만 자에서 "lazy dog. the quick"(길이 19) 찾기
브루트포스 : 2221개 발견, 비교 139950회
보이어-무어: 2221개 발견, 비교 55526회 (2.5배 적게!)
=== 패턴이 길수록 더 빨라진다! (없는 패턴으로 순수 점프력 측정) ===
패턴 길이 5: 비교 22219회
패턴 길이 18: 비교 8890회
패턴 길이 39: 비교 4442회
(패턴이 길수록 한 번에 더 멀리 점프! 다른 알고리즘과 정반대)
정리:
1. 뒤에서 비교 + 나쁜 문자 점프 = 텍스트 대부분을 건너뜀
2. 알파벳이 크고(영어 등) 패턴이 길수록 유리
3. grep이 빠른 비밀이 이것 (실제로는 good suffix 규칙도 추가)
4. 약점: 알파벳이 작으면(DNA: 4글자) 점프가 짧다 -> KMP 고려
보이어-무어
그림은 글을 쓴 뒤 다시 돌린 결과입니다. 벤치마크라서 본문 표와 수치가 몇 % 다릅니다. 배속과 순서가 같은지를 보세요 — 절대값이 아니라 그게 이 측정이 말하려는 것입니다.
“총 비교 15회 (텍스트 길이 24인데!)” — 텍스트보다 적게 비교했습니다. 앞의 어떤 알고리즘도 하지 못한 일입니다.
4.3 손으로 따라가기 — 15회는 어디서 나왔나
shift는 패턴을 텍스트의 어디에 놓았는지, j는 패턴에서 비교 중인 위치(끝에서부터)입니다. 프로그램에 추적 출력을 붙여 다섯 단계를 전부 찍었습니다.
1단계 shift=0 HERE IS A SIMPLE EXAMPLE
EXAMPLE
-> p[6]='E' vs t[6]='S' 불일치. 'S'의 last=-1, jump = 6 - (-1) = 7
2단계 shift=7 HERE IS A SIMPLE EXAMPLE
EXAMPLE
-> p[6]='E' vs t[13]='P' 불일치. 'P'의 last=4, jump = 6 - (4) = 2
3단계 shift=9 HERE IS A SIMPLE EXAMPLE
EXAMPLE
-> p[2]='A' vs t[11]='I' 불일치. 'I'의 last=-1, jump = 2 - (-1) = 3
4단계 shift=12 HERE IS A SIMPLE EXAMPLE
EXAMPLE
-> p[6]='E' vs t[18]='X' 불일치. 'X'의 last=1, jump = 6 - (1) = 5
5단계 shift=17 HERE IS A SIMPLE EXAMPLE
EXAMPLE
-> 전부 일치! 위치 17. 한 칸 이동
총 비교 15회
단계별 비교 횟수를 세면 1 + 1 + 5 + 1 + 7 = 15입니다.
- 1단계:
S는 패턴에 없으니(last = -1)j + 1 = 7칸 점프. 텍스트 0~5번은 안 봤습니다. - 2단계:
P는 패턴에 있습니다.EXAMPLE에서P는 4번 위치입니다. 지금P가 패턴의 6번 자리와 겹쳐 있으니, 패턴을6 - 4 = 2칸 밀면 패턴의P가 텍스트의P위로 옵니다. 그 전의 1칸 이동은P가L이나E와 만날 뿐이라 시도할 가치가 없습니다. - 3단계: 이번에는
E,L,P,M이 뒤에서부터 4글자나 맞았습니다(SIMPLE의 뒷부분과EXAMPLE의 뒷부분이 같으니까요). 5번째 비교에서I와A가 불일치.I는 패턴에 없으니j + 1 = 3칸 점프. - 4단계:
X는 패턴의 1번 위치.6 - 1 = 5칸 점프하면 패턴의X가 텍스트의X에 옵니다. - 5단계: 7글자 전부 일치. 발견.
2단계에서 3단계로 갈 때 텍스트를 뒤에서부터 비교하는 이유가 드러납니다. 뒤에서 비교하면 불일치가 나는 글자가 “창의 오른쪽 끝 근처”에 있게 되고, 그 글자를 기준으로 점프하니 멀리 뛸 수 있습니다. 앞에서부터 비교했다면 첫 글자에서 불일치가 나도 한 칸밖에 못 옮깁니다.
4.4 나쁜 문자 규칙과 점프 하한
/* 나쁜 문자 표: last[c] = 패턴에서 문자 c의 마지막 위치 (-1 = 없음) */
void build_last(const char *pattern, int m, int last[]) {
for (int c = 0; c < ALPHABET; c++) last[c] = -1;
for (int i = 0; i < m; i++) {
last[(unsigned char)pattern[i]] = i;
}
}
전처리는 이게 전부입니다. 글자마다 패턴에서 마지막으로 등장하는 위치를 적은 256칸 배열입니다. EXAMPLE이면 E는 0과 6에 있지만 마지막인 6이 기록됩니다. 왜 마지막일까요? 점프한 뒤 텍스트의 그 글자와 패턴의 그 글자가 겹치게 하려면 가장 오른쪽 등장 위치에 맞춰야 합니다. 더 왼쪽 등장에 맞추면 그 사이의 등장을 건너뛰어 매치를 놓칠 수 있습니다.
점프 계산은 세 줄입니다.
char bad = text[shift + j];
int last_pos = last[(unsigned char)bad];
int jump = j - last_pos;
if (jump < 1) jump = 1;
shift += jump;
- 패턴에 없는 글자(
last_pos == -1):jump = j + 1. 불일치 지점 바로 다음으로 통째로 넘어갑니다. 패턴 끝에서 실패했다면j = m - 1이니jump = m, 패턴 길이만큼 뜁니다. - 패턴에 있는 글자: 패턴의 그 글자가 텍스트의 나쁜 문자와 정렬되도록 이동합니다.
실험: if (jump < 1) jump = 1;을 빼면? 이 줄이 왜 있는지 실험해 봅시다. 패턴 ABAB(last[A] = 2, last[B] = 3)를 텍스트 XAAB에서 찾습니다.
패턴 ABAB 의 last: A=2 B=3
shift=0: j=1 에서 불일치, t[1]='A' 의 last=2 -> jump = 1 - 2 = -1 <-- 뒤로 간다!
shift=-1: j=3 에서 불일치, t[2]='A' 의 last=2 -> jump = 3 - 2 = 1
shift=0: j=1 에서 불일치, t[1]='A' 의 last=2 -> jump = 1 - 2 = -1 <-- 뒤로 간다!
shift=-1: ...
(5번 만에 강제 종료. 하한이 없으면 shift 가 음수가 되어 배열 밖을 읽는다)
뒤에서부터 B, A가 맞고 세 번째(j = 1)에서 A가 패턴의 B와 불일치했습니다. 나쁜 문자 A의 마지막 위치는 2인데 지금 j = 1이라 jump = 1 - 2 = -1, 패턴이 뒤로 갑니다. 그러면 shift = -1이 되어 text[-1]을 읽고(배열 밖, 4주차의 사고), 다음 단계에서 다시 0으로 돌아와 같은 일을 영원히 반복합니다. 하한 한 줄이 무한 루프와 메모리 침범을 동시에 막습니다. 나쁜 문자 규칙만으로는 “뒤로 가야 한다”는 결론이 나올 수 있으니, 그럴 땐 최소 1칸은 앞으로 가는 것으로 대신하는 것입니다.
4.5 실험: 패턴 길이와 알파벳 크기
실행 결과의 마지막 실험이 보이어-무어의 정체성을 보여 줍니다.
| 패턴 길이 | 비교 횟수 |
|---|---|
| 5 | 22,219 |
| 18 | 8,890 |
| 39 | 4,442 |
패턴이 길어질수록 비교가 줄어듭니다. 다른 모든 검색 알고리즘과 정반대입니다. 이유는 점프 거리의 최대치가 패턴 길이이기 때문입니다. 패턴이 39글자면 운 좋을 때 한 번에 39칸을 건너뜁니다. 텍스트 10만 글자를 4,442번만 보고 끝냈으니 텍스트의 96%를 안 보고 지나간 셈입니다.
그럼 알파벳이 작으면 어떻게 될까요? DNA 서열은 A, C, G, T 네 글자뿐입니다. 텍스트 10만 글자를 무작위 DNA로 만들고 같은 실험을 했습니다.
패턴 길이 영어 텍스트 비교 DNA 텍스트(ACGT) 비교
5 22219 51757
18 8890 77696
39 4442 58543
DNA에서는 패턴이 길어져도 비교가 줄지 않습니다. 오히려 늘기도 합니다. 글자가 네 종류뿐이니 텍스트의 어떤 글자든 패턴 안에 거의 항상 있고, 그것도 패턴 끝 근처에 있어서 점프가 한두 칸에 그치기 때문입니다. “패턴에 없는 글자를 만나 통째로 점프”하는 최선의 경우가 거의 안 나옵니다.
정리하면 보이어-무어는 이럴 때 강합니다.
- 알파벳이 클 때: 영어 텍스트(대소문자 + 기호 = 수십 종)에서는 “패턴에 없는 글자”를 자주 만납니다.
- 패턴이 길 때: 위에서 본 그대로입니다.
반대로 약할 때는 이렇습니다.
- 알파벳이 작을 때: DNA, 이진 데이터. 이럴 땐 KMP가 낫습니다.
- 패턴이 짧을 때: 점프 거리 자체가 작습니다.
grep이 빠른 이유가 바로 이것입니다. 실제 grep은 여기에 좋은 접미사(good suffix) 규칙까지 더해 점프를 더 키웁니다. 4.3절 3단계에서 뒤의 4글자 MPLE가 맞았다는 정보를 이 예제는 버리지만, 좋은 접미사 규칙은 “패턴 안에 MPLE가 또 나오는 곳”으로 맞춰 점프합니다. 이 예제는 학습을 위해 나쁜 문자 규칙만 구현했습니다.
5. Z 알고리즘: 만능 나사돌리개
5.1 Z 배열이란
Z[i] = “위치 i부터 시작하는 부분 문자열이, 전체 문자열의 접두사와 앞에서부터 몇 글자 일치하는가”입니다.
s = a a b a a b a a a
Z = 0 1 0 5 1 0 2 2 1
Z[3] = 5를 확인해 봅시다. s[3..]은 aabaaa이고, s의 접두사는 aabaab...입니다. 앞에서부터 a-a-b-a-a 다섯 글자가 같고 여섯 번째에서 갈라집니다(a vs b). 그래서 5입니다. Z[1] = 1은 s[1..] = abaabaaa가 접두사 aab...와 a 한 글자만 같기 때문입니다. Z[0]은 전체 문자열 자신이라 관례상 0(또는 n)으로 둡니다.
정의는 이게 전부입니다. 그런데 이 배열 하나로 검색, 주기 찾기, 접두사-접미사 찾기가 한꺼번에 풀립니다. 그래서 “만능 나사돌리개”입니다.
5.2 예제: z_algorithm.c
examples/z_algorithm.c:
/*
* z_algorithm.c - Z 알고리즘: 접두사 일치 길이의 마법
* 16주차: 문자열 알고리즘
*
* Z 배열: Z[i] = "s[i..]와 s(전체)의 접두사가 일치하는 최대 길이"
*
* s = a a b a a b a a a
* Z = 1 0 5 1 0 2 2 1 (Z[0]은 관례상 0 또는 n)
* Z[3]=5: s[3..]="aabaaa"와 s의 접두사 "aabaa"가 5글자 일치
*
* O(n)에 계산하는 비결: 이미 계산한 "Z-박스"(일치 구간)를 재활용.
* KMP의 실패 함수와 형제 같은 존재인데 더 직관적입니다.
*
* 패턴 검색 응용: "패턴$텍스트"를 이어 붙여 Z를 구하면
* Z[i] == 패턴 길이인 곳이 바로 매치 위치!
*/
#include <stdio.h>
#include <string.h>
/* Z 배열 계산: O(n) */
void z_array(const char *s, int n, int z[]) {
z[0] = 0; /* 관례 */
int l = 0, r = 0; /* 현재 Z-박스 [l, r) */
for (int i = 1; i < n; i++) {
if (i < r) {
/* i가 Z-박스 안: 앞에서 계산한 값을 복사해 출발!
* (s[l..r) == s[0..r-l) 이므로 s[i]는 s[i-l]과 같은 상황) */
z[i] = (r - i < z[i - l]) ? r - i : z[i - l];
} else {
z[i] = 0;
}
/* 박스를 벗어난 부분은 직접 비교로 연장 */
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
/* 더 오른쪽까지 가는 박스면 갱신 */
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
}
/* Z로 패턴 검색: pattern + '\x01' + text 를 이어 붙인다 */
void z_search(const char *text, const char *pattern) {
char joined[1024];
int m = (int)strlen(pattern);
snprintf(joined, sizeof(joined), "%s\x01%s", pattern, text);
int n = (int)strlen(joined);
int z[1024];
z_array(joined, n, z);
for (int i = m + 1; i < n; i++) {
if (z[i] == m) {
printf(" 위치 %d에서 발견\n", i - m - 1);
}
}
}
int main(void) {
printf("=== Z 배열 손으로 확인 ===\n");
const char *s = "aabaabaaa";
int n = (int)strlen(s);
int z[64];
z_array(s, n, z);
printf(" s : ");
for (int i = 0; i < n; i++) printf("%c ", s[i]);
printf("\n Z : ");
for (int i = 0; i < n; i++) printf("%d ", z[i]);
printf("\n");
printf(" 해석: Z[3]=%d -> s[3..]인 \"%s\"가 접두사와 %d글자 일치\n",
z[3], s + 3, z[3]);
printf("\n=== Z로 패턴 검색 (패턴 + 구분자 + 텍스트) ===\n");
const char *text = "abcxabcyabcabc";
printf("텍스트: %s, 패턴: abc\n", text);
z_search(text, "abc");
printf("\n=== 응용 1: 문자열의 주기 찾기 ===\n");
const char *periodic = "abcabcabcabc";
int pn = (int)strlen(periodic);
z_array(periodic, pn, z);
printf("s = %s (길이 %d)\n", periodic, pn);
for (int p = 1; p < pn; p++) {
/* 주기 p 판정: Z[p] == n - p 이면 s는 주기 p로 반복 */
if (pn % p == 0 && z[p] == pn - p) {
printf(" 최소 주기 %d: \"%.*s\"의 %d회 반복!\n",
p, p, periodic, pn / p);
break;
}
}
printf("\n=== 응용 2: 접두사이자 접미사인 것 ===\n");
const char *word = "abcabdabcab";
int wn = (int)strlen(word);
z_array(word, wn, z);
printf("s = %s\n", word);
for (int i = wn - 1; i > 0; i--) {
if (i + z[i] == wn) { /* 끝까지 일치 = 접미사가 접두사 */
printf(" 길이 %d: \"%.*s\" (접두사이면서 접미사!)\n",
z[i], z[i], word);
}
}
printf("\n정리:\n");
printf("1. Z[i] = i에서 시작하는 접두사 일치 길이. O(n) 계산\n");
printf("2. Z-박스 재활용이 비결 (계산한 것을 두 번 계산하지 않는다)\n");
printf("3. 검색/주기/접두사-접미사 등 문자열 문제의 만능 나사돌리개\n");
printf("4. KMP 실패 함수와 상호 변환 가능한 형제 관계\n");
return 0;
}
$ ./build/z_algorithm
=== Z 배열 손으로 확인 ===
s : a a b a a b a a a
Z : 0 1 0 5 1 0 2 2 1
해석: Z[3]=5 -> s[3..]인 "aabaaa"가 접두사와 5글자 일치
=== Z로 패턴 검색 (패턴 + 구분자 + 텍스트) ===
텍스트: abcxabcyabcabc, 패턴: abc
위치 0에서 발견
위치 4에서 발견
위치 8에서 발견
위치 11에서 발견
=== 응용 1: 문자열의 주기 찾기 ===
s = abcabcabcabc (길이 12)
최소 주기 3: "abc"의 4회 반복!
=== 응용 2: 접두사이자 접미사인 것 ===
s = abcabdabcab
길이 2: "ab" (접두사이면서 접미사!)
길이 5: "abcab" (접두사이면서 접미사!)
정리:
1. Z[i] = i에서 시작하는 접두사 일치 길이. O(n) 계산
2. Z-박스 재활용이 비결 (계산한 것을 두 번 계산하지 않는다)
3. 검색/주기/접두사-접미사 등 문자열 문제의 만능 나사돌리개
4. KMP 실패 함수와 상호 변환 가능한 형제 관계
5.3 Z-박스: 계산한 것을 두 번 계산하지 않는다
Z 배열을 정의대로 구하면 위치마다 앞에서부터 비교하니 O(n²)입니다. O(n)으로 줄이는 비결이 Z-박스입니다.
void z_array(const char *s, int n, int z[]) {
z[0] = 0; /* 관례 */
int l = 0, r = 0; /* 현재 Z-박스 [l, r) */
for (int i = 1; i < n; i++) {
if (i < r) {
z[i] = (r - i < z[i - l]) ? r - i : z[i - l];
} else {
z[i] = 0;
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
}
Z-박스 [l, r)는 “지금까지 발견한, 접두사와 일치하는 구간 중 가장 오른쪽까지 뻗은 것”입니다. s[l..r)가 s[0..r-l)과 똑같다는 사실을 이미 알고 있는 상태죠.
새 위치 i가 이 박스 안에 있다면(i < r), s[i]부터의 상황은 s[i-l]부터의 상황과 같습니다. 박스 안에서는 두 부분이 글자 단위로 똑같으니까요. 그래서 이미 계산해 둔 z[i-l]을 그대로 가져와 출발점으로 삼습니다. 다만 박스 밖은 보장이 없으니 박스 경계까지(r - i)로 제한합니다. 그다음 while이 “박스 밖 부분만” 직접 비교해 연장합니다.
말로는 어지러우니 aabaabaaa에서 한 단계씩 찍었습니다.
i s[i] 박스[l,r) i<r? 출발값 직접 비교 후 z[i] 새 박스
1 a [0,0) N 0 (박스 밖) 1 (+1) [1,2)
2 b [1,2) N 0 (박스 밖) 0 (+0) (유지)
3 a [1,2) N 0 (박스 밖) 5 (+5) [3,8)
4 a [3,8) Y min(r-i=4, z[1]=1)=1 1 (+0) (유지)
5 b [3,8) Y min(r-i=3, z[2]=0)=0 0 (+0) (유지)
6 a [3,8) Y min(r-i=2, z[3]=5)=2 2 (+0) (유지)
7 a [3,8) Y min(r-i=1, z[4]=1)=1 2 (+1) [7,9)
8 a [7,9) Y min(r-i=1, z[1]=1)=1 1 (+0) (유지)
Z = 0 1 0 5 1 0 2 2 1
i = 3에서 직접 비교로 5글자를 맞춰 박스[3, 8)이 생겼습니다. 이 구간이 접두사와 같다는 것을 이제 압니다.i = 4, 5, 6은 전부 박스 안입니다.z[1], z[2], z[3]을 복사해 출발했고, 직접 비교가 한 번도 필요 없었습니다(+0). 세 위치를 비교 0번으로 처리한 것입니다.i = 6:z[3] = 5를 가져오지만 박스 경계까지 2칸밖에 안 남았으니min(2, 5) = 2로 제한합니다. 그 뒤while이s[2]와s[8](bvsa)을 비교해 더 못 늘리고 끝납니다.i = 7: 출발값 1에서 직접 비교로 1을 더해 2가 되고,7 + 2 = 9 > 8이라 박스가[7, 9)로 갱신됩니다.
전체가 O(n)인 이유가 여기 있습니다. while이 한 번 돌 때마다(+1이 날 때마다) r이 오른쪽으로 한 칸 이상 밀리고, r은 n을 넘지 못합니다. 그러니 직접 비교의 총량이 n을 넘지 못합니다. 표에서 + 뒤의 숫자를 다 더하면 8이고, n = 9입니다. 10주차 동적 배열에서 본 분할 상환 분석의 또 다른 사례입니다.
5.4 Z의 세 가지 응용
응용 1 — 패턴 검색. 패턴 + 구분자 + 텍스트를 이어 붙이고 Z 배열을 구합니다.
snprintf(joined, sizeof(joined), "%s\x01%s", pattern, text);
...
for (int i = m + 1; i < n; i++) {
if (z[i] == m) {
printf(" 위치 %d에서 발견\n", i - m - 1);
}
}
합친 문자열의 접두사가 곧 패턴이므로, Z[i]가 패턴 길이와 같다는 것은 그 위치에서 패턴이 통째로 일치한다는 뜻입니다. 실제 값을 찍어 보면 이렇습니다(#이 구분자 \x01 자리).
i : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
s : a b c # a b c x a b c y a b c a b c
Z : 0 0 0 0 3 0 0 0 3 0 0 0 3 0 0 3 0 0
Z[i]==3 인 i: 4(텍스트 위치 0) 8(텍스트 위치 4) 12(텍스트 위치 8) 15(텍스트 위치 11)
Z[i] == 3인 곳이 정확히 네 군데이고, i - m - 1을 하면 텍스트 위치가 나옵니다. 검색 알고리즘이 배열 계산 하나로 환원됐습니다.
구분자 \x01이 왜 필요한지도 실험했습니다. 패턴 abc를 텍스트 abcabc에서 찾는데, 구분자를 넣은 것과 뺀 것의 텍스트 구간 Z값을 비교하면 이렇습니다.
구분자 있음: Z(텍스트 구간) = 3 0 0 3 0 0 -> ==m 인 위치: 0 3
구분자 없음: Z(텍스트 구간) = 6 0 0 3 0 0 -> ==m 인 위치: 3
구분자가 없으면 텍스트 위치 0의 일치가 패턴 끝을 지나 텍스트로 이어져 Z = 6이 되고, == m 검사가 위치 0의 진짜 매치를 놓칩니다. 구분자가 있으면 일치는 구분자에서 반드시 끊기므로 Z값이 m을 넘을 수 없고, “Z == m이면 매치”가 정확히 성립합니다. 구분자는 패턴에도 텍스트에도 절대 나오지 않는 글자여야 하고, 그래서 화면에 찍히지 않는 제어 문자 \x01을 골랐습니다.
응용 2 — 주기 찾기.
if (pn % p == 0 && z[p] == pn - p) {
/* s는 주기 p로 반복된다 */
}
abcabcabcabc에서 Z[3] = 9입니다. 위치 3부터가 접두사와 9글자 일치한다는 뜻이고, 문자열 길이가 12이니 끝까지 일치합니다. “3칸 밀어도 자기 자신과 똑같다”는 것이 곧 “주기가 3″입니다. p를 1부터 올리며 처음 조건을 만족하는 값이 최소 주기입니다.
응용 3 — 접두사이자 접미사.
if (i + z[i] == wn) { /* 끝까지 일치 = 접미사가 접두사 */
i + z[i]가 문자열 끝과 같다는 것은 “위치 i부터 끝까지가 접두사와 일치”한다는 뜻이고, 그것이 바로 접두사이자 접미사입니다. KMP의 실패 함수가 하던 바로 그 일입니다. abcabdabcab의 답 ab(2)와 abcab(5)를 KMP의 fail[10]으로 구해도 5가 나옵니다. Z 배열과 실패 함수는 서로 변환할 수 있는 형제 관계입니다.
6. 검색 알고리즘 총정리와 실전 대결
네 알고리즘을 한 표에 놓고 보겠습니다. σ는 알파벳 크기입니다.
| 알고리즘 | 전처리 | 검색 (평균) | 최악 | 필살기 | 약점 |
|---|---|---|---|---|---|
| 브루트포스 | 없음 | O(n) | O(nm) | 구현이 5줄 | 최악 보장 없음 |
| KMP | O(m) | O(n) | O(n) | 후진 없음(스트림), 최악 보장 | 실전 텍스트에서 이득 적음 |
| 라빈-카프 | O(m) | O(n) | O(nm) | 멀티 패턴, 문서 지문 | 충돌 시 느려짐 |
| 보이어-무어 | O(m+σ) | O(n/m) | O(nm) | 긴 패턴 + 큰 알파벳 | 작은 알파벳에 약함 |
| Z | O(n+m) | O(n) | O(n) | 주기·구조 분석 겸용 | 텍스트 전체를 메모리에 |
표만 보면 끝이 아닙니다. 실제로 경주를 시켜 봤습니다. 영어 문장을 반복해 1,000만 글자짜리 텍스트를 만들고, 네 알고리즘과 C 표준 라이브러리의 strstr로 같은 패턴을 찾았습니다. -O2로 컴파일했습니다.
텍스트 1000만 자 (영어 문장 반복)
패턴 "lazy dog. the quick" (길이 19)
브루트포스 19.3 ms (222222개)
KMP 18.1 ms (222222개)
보이어-무어 7.5 ms (222222개)
strstr(glibc) 5.2 ms (222222개)
패턴 "zebras and pythons" (길이 18)
브루트포스 16.6 ms (0개)
KMP 21.9 ms (0개)
보이어-무어 3.7 ms (0개)
strstr(glibc) 1.3 ms (0개)
세 가지가 보입니다.
- 일상 텍스트에서 KMP는 브루트포스와 같거나 오히려 느립니다. 2.7절에서 예고한 그대로입니다. 불일치가 첫 글자에서 나는 텍스트에서는 실패 함수를 참고하는 비용이 오히려 짐입니다. KMP의 가치는 평균이 아니라 최악 보장에 있습니다.
- 보이어-무어는 2.5~4.5배 빠릅니다. 없는 패턴을 찾을 때 더 빠른 것도 이유가 있습니다. 매치가 없으면 점프만 계속하니까요.
strstr가 가장 빠릅니다. glibc의strstr는 짧은 패턴에는 CPU의 SIMD 명령을, 긴 패턴에는 “Two-Way” 알고리즘을 씁니다. 수십 년간 다듬어진 구현입니다. 그러니 실무에서 문자열 검색이 필요하면 먼저strstr를 쓰세요. 이번 주에 직접 구현하는 것은 원리를 알기 위해서이고, 직접 구현이 정당화되는 경우는 스트림 처리(KMP), 멀티 패턴(라빈-카프), 특수한 성능 요구처럼 표준 함수가 못 하는 일이 있을 때입니다.
실전 선택 기준을 정리하면 이렇습니다.
- 일반 텍스트에서 한 패턴 찾기 → 보이어-무어 (
grep의 선택), 또는 그냥strstr - 패턴 여러 개를 동시에 → 라빈-카프 (또는 아호-코라식, 13주차 트라이의 확장판)
- 스트림·실시간 처리, 최악 보장 필요 → KMP
- 같은 텍스트에 검색을 반복 → 다음 절의 접미사 배열
- 문자열의 구조 자체가 궁금 → Z 알고리즘
7. 접미사 배열: 문자열의 색인
7.1 같은 텍스트를 반복 검색한다면
지금까지의 알고리즘은 전부 패턴을 전처리했습니다. 텍스트는 매번 처음부터 훑었죠. 그런데 상황이 반대라면 어떨까요? 텍스트는 고정인데 패턴이 계속 바뀐다면?
책 한 권에서 단어를 수천 번 검색한다고 생각해 보세요. 매번 책 전체를 훑는 것보다, 한 번 색인(책 뒤의 찾아보기)을 만들어 두고 재사용하는 편이 낫습니다. 13주차의 역색인이 그런 발상이었습니다. 다만 역색인은 “단어” 단위라서 단어 중간의 조각(ana)은 못 찾습니다.
접미사 배열(suffix array)은 문자열의 범용 색인입니다. 정의는 이렇습니다.
모든 접미사를 사전순으로 정렬한 뒤, 각 접미사의 시작 위치를 순서대로 적은 배열.
접미사(suffix)는 “어떤 위치부터 끝까지”입니다. banana의 접미사는 여섯 개입니다.
banana의 접미사들: 사전순으로 정렬하면:
0: banana 5: a
1: anana 3: ana
2: nana 1: anana
3: ana -> 0: banana
4: na 4: nana
5: a 2: na
접미사 배열 = [5, 3, 1, 0, 4, 2]
왜 이게 색인이 될까요? 패턴 P로 시작하는 접미사의 시작 위치가 곧 P의 등장 위치이기 때문입니다. ana로 시작하는 접미사는 ana(위치 3)와 anana(위치 1)이고, 실제로 banana에서 ana는 위치 1과 3에 있습니다. 그리고 접미사들이 사전순으로 정렬되어 있으니, P로 시작하는 것들은 연속된 구간(순위 1~2)에 모여 있습니다. 그 구간을 15주차의 이진 탐색으로 찾으면 끝입니다.
7.2 예제: suffix_array.c
examples/suffix_array.c:
/*
* suffix_array.c - 접미사 배열과 LCP
* 16주차: 문자열 알고리즘
*
* 접미사 배열 = "모든 접미사를 사전순으로 정렬한 시작 인덱스 배열"
*
* banana의 접미사들: 정렬하면:
* 0: banana 5: a
* 1: anana 3: ana
* 2: nana 1: anana
* 3: ana -> 0: banana
* 4: na 4: nana
* 5: a 2: na
* 접미사 배열 = [5, 3, 1, 0, 4, 2]
*
* 이걸로 뭘 하나?
* - 패턴 검색이 이진 탐색으로! O(m log n) (어떤 패턴이든!)
* - LCP(이웃 접미사의 공통 접두사)로 "가장 긴 반복 부분 문자열"
*
* 학습용 O(n^2 log n) 구축 (실전은 O(n log n) 접미사 배열 알고리즘)
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static const char *g_text; /* qsort 비교용 전역 */
int suffix_cmp(const void *a, const void *b) {
int i = *(const int *)a, j = *(const int *)b;
return strcmp(g_text + i, g_text + j);
}
/* 접미사 배열 구축 (단순 정렬 방식) */
void build_suffix_array(const char *text, int n, int sa[]) {
for (int i = 0; i < n; i++) sa[i] = i;
g_text = text;
qsort(sa, n, sizeof(int), suffix_cmp);
}
/* LCP 배열: lcp[i] = sa[i-1] 접미사와 sa[i] 접미사의 공통 접두사 길이 */
void build_lcp(const char *text, int n, const int sa[], int lcp[]) {
lcp[0] = 0;
for (int i = 1; i < n; i++) {
const char *a = text + sa[i - 1];
const char *b = text + sa[i];
int len = 0;
while (a[len] && b[len] && a[len] == b[len]) len++;
lcp[i] = len;
}
}
/* 접미사 배열로 패턴 검색: 이진 탐색! */
int sa_search(const char *text, int n, const int sa[], const char *pattern) {
int m = (int)strlen(pattern);
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int cmp = strncmp(pattern, text + sa[mid], m);
if (cmp == 0) return sa[mid]; /* 발견! */
if (cmp < 0) high = mid - 1;
else low = mid + 1;
}
return -1;
}
int main(void) {
const char *text = "banana";
int n = (int)strlen(text);
int sa[64], lcp[64];
printf("=== \"%s\"의 접미사 배열 ===\n", text);
build_suffix_array(text, n, sa);
build_lcp(text, n, sa, lcp);
printf(" 순위 시작 LCP 접미사\n");
for (int i = 0; i < n; i++) {
printf(" %d %d %d %s\n", i, sa[i], lcp[i], text + sa[i]);
}
printf("\n=== 패턴 검색 = 정렬된 접미사에 이진 탐색 ===\n");
const char *queries[] = {"ana", "nan", "ban", "xyz"};
for (int q = 0; q < 4; q++) {
int pos = sa_search(text, n, sa, queries[q]);
if (pos >= 0) printf(" \"%s\": 위치 %d에서 발견\n", queries[q], pos);
else printf(" \"%s\": 없음\n", queries[q]);
}
printf(" (15주차 이진 탐색이 문자열 세계에서 재활용!)\n");
printf("\n=== LCP의 보물: 가장 긴 반복 부분 문자열 ===\n");
/* LCP 최댓값 = 두 번 이상 나오는 가장 긴 부분 문자열 */
int best = 0;
for (int i = 1; i < n; i++) {
if (lcp[i] > lcp[best]) best = i;
}
printf(" LCP 최대 = %d (\"%.*s\")\n",
lcp[best], lcp[best], text + sa[best]);
printf(" -> \"%s\"에서 두 번 이상 나오는 가장 긴 조각 = \"%.*s\"!\n",
text, lcp[best], text + sa[best]);
/* 좀 더 재미있는 예 */
const char *text2 = "abcdabcdabcde";
int n2 = (int)strlen(text2);
int sa2[64], lcp2[64];
build_suffix_array(text2, n2, sa2);
build_lcp(text2, n2, sa2, lcp2);
int best2 = 0;
for (int i = 1; i < n2; i++) {
if (lcp2[i] > lcp2[best2]) best2 = i;
}
printf("\n \"%s\"의 최장 반복 조각: \"%.*s\" (길이 %d)\n",
text2, lcp2[best2], text2 + sa2[best2], lcp2[best2]);
printf(" (표절 검사, 데이터 압축, DNA 반복 서열 분석의 원리)\n");
printf("\n더 가면 (심화 예고만):\n");
printf("- 접미사 트리: 접미사 배열의 트리 버전, O(m) 검색\n");
printf("- BWT(버로우즈-휠러 변환): 접미사 배열로 만드는 압축 전처리\n");
printf(" (bzip2와 DNA 검색 도구 BWA의 핵심!)\n");
return 0;
}
$ ./build/suffix_array
=== "banana"의 접미사 배열 ===
순위 시작 LCP 접미사
0 5 0 a
1 3 1 ana
2 1 3 anana
3 0 0 banana
4 4 0 na
5 2 2 nana
=== 패턴 검색 = 정렬된 접미사에 이진 탐색 ===
"ana": 위치 1에서 발견
"nan": 위치 2에서 발견
"ban": 위치 0에서 발견
"xyz": 없음
(15주차 이진 탐색이 문자열 세계에서 재활용!)
=== LCP의 보물: 가장 긴 반복 부분 문자열 ===
LCP 최대 = 3 ("ana")
-> "banana"에서 두 번 이상 나오는 가장 긴 조각 = "ana"!
"abcdabcdabcde"의 최장 반복 조각: "abcdabcd" (길이 8)
(표절 검사, 데이터 압축, DNA 반복 서열 분석의 원리)
더 가면 (심화 예고만):
- 접미사 트리: 접미사 배열의 트리 버전, O(m) 검색
- BWT(버로우즈-휠러 변환): 접미사 배열로 만드는 압축 전처리
(bzip2와 DNA 검색 도구 BWA의 핵심!)
7.3 구축: qsort로 정렬하기
static const char *g_text; /* qsort 비교용 전역 */
int suffix_cmp(const void *a, const void *b) {
int i = *(const int *)a, j = *(const int *)b;
return strcmp(g_text + i, g_text + j);
}
void build_suffix_array(const char *text, int n, int sa[]) {
for (int i = 0; i < n; i++) sa[i] = i;
g_text = text;
qsort(sa, n, sizeof(int), suffix_cmp);
}
접미사를 따로 복사하지 않는다는 점을 보세요. 접미사 i는 그냥 text + i, 즉 원본 문자열 안의 주소입니다(6주차 포인터 산술). 배열 sa에는 시작 위치만 넣고, 15주차의 qsort로 정렬하되 비교 함수가 text + i와 text + j를 strcmp합니다. 메모리는 정수 n개뿐입니다.
qsort의 비교 함수는 인자를 두 개만 받으므로, 텍스트 포인터를 넘길 자리가 없습니다. 그래서 전역 변수 g_text를 씁니다. 5주차에서 전역 변수는 피하라고 했지만, 이런 경우는 흔히 쓰는 예외입니다. (GNU 확장 qsort_r은 추가 인자를 받아 이 문제를 해결합니다.)
이 방식의 시간 복잡도는 얼마일까요? qsort가 O(n log n)번 비교하는데, 비교 한 번이 strcmp라 최악 O(n)입니다. 그러니 전체 O(n² log n)입니다. 실제로 얼마나 느려지는지 재 봤습니다. 왼쪽은 무작위 영문, 오른쪽은 abcabcabc...처럼 반복이 심한 텍스트입니다.
n(글자) strcmp 호출 시간(ms) [반복 텍스트 'abcabc...' 는?] 시간(ms)
1000 16544 0.1 0.1
2000 36736 0.3 0.2
4000 80769 0.5 0.7
8000 176194 1.1 2.4
16000 381675 2.4 9.2
무작위 텍스트에서는 strcmp가 첫 글자 근처에서 끝나 n log n에 가깝게 늘어납니다. 그런데 반복 텍스트에서는 n이 2배 될 때 시간이 4배씩 늘어납니다. 접미사들이 앞부분이 전부 같아서 strcmp가 끝까지 비교하기 때문입니다. 텍스트가 100만 글자면 이 방식으로는 못 씁니다. 실전에서는 O(n log n) 또는 O(n)에 만드는 알고리즘(접두사 배가법, SA-IS)을 씁니다. 원리는 “길이 1인 접두사로 먼저 정렬하고, 그 결과를 이용해 길이 2, 4, 8, …로 배가하며 정렬”하는 것입니다. 이번 주의 목표는 접미사 배열이 무엇이고 왜 강력한가를 이해하는 것이므로 단순한 구현을 골랐습니다.
7.4 이진 탐색으로 검색하기
int sa_search(const char *text, int n, const int sa[], const char *pattern) {
int m = (int)strlen(pattern);
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int cmp = strncmp(pattern, text + sa[mid], m);
if (cmp == 0) return sa[mid]; /* 발견! */
if (cmp < 0) high = mid - 1;
else low = mid + 1;
}
return -1;
}
15주차의 이진 탐색이 그대로 들어왔습니다. 다른 점은 비교 대상이 정수가 아니라 문자열이고, 그것도 strncmp(..., m)으로 앞 m글자만 비교한다는 것뿐입니다. 접미사가 패턴으로 시작하는지만 보면 되니까요. mid 계산도 15주차에서 배운 넘침 없는 공식입니다.
시간 복잡도는 O(m log n)입니다. 이진 탐색이 log n번 돌고, 각 비교가 최대 m글자를 봅니다. 텍스트가 100만 글자여도 20번의 비교면 끝납니다. 색인을 한 번 만들어 두면 어떤 패턴이든 즉시 찾는 것이죠.
다만 이 구현은 “아무 위치 하나”만 돌려줍니다. ana를 찾으면 순위 1과 2 중 이진 탐색이 먼저 만난 쪽을 돌려주죠. 모든 등장 위치를 찾으려면 15주차의 lower_bound / upper_bound로 구간의 양 끝을 찾으면 됩니다. 실제로 그렇게 바꿔 돌리면 이렇게 나옵니다.
"ana" 는 순위 1..2 (총 2개): 위치 3 위치 1
순위 1은 ana(위치 3), 순위 2는 anana(위치 1)입니다. 이것이 연습 문제 4번입니다.
7.5 LCP 배열의 보물
LCP(Longest Common Prefix) 배열은 정렬된 접미사 배열에서 이웃한 두 접미사의 공통 접두사 길이입니다.
void build_lcp(const char *text, int n, const int sa[], int lcp[]) {
lcp[0] = 0;
for (int i = 1; i < n; i++) {
const char *a = text + sa[i - 1];
const char *b = text + sa[i];
int len = 0;
while (a[len] && b[len] && a[len] == b[len]) len++;
lcp[i] = len;
}
}
banana의 표를 다시 보세요. 순위 1 ana와 순위 2 anana는 앞 3글자 ana가 같으니 lcp[2] = 3입니다. 순위 4 na와 순위 5 nana는 na 2글자가 같아 lcp[5] = 2입니다. while 조건의 a[len] && b[len]은 4주차에서 배운 대로 \0(문자열 끝)에 닿으면 멈추라는 뜻입니다.
그리고 여기에 보물 같은 성질이 있습니다.
LCP 배열의 최댓값 = 두 번 이상 나타나는 가장 긴 부분 문자열의 길이
왜 그럴까요? 어떤 조각이 두 번 나타난다면, 그 두 위치에서 시작하는 접미사가 둘 다 그 조각으로 시작합니다. 접미사들이 사전순이니 같은 조각으로 시작하는 접미사들은 서로 붙어 있고, 결국 이웃한 두 접미사의 공통 접두사로 나타납니다. banana에서 LCP 최댓값 3이 ana이고, 실제로 b-ana-na와 ban-ana에서 두 번 나타납니다(겹치기까지 합니다). 두 번째 예 abcdabcdabcde에서는 abcdabcd(8글자)가 위치 0과 4에서 겹쳐 나타납니다.
이 한 줄짜리 결과가 실무에서 이렇게 쓰입니다.
- 표절 검사: 두 문서를 이어 붙이고 최장 공통 부분 문자열을 찾습니다(연습 문제 6번).
- 데이터 압축: 반복되는 긴 조각을 찾아 “앞에 나온 것을 참조”로 바꿉니다. ZIP의 LZ 계열 압축이 이 원리입니다.
- DNA 분석: 반복 서열 탐지는 유전체학의 기본 작업입니다.
- 중복 코드 탐지: 소스 코드에서 복사-붙여넣기된 블록 찾기.
더 가면: 접미사 배열의 트리 버전이 접미사 트리(13주차 트라이의 확장)이고, 접미사 배열로 만드는 압축 전처리가 BWT(버로우즈-휠러 변환)입니다. bzip2와 DNA 정렬 도구 BWA의 핵심입니다. 관심 있으면 찾아보세요.
8. RLE: 가장 단순한 압축과 첫 교훈
8.1 연속을 세어 줄이기
이제 주제를 압축으로 옮깁니다. 압축이 왜 문자열 알고리즘일까요? 압축은 결국 데이터 속의 패턴을 더 짧은 표현으로 바꾸는 일이고, 패턴을 찾는 것이 이번 주 내내 한 일이기 때문입니다.
가장 단순한 압축이 RLE(Run-Length Encoding, 연속 길이 부호화)입니다. AAAABBB → 4A3B. 연속된 같은 글자(run)를 “개수 + 글자”로 바꿉니다. 팩스가 흑백 이미지를 보낼 때 “흰 점 300개, 검은 점 5개, 흰 점 295개”라고 보내는 것이 이 방식입니다.
8.2 예제: rle_compress.c
examples/rle_compress.c:
/*
* rle_compress.c - RLE(Run-Length Encoding): 가장 단순한 압축
* 16주차: 문자열 알고리즘
*
* "AAAABBBCC" -> "4A3B2C" : 연속(run)을 개수+문자로 바꾼다.
*
* 압축의 첫 번째 교훈을 주는 알고리즘입니다:
* 압축은 "패턴이 있을 때만" 된다.
* 반복이 없는 데이터에 RLE를 쓰면 오히려 커진다!
*
* 안전한 이진 RLE 형식: [개수(1바이트)][문자] 쌍의 나열
* (문자에 숫자가 나와도 안전하도록)
*/
#include <stdio.h>
#include <string.h>
/* RLE 압축: out에 [개수][문자] 쌍. 반환 = 출력 길이 */
int rle_compress(const unsigned char *in, int n, unsigned char *out) {
int k = 0;
int i = 0;
while (i < n) {
unsigned char c = in[i];
int run = 1;
while (i + run < n && in[i + run] == c && run < 255) {
run++; /* 최대 255 (1바이트 한계) */
}
out[k++] = (unsigned char)run;
out[k++] = c;
i += run;
}
return k;
}
/* RLE 해제 */
int rle_decompress(const unsigned char *in, int n, unsigned char *out) {
int k = 0;
for (int i = 0; i + 1 < n; i += 2) {
int run = in[i];
unsigned char c = in[i + 1];
for (int r = 0; r < run; r++) out[k++] = c;
}
return k;
}
void show_case(const char *label, const unsigned char *data, int n) {
unsigned char packed[1024], restored[1024];
int packed_len = rle_compress(data, n, packed);
int restored_len = rle_decompress(packed, packed_len, restored);
int ok = (restored_len == n && memcmp(data, restored, n) == 0);
double ratio = 100.0 * packed_len / n;
printf("%s\n", label);
printf(" 원본 (%3d바이트): %.40s%s\n", n, (const char *)data,
n > 40 ? "..." : "");
printf(" 압축 (%3d바이트): ", packed_len);
for (int i = 0; i + 1 < packed_len && i < 20; i += 2) {
printf("%d%c ", packed[i], packed[i + 1]);
}
if (packed_len > 20) printf("...");
printf("\n 압축률: %.0f%% %s | 복원 검증: %s\n\n",
ratio,
ratio < 100 ? "(줄었다!)" : "(오히려 늘었다!!)",
ok ? "OK" : "실패!");
}
int main(void) {
printf("=== RLE: 연속을 세어 줄이기 ===\n\n");
/* 1. RLE의 홈그라운드: 반복 많은 데이터 */
unsigned char good[] = "AAAAAAAAAABBBBBBCCCCCCCCCCCCDDDDDD";
show_case("[반복 많음 - 단색 이미지/여백 같은 데이터]",
good, (int)strlen((char *)good));
/* 2. RLE의 지옥: 반복 없는 데이터 */
unsigned char bad[] = "abcdefghijklmnopqrstuvwxyz";
show_case("[반복 없음 - 일반 텍스트]",
bad, (int)strlen((char *)bad));
/* 3. 극단적으로 유리한 경우 */
unsigned char extreme[300];
memset(extreme, 'X', 255);
extreme[255] = '\0';
show_case("[한 문자 255개]", extreme, 255);
printf("=== 교훈 ===\n");
printf("1. 압축 = 데이터의 '중복/패턴'을 짧은 표현으로 바꾸는 것\n");
printf("2. 패턴이 없으면 압축 불가 (오히려 헤더만큼 커진다)\n");
printf(" -> '모든 데이터를 줄이는 압축'은 수학적으로 불가능!\n");
printf("3. RLE 실사용처: 팩스, BMP/TIFF 이미지, 스프라이트\n");
printf("4. 일반 텍스트의 중복은 '반복 문자'가 아니라 '반복 단어'\n");
printf(" -> 그래서 사전 압축(LZ)과 빈도 압축(허프만)이 필요 (다음 예제!)\n");
return 0;
}
$ ./build/rle_compress
=== RLE: 연속을 세어 줄이기 ===
[반복 많음 - 단색 이미지/여백 같은 데이터]
원본 ( 34바이트): AAAAAAAAAABBBBBBCCCCCCCCCCCCDDDDDD
압축 ( 8바이트): 10A 6B 12C 6D
압축률: 24% (줄었다!) | 복원 검증: OK
[반복 없음 - 일반 텍스트]
원본 ( 26바이트): abcdefghijklmnopqrstuvwxyz
압축 ( 52바이트): 1a 1b 1c 1d 1e 1f 1g 1h 1i 1j ...
압축률: 200% (오히려 늘었다!!) | 복원 검증: OK
[한 문자 255개]
원본 (255바이트): XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
압축 ( 2바이트): 255X
압축률: 1% (줄었다!) | 복원 검증: OK
rle_compress의 구조는 단순합니다. in[i]부터 같은 글자가 몇 개 이어지는지 run으로 센 뒤, out에 [run][글자] 두 바이트를 쓰고 i를 run만큼 건너뜁니다. 반환값은 출력 길이입니다. rle_decompress는 반대로 두 바이트씩 읽어 글자를 run번 씁니다. show_case는 압축 → 해제 → memcmp로 원본과 비교하는 라운드트립 검증까지 합니다. 압축기에서 “얼마나 줄었나”보다 먼저 물어야 할 것은 “정확히 복원되는가”입니다.
unsigned char를 쓰는 이유도 짚고 갑시다. 개수를 바이트 하나에 담는데, char는 부호 때문에 128 이상이 음수로 읽힙니다(2주차). 255를 담으려면 unsigned char여야 합니다.
8.3 압축의 첫 교훈
세 결과의 대비가 이 예제의 전부입니다. 압축률이 24%, 200%, 1%입니다.
가운데를 보세요. abcdefg...처럼 반복이 없는 데이터에 RLE를 쓰면 크기가 두 배가 됩니다. 모든 글자가 1a, 1b처럼 2바이트로 늘어나니까요. 여기서 첫 교훈이 나옵니다.
압축은 패턴이 있을 때만 됩니다.
그리고 더 강한 명제도 성립합니다. “모든 데이터를 줄여 주는 압축 알고리즘”은 수학적으로 존재할 수 없습니다. 증명은 13주차에서 본 비둘기집 원리입니다. n비트 데이터는 2ⁿ가지인데, 이것을 전부 n−1비트 이하로 압축하면 결과는 2ⁿ − 1가지뿐입니다(길이 0부터 n−1까지의 비트열을 다 합친 수). 서로 다른 두 입력이 같은 출력으로 가게 되고, 그러면 복원이 불가능합니다. 어떤 압축 알고리즘이든 줄어드는 입력이 있으면 반드시 늘어나는 입력도 있습니다.
그러니 압축 알고리즘은 전부 “어떤 종류의 데이터를 줄이고, 어떤 종류를 늘릴 것인가”를 선택한 결과입니다. RLE는 “연속이 많은 데이터”에 걸었고, 다음 절 허프만은 “빈도가 치우친 데이터”에 걸었습니다.
8.4 실험: 한계 255를 넘기면?
while (i + run < n && in[i + run] == c && run < 255) {
run++; /* 최대 255 (1바이트 한계) */
}
run < 255 조건이 왜 있는지 실험해 봅시다. X를 256개 넣고, 이 조건이 있는 버전과 없는 버전을 비교했습니다.
X 256개, 한계 있음: 4바이트 -> 255X 1X
X 256개, 한계 없음: 2바이트 -> 0X (256 이 1바이트에 담기며 0 으로!)
한계가 없으면 run = 256이 되고, 이것을 1바이트에 넣는 순간 0으로 잘립니다(256 = 1 0000 0000, 아래 8비트만 남으면 0). 압축 결과는 “X 0개”가 되어 복원하면 빈 파일이 나옵니다. 오류 메시지 하나 없이 데이터가 조용히 사라지는 버그입니다. 형식에 한계가 있으면 코드에 반드시 그 한계를 적어야 합니다.
주석의 “안전한 이진 RLE 형식”이라는 말도 짚어 봅시다. "4A3B"처럼 글자로 쓰면 원본에 숫자가 들어 있을 때 구분이 안 됩니다. "4A4"는 “A 4개 다음 4″일까요, “A 4개 다음 4 하나”일까요? 항상 [개수][글자] 2바이트 쌍으로 고정하면 그런 모호함이 사라집니다. 파일 형식을 설계할 때 항상 물어야 할 질문입니다. “이 형식으로 표현할 수 없는 데이터가 있는가?”
RLE의 실사용처는 분명합니다. 팩스, BMP/TIFF 이미지, 게임 스프라이트(투명 영역이 넓음). 일반 텍스트에는 맞지 않는데, 텍스트의 중복은 “같은 글자의 연속”이 아니라 “자주 나오는 글자”와 “반복되는 단어”이기 때문입니다. 그 문제는 다른 방식이 필요합니다.
9. 허프만 코딩: 자주 나오면 짧게
9.1 고정 길이의 낭비
ASCII는 모든 글자가 8비트입니다. 그런데 영어 텍스트에서 e는 z보다 100배쯤 자주 나옵니다. 둘에게 같은 비용을 치르는 것은 공평해 보이지만, 전체 크기 관점에서는 낭비입니다. 모스 부호가 가장 흔한 E에 가장 짧은 ·을 준 것과 같은 발상으로, 자주 나오는 글자에 짧은 코드를, 드문 글자에 긴 코드를 주면 어떨까요?
문제가 하나 있습니다. 코드 길이가 제각각이면 어디서 끊어 읽어야 할지 어떻게 알까요? a = 0, b = 01, c = 1이라고 정했다고 합시다.
코드 a=0, b=01, c=1 로 "01" 을 해독하면?
0 다음 1 -> 'a' 'c'
01 -> 'b'
두 가지로 읽힌다: 0 이 01 의 접두사이기 때문
a의 코드 0이 b의 코드 01의 앞부분(접두사)이라서 생기는 문제입니다. 해법은 어떤 코드도 다른 코드의 접두사가 되지 않게 만드는 것입니다. 이것을 접두사 코드(prefix code)라고 합니다.
허프만 코드 a=0, b=10, c=11 로 "0101011" 을 해독:
0|10|10|11 -> a b b c (다른 읽기 불가능)
0을 읽으면 그 자리에서 a로 확정됩니다. 0으로 시작하는 다른 코드가 없으니까요. 1을 읽으면 아직 모르니 한 비트 더 읽고, 10이면 b, 11이면 c. 구분자 없이 이어 붙여도 읽는 방법이 하나뿐입니다.
허프만의 천재적인 부분은 이 접두사 코드를 트리로 자연스럽게 만든다는 것입니다. 모든 글자를 트리의 잎에 놓고, 뿌리에서 잎까지 가는 길(왼쪽 = 0, 오른쪽 = 1)을 코드로 삼으면, 어떤 글자의 길도 다른 글자의 길의 앞부분이 될 수 없습니다. 잎에서 길이 끝나니까요.
그리고 자주 나오는 글자를 뿌리 가까이(짧은 길)에, 드문 글자를 깊은 곳(긴 길)에 놓으려면 이렇게 합니다.
- 글자별 빈도를 센다.
- 각 글자를 노드로 만들어 최소 힙(12주차)에 넣는다.
- 가장 드문 둘을 꺼내 묶어 새 노드로 만든다(빈도 = 둘의 합). 다시 힙에 넣는다.
- 하나 남을 때까지 반복한다. 마지막 남은 것이 뿌리다.
드문 것부터 묶는 것이 핵심입니다. 먼저 묶일수록 트리의 깊은 곳에 있게 되고, 깊을수록 코드가 길어지니까요.
9.2 손으로 만들어 보기
작은 예로 트리를 직접 만들어 봅시다. 텍스트는 aaaabbbccd, 빈도는 a=4 b=3 c=2 d=1입니다.
| 단계 | 힙에 있는 것 (빈도) | 꺼낸 둘 | 묶은 결과 |
|---|---|---|---|
| 시작 | a(4) b(3) c(2) d(1) | ||
| 1 | a(4) b(3) dc | d(1), c(2) | 빈도 3짜리 묶음 |
| 2 | a(4) b,dc | b(3), dc | 빈도 6짜리 묶음 |
| 3 | a,[b,dc] | a(4), b,dc | 뿌리 |
2단계에서 b(3)과 [dc](3)은 빈도가 같은데 어느 쪽을 먼저 꺼내든 트리 모양은 같습니다. 완성된 트리를 프로그램으로 찍으면 이렇습니다.
원문 "aaaabbbccd"
빈도: a=4 b=3 c=2 d=1
트리:
루트 노드 (빈도 10)
0: 잎 'a' (빈도 4)
1: 노드 (빈도 6)
0: 잎 'b' (빈도 3)
1: 노드 (빈도 3)
0: 잎 'd' (빈도 1)
1: 잎 'c' (빈도 2)
코드표: a=0 b=10 c=111 d=110
총 19비트 (고정 8비트면 80비트)
가장 흔한 a는 뿌리 바로 아래라 1비트, 가장 드문 d는 세 단계 아래라 3비트입니다. 전체는 4×1 + 3×2 + 2×3 + 1×3 = 19비트. 글자 4종이니 고정 길이로 해도 2비트씩 20비트인데, 그보다도 줄었습니다. 글자마다 8비트를 쓰는 ASCII(80비트)에 비하면 4분의 1입니다.
9.3 예제: huffman.c
examples/huffman.c:
/*
* huffman.c - 허프만 코딩: 자주 나오면 짧게
* 16주차: 문자열 알고리즘
*
* ASCII는 모든 문자가 8비트로 같은 길이입니다. 그런데 'e'는
* 'z'보다 백 배쯤 자주 나옵니다. 자주 나오는 문자에 짧은 코드를,
* 드문 문자에 긴 코드를 주면? 전체가 줄어듭니다!
*
* 허프만 알고리즘 (12주차 트리 + 힙의 재등장!):
* 1. 문자별 빈도를 센다
* 2. 빈도를 우선순위 큐(최소 힙)에 넣는다
* 3. 가장 드문 둘을 꺼내 묶어 새 노드로 (빈도 = 합) 다시 넣는다
* 4. 하나 남을 때까지 반복 -> 허프만 트리 완성
* 5. 왼쪽=0, 오른쪽=1로 경로가 곧 코드
*
* 천재적인 성질: 어떤 코드도 다른 코드의 접두사가 아니다
* (문자는 전부 잎에 있으니까!) -> 구분자 없이 이어 붙여도 해독 가능
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SYMBOLS 128
typedef struct HNode {
unsigned char symbol;
long freq;
struct HNode *left, *right;
} HNode;
/* ---------- HNode* 최소 힙 (12주차 패턴) ---------- */
typedef struct {
HNode *data[MAX_SYMBOLS * 2];
int size;
} Heap;
void heap_push(Heap *h, HNode *node) {
int i = h->size++;
h->data[i] = node;
while (i > 0) {
int p = (i - 1) / 2;
if (h->data[i]->freq >= h->data[p]->freq) break;
HNode *t = h->data[i]; h->data[i] = h->data[p]; h->data[p] = t;
i = p;
}
}
HNode *heap_pop(Heap *h) {
HNode *top = h->data[0];
h->data[0] = h->data[--h->size];
int i = 0;
while (1) {
int s = i, l = 2*i + 1, r = 2*i + 2;
if (l < h->size && h->data[l]->freq < h->data[s]->freq) s = l;
if (r < h->size && h->data[r]->freq < h->data[s]->freq) s = r;
if (s == i) break;
HNode *t = h->data[i]; h->data[i] = h->data[s]; h->data[s] = t;
i = s;
}
return top;
}
HNode *new_node(unsigned char symbol, long freq, HNode *l, HNode *r) {
HNode *n = malloc(sizeof(HNode));
if (n == NULL) exit(1);
n->symbol = symbol;
n->freq = freq;
n->left = l;
n->right = r;
return n;
}
/* ---------- 허프만 트리 구축 ---------- */
HNode *build_tree(const long freq[]) {
Heap heap = { .size = 0 };
for (int c = 0; c < MAX_SYMBOLS; c++) {
if (freq[c] > 0) {
heap_push(&heap, new_node((unsigned char)c, freq[c], NULL, NULL));
}
}
if (heap.size == 1) { /* 문자가 한 종류뿐인 특수 케이스 */
HNode *only = heap_pop(&heap);
return new_node(0, only->freq, only, NULL);
}
while (heap.size > 1) {
HNode *a = heap_pop(&heap); /* 가장 드문 둘을 */
HNode *b = heap_pop(&heap);
heap_push(&heap, new_node(0, a->freq + b->freq, a, b)); /* 묶는다 */
}
return heap_pop(&heap);
}
/* 트리에서 코드표 추출 (DFS, 12주차 백트래킹) */
void build_codes(const HNode *node, char *path, int depth,
char codes[][32]) {
if (node->left == NULL && node->right == NULL) {
path[depth] = '\0';
strcpy(codes[node->symbol], path);
return;
}
if (node->left) {
path[depth] = '0';
build_codes(node->left, path, depth + 1, codes);
}
if (node->right) {
path[depth] = '1';
build_codes(node->right, path, depth + 1, codes);
}
}
void free_tree(HNode *node) {
if (node == NULL) return;
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void) {
const char *text = "this is an example of a huffman tree";
int n = (int)strlen(text);
printf("원문: \"%s\" (%d자 = %d비트)\n\n", text, n, n * 8);
/* 1. 빈도 집계 */
long freq[MAX_SYMBOLS] = {0};
for (int i = 0; i < n; i++) freq[(unsigned char)text[i]]++;
/* 2~4. 트리 구축 */
HNode *root = build_tree(freq);
/* 5. 코드표 */
char codes[MAX_SYMBOLS][32] = {{0}};
char path[64];
build_codes(root, path, 0, codes);
printf("=== 빈도와 코드 (자주 나올수록 짧다!) ===\n");
printf(" 문자 빈도 코드\n");
for (int c = 0; c < MAX_SYMBOLS; c++) {
if (freq[c] > 0) {
printf(" '%c' %3ld %s\n",
(c == ' ') ? '_' : (char)c, freq[c], codes[c]);
}
}
/* 인코딩 */
printf("\n=== 인코딩 ===\n");
long bits = 0;
printf("앞 10자만: ");
for (int i = 0; i < n; i++) {
if (i < 10) printf("%s|", codes[(unsigned char)text[i]]);
bits += (long)strlen(codes[(unsigned char)text[i]]);
}
printf("...\n");
printf("총 %ld비트 (원본 %d비트의 %.0f%%)\n",
bits, n * 8, 100.0 * bits / (n * 8));
/* 디코딩: 비트를 따라 트리를 내려가다 잎에 닿으면 문자 출력 */
printf("\n=== 디코딩 (트리 타고 내려가기) ===\n");
/* 인코딩 비트열을 만들어서 다시 풀어본다 */
static char bitstream[4096];
int bp = 0;
for (int i = 0; i < n; i++) {
const char *code = codes[(unsigned char)text[i]];
for (int k = 0; code[k]; k++) bitstream[bp++] = code[k];
}
bitstream[bp] = '\0';
char decoded[256];
int dp = 0;
const HNode *cur = root;
for (int i = 0; i < bp; i++) {
cur = (bitstream[i] == '0') ? cur->left : cur->right;
if (cur->left == NULL && cur->right == NULL) {
decoded[dp++] = (char)cur->symbol;
cur = root; /* 잎 도착 = 문자 하나 완성, 처음부터 */
}
}
decoded[dp] = '\0';
printf("복원: \"%s\"\n", decoded);
printf("검증: %s\n", strcmp(text, decoded) == 0 ? "원본과 완전 일치!" : "실패!");
printf("\n왜 구분자 없이 해독이 되는가?\n");
printf("-> 모든 문자가 트리의 '잎'이라 어떤 코드도 다른 코드의\n");
printf(" 접두사가 될 수 없다 (접두사 코드). 잎에 닿으면 무조건 확정!\n");
printf("\n실사용: ZIP(deflate)의 후반부, JPEG, MP3의 엔트로피 코딩\n");
printf("(전반부는 LZ 계열 사전 압축 - 프로젝트에서 조합합니다)\n");
free_tree(root);
return 0;
}
$ ./build/huffman
원문: "this is an example of a huffman tree" (36자 = 288비트)
=== 빈도와 코드 (자주 나올수록 짧다!) ===
문자 빈도 코드
'_' 7 111
'a' 4 010
'e' 4 011
'f' 3 1101
'h' 2 0001
'i' 2 1000
'l' 1 00100
'm' 2 1001
'n' 2 0011
'o' 1 00101
'p' 1 00001
'r' 1 10110
's' 2 1010
't' 2 1100
'u' 1 10111
'x' 1 00000
=== 인코딩 ===
앞 10자만: 1100|0001|1000|1010|111|1000|1010|111|010|0011|...
총 135비트 (원본 288비트의 47%)
=== 디코딩 (트리 타고 내려가기) ===
복원: "this is an example of a huffman tree"
검증: 원본과 완전 일치!
왜 구분자 없이 해독이 되는가?
-> 모든 문자가 트리의 '잎'이라 어떤 코드도 다른 코드의
접두사가 될 수 없다 (접두사 코드). 잎에 닿으면 무조건 확정!
실사용: ZIP(deflate)의 후반부, JPEG, MP3의 엔트로피 코딩
(전반부는 LZ 계열 사전 압축 - 프로젝트에서 조합합니다)
허프만 부호화
빈도 7인 공백(_로 표시)은 3비트, 빈도 1인 x는 5비트를 받았습니다. 전체는 288비트에서 135비트로, 47%로 줄었습니다. 코드표를 훑어보면 어떤 코드도 다른 코드로 시작하지 않는다는 것을 확인할 수 있습니다. 010(a)으로 시작하는 다른 코드는 없고, 00으로 시작하는 코드들은 전부 4~5비트로 서로 구분됩니다.
9.4 힙으로 트리 만들기
HNode *build_tree(const long freq[]) {
Heap heap = { .size = 0 };
for (int c = 0; c < MAX_SYMBOLS; c++) {
if (freq[c] > 0) {
heap_push(&heap, new_node((unsigned char)c, freq[c], NULL, NULL));
}
}
if (heap.size == 1) { /* 문자가 한 종류뿐인 특수 케이스 */
HNode *only = heap_pop(&heap);
return new_node(0, only->freq, only, NULL);
}
while (heap.size > 1) {
HNode *a = heap_pop(&heap); /* 가장 드문 둘을 */
HNode *b = heap_pop(&heap);
heap_push(&heap, new_node(0, a->freq + b->freq, a, b)); /* 묶는다 */
}
return heap_pop(&heap);
}
루프 본체가 세 줄입니다. 최소 힙에서 둘 꺼내고, 합쳐서, 다시 넣기. 9.2절의 표 그대로입니다. 12주차에서 힙을 만들어 둔 덕분에 알고리즘이 이렇게 짧아졌습니다. “자료구조를 잘 고르면 알고리즘이 단순해진다”는 말의 좋은 예입니다. Heap은 12주차의 정수 힙에서 원소 타입만 HNode *로 바꾼 것이고, 비교는 ->freq로 합니다.
HNode는 8주차 구조체입니다. symbol(글자), freq(빈도), left/right(자식 포인터). 묶음 노드는 글자가 없으니 symbol = 0으로 두고, 잎인지는 left == NULL && right == NULL로 판단합니다. new_node는 7주차 malloc이고, 그래서 main 끝에 free_tree가 있습니다. valgrind로 검사하면 누수 0입니다.
9.5 실험: 글자가 한 종류뿐이면?
heap.size == 1 특수 처리를 빼면 어떻게 될까요? 입력이 AAAA라면 힙에 노드가 하나뿐이고, while (heap.size > 1)은 한 번도 돌지 않으며, 그 노드 자체가 뿌리로 반환됩니다. 뿌리가 곧 잎이니 경로 길이가 0, 코드가 빈 문자열입니다. 인코딩하면 0비트가 되고, 디코딩할 비트가 없으니 복원이 불가능합니다.
특수 처리가 있는 실제 예제에 AAAA를 넣어 봤습니다.
원문: "AAAA" (4자 = 32비트)
=== 빈도와 코드 (자주 나올수록 짧다!) ===
문자 빈도 코드
'A' 4 0
=== 인코딩 ===
앞 10자만: 0|0|0|0|...
총 4비트 (원본 32비트의 12%)
=== 디코딩 (트리 타고 내려가기) ===
복원: "AAAA"
억지로 부모 노드를 하나 만들어 A를 왼쪽 자식으로 두니 코드가 0 한 비트가 되고, 4비트로 정상 복원됩니다. 이런 경계 조건(edge case)을 놓치면 “대부분 잘 동작하는데 가끔 깨지는” 코드가 됩니다. 9.4절의 while을 쓰면서 “노드가 하나뿐이면?”이라고 스스로 물어보는 습관이 이 특수 처리를 만듭니다.
9.6 코드 추출과 디코딩
void build_codes(const HNode *node, char *path, int depth,
char codes[][32]) {
if (node->left == NULL && node->right == NULL) {
path[depth] = '\0';
strcpy(codes[node->symbol], path);
return;
}
if (node->left) {
path[depth] = '0';
build_codes(node->left, path, depth + 1, codes);
}
if (node->right) {
path[depth] = '1';
build_codes(node->right, path, depth + 1, codes);
}
}
12주차 트리 순회(DFS)입니다. 내려가면서 path[depth]에 0 또는 1을 적고, 잎에 닿으면 path에 \0을 붙여 문자열로 만든 뒤 코드표에 복사합니다. 되돌아올 때 path를 지우지 않아도 되는 이유는 다음 형제가 같은 자리 path[depth]를 덮어쓰기 때문입니다. 13주차 트라이의 collect와 완전히 같은 구조입니다.
디코딩은 더 단순합니다.
const HNode *cur = root;
for (int i = 0; i < bp; i++) {
cur = (bitstream[i] == '0') ? cur->left : cur->right;
if (cur->left == NULL && cur->right == NULL) {
decoded[dp++] = (char)cur->symbol;
cur = root; /* 잎 도착 = 문자 하나 완성, 처음부터 */
}
}
비트를 읽으며 트리를 타고 내려가다 잎에 닿으면 글자 하나 확정, 다시 뿌리로. 접두사 코드 덕분에 “여기까지가 한 글자인가?”를 고민할 필요가 없습니다. 잎에 닿았다는 것이 곧 끝났다는 뜻입니다. 9.1절에서 0|10|10|11을 손으로 끊어 읽은 과정이 이 코드입니다.
9.7 어디에 쓰이나
허프만은 1952년 논문인데 지금도 현역입니다.
- ZIP (deflate): LZ77(반복 문자열을 참조로) + 허프만(빈도 압축)의 2단 구성
- JPEG: 변환 계수를 허프만으로
- MP3: 엔트로피 코딩 단계
- PNG: deflate를 그대로 사용
RLE와 허프만이 노리는 중복이 다르다는 점이 중요합니다. RLE는 “같은 글자의 연속”을, 허프만은 “글자별 빈도 편차”를 먹고 삽니다. 그래서 실제 압축기는 여러 기법을 조합합니다. LZ로 반복 문자열을 참조로 바꾸고, 남은 것을 허프만으로 줄이는 식입니다. 12절의 프로젝트 2에서 허프만을 진짜 파일 압축기로 만들고, 그 결과를 gzip과 비교해 봅니다.
10. 편집 거리: 오타 교정의 원리
10.1 두 문자열은 얼마나 다른가
마지막 알고리즘입니다. “kitten을 sitting으로 바꾸려면 최소 몇 번 고쳐야 하는가?” 허용하는 연산은 세 가지입니다. 글자 하나를 삽입, 삭제, 다른 글자로 교체. 각각 1번으로 셉니다.
이 최소 횟수를 편집 거리(edit distance) 또는 레벤슈타인 거리라고 합니다. kitten → sitting은 3입니다(k→s 교체, e→i 교체, g 삽입). 이 값 하나로 “두 문자열이 얼마나 비슷한가”를 숫자로 잴 수 있고, 그것이 맞춤법 검사기, diff, DNA 서열 비교의 공통 원리입니다.
10.2 예제: edit_distance.c
examples/edit_distance.c:
/*
* edit_distance.c - 편집 거리: 오타 교정의 원리
* 16주차: 문자열 알고리즘
*
* "kitten을 sitting으로 바꾸려면 최소 몇 번 고쳐야 하나?"
* 허용 연산: 삽입, 삭제, 교체 (각 1회)
*
* 레벤슈타인 거리라고도 부르며, 동적 계획법(DP)의 대표 문제입니다.
* 맞춤법 검사기("혹시 이 단어?"), DNA 서열 비교, diff 명령의 원리!
*
* 점화식: dp[i][j] = word1의 앞 i자를 word2의 앞 j자로 만드는 비용
* 같은 문자면: dp[i-1][j-1] (공짜)
* 다르면: 1 + min(교체 dp[i-1][j-1], 삭제 dp[i-1][j], 삽입 dp[i][j-1])
*/
#include <stdio.h>
#include <string.h>
#define MAX_LEN 32
int min3(int a, int b, int c) {
int m = (a < b) ? a : b;
return (c < m) ? c : m;
}
int edit_distance(const char *a, const char *b, int show_table) {
int la = (int)strlen(a);
int lb = (int)strlen(b);
int dp[MAX_LEN][MAX_LEN];
/* 기저: 빈 문자열에서/으로 만들기 = 전부 삽입/삭제 */
for (int i = 0; i <= la; i++) dp[i][0] = i;
for (int j = 0; j <= lb; j++) dp[0][j] = j;
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]; /* 공짜 */
} else {
dp[i][j] = 1 + min3(dp[i - 1][j - 1], /* 교체 */
dp[i - 1][j], /* 삭제 */
dp[i][j - 1]); /* 삽입 */
}
}
}
if (show_table) {
printf(" ");
for (int j = 0; j < lb; j++) printf("%2c ", b[j]);
printf("\n");
for (int i = 0; i <= la; i++) {
if (i == 0) printf(" ");
else printf(" %c ", a[i - 1]);
for (int j = 0; j <= lb; j++) printf("%2d ", dp[i][j]);
printf("\n");
}
}
return dp[la][lb];
}
int main(void) {
printf("=== 편집 거리: kitten -> sitting ===\n");
int d = edit_distance("kitten", "sitting", 1);
printf("\n거리 = %d\n", d);
printf("경로 예: kitten -> sitten(교체 k->s) -> sittin(교체 e->i)\n");
printf(" -> sitting(삽입 g)\n");
printf("\n표 읽는 법: 오른쪽 아래 끝 칸이 답.\n");
printf("각 칸은 왼쪽(삽입)/위(삭제)/대각선(교체 or 공짜) 중 최소 + 1\n");
printf("\n=== 맞춤법 검사기 흉내 ===\n");
const char *dictionary[] = {
"apple", "apply", "ample", "maple", "grape",
"happy", "angle", "angel", "table", "cable",
};
int dict_size = 10;
const char *typos[] = {"aple", "anlge", "tabel"};
for (int t = 0; t < 3; t++) {
printf("\n입력: \"%s\" <- 사전에 없음! 비슷한 단어는?\n", typos[t]);
int best_dist = 999;
for (int w = 0; w < dict_size; w++) {
int dist = edit_distance(typos[t], dictionary[w], 0);
if (dist < best_dist) best_dist = dist;
}
printf(" 제안:");
for (int w = 0; w < dict_size; w++) {
if (edit_distance(typos[t], dictionary[w], 0) == best_dist) {
printf(" %s(거리%d)", dictionary[w], best_dist);
}
}
printf("\n");
}
printf("\n=== DNA 서열 비교 (생물정보학의 그 문제) ===\n");
const char *dna1 = "GATTACA";
const char *dna2 = "GCATGCA";
printf("%s vs %s: 편집 거리 %d\n",
dna1, dna2, edit_distance(dna1, dna2, 0));
printf("(거리가 가까울수록 유사한 서열 - 진화적 근연도!)\n");
printf("\n정리:\n");
printf("1. DP 표 한 장이면 O(n*m). 재귀로 풀면 지수 시간!\n");
printf("2. '큰 문제의 답 = 작은 문제 답들의 조합' = 동적 계획법\n");
printf(" (17주차에서 DP를 본격적으로 다룹니다)\n");
printf("3. 응용: 맞춤법 교정, diff, DNA 정렬, 검색어 '혹시...?'\n");
return 0;
}
$ ./build/edit_distance
=== 편집 거리: kitten -> sitting ===
s i t t i n g
0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3
거리 = 3
경로 예: kitten -> sitten(교체 k->s) -> sittin(교체 e->i)
-> sitting(삽입 g)
표 읽는 법: 오른쪽 아래 끝 칸이 답.
각 칸은 왼쪽(삽입)/위(삭제)/대각선(교체 or 공짜) 중 최소 + 1
=== 맞춤법 검사기 흉내 ===
입력: "aple" <- 사전에 없음! 비슷한 단어는?
제안: apple(거리1) ample(거리1) maple(거리1)
입력: "anlge" <- 사전에 없음! 비슷한 단어는?
제안: angle(거리2) angel(거리2)
입력: "tabel" <- 사전에 없음! 비슷한 단어는?
제안: table(거리2)
=== DNA 서열 비교 (생물정보학의 그 문제) ===
GATTACA vs GCATGCA: 편집 거리 3
(거리가 가까울수록 유사한 서열 - 진화적 근연도!)
정리:
1. DP 표 한 장이면 O(n*m). 재귀로 풀면 지수 시간!
2. '큰 문제의 답 = 작은 문제 답들의 조합' = 동적 계획법
(17주차에서 DP를 본격적으로 다룹니다)
3. 응용: 맞춤법 교정, diff, DNA 정렬, 검색어 '혹시...?'
편집 거리
10.3 DP 표 — 손으로 채우기
/* 기저: 빈 문자열에서/으로 만들기 = 전부 삽입/삭제 */
for (int i = 0; i <= la; i++) dp[i][0] = i;
for (int j = 0; j <= lb; j++) dp[0][j] = j;
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]; /* 공짜 */
} else {
dp[i][j] = 1 + min3(dp[i - 1][j - 1], /* 교체 */
dp[i - 1][j], /* 삭제 */
dp[i][j - 1]); /* 삽입 */
}
}
}
dp[i][j]의 뜻부터 정확히 합시다. “a의 앞 i글자를 b의 앞 j글자로 바꾸는 최소 연산 수”입니다. dp[i][j]의 i, j는 글자 개수이고, 그래서 코드에서 마지막 글자를 볼 때 a[i - 1], b[j - 1]로 하나씩 빼는 것입니다(4주차 인덱스 0부터).
기저 조건: dp[i][0] = i는 “a의 i글자를 빈 문자열로 만들려면 i번 삭제”입니다. dp[0][j] = j는 그 반대로 j번 삽입입니다. 표의 첫 행과 첫 열이 0, 1, 2, 3, …으로 채워지는 이유입니다.
점화식은 “마지막 글자를 어떻게 처리할지”만 묻습니다.
- 마지막 글자가 같으면: 그 글자는 건드릴 필요가 없으니, 그 글자를 뺀 앞부분끼리의 답
dp[i-1][j-1]을 그대로 가져옵니다. 비용 0. - 다르면: 세 가지 중 최소를 고르고 1을 더합니다.
dp[i-1][j-1] + 1: a의 마지막 글자를 b의 마지막 글자로 교체하고, 나머지는 앞부분끼리dp[i-1][j] + 1: a의 마지막 글자를 삭제하고, a의 앞 i−1글자를 b의 j글자로dp[i][j-1] + 1: b의 마지막 글자를 삽입하고, a의 i글자를 b의 앞 j−1글자로
표에서 보면 대각선 왼쪽 위가 교체, 바로 위가 삭제, 바로 왼쪽이 삽입입니다. 각 칸을 채울 때 이웃 세 칸만 보면 됩니다. 작은 예로 직접 채워 봅시다. cat → cut입니다.
c u t
0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 1
거리 1
dp[1][1](cvsc): 같으니 대각선dp[0][0] = 0. 0.dp[2][2](cavscu):a≠u. 세 이웃dp[1][1] = 0,dp[1][2] = 1,dp[2][1] = 1중 최소 0에 1을 더해 1. (a를u로 교체)dp[3][3](catvscut):t=t. 대각선dp[2][2] = 1. 답 1.
조금 더 큰 예, sunday → saturday도 표를 찍어 보면 오른쪽 아래가 3입니다(a, t 삽입, n→r 교체).
s a t u r d a y
0 1 2 3 4 5 6 7 8
s 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3
거리 3
직접 해 보기:
kitten→sitting표(위 실행 결과)의dp[2][2](kivssi)가 왜 1인지,dp[6][7]이 왜 3인지 이웃 세 칸으로 설명해 보세요.
10.4 실험: 같은 논리를 재귀로 짜면
점화식을 보면 재귀가 떠오릅니다. 5주차 재귀로 짜면 이렇게 짧습니다.
/* 이렇게 쓰면 안 됩니다 */
int ed(const char *a, int i, const char *b, int j) {
if (i == 0) return j;
if (j == 0) return i;
if (a[i-1] == b[j-1]) return ed(a, i-1, b, j-1);
return 1 + min3(ed(a,i-1,b,j-1), ed(a,i-1,b,j), ed(a,i,b,j-1));
}
논리는 똑같고 코드도 더 짧습니다. 그런데 얼마나 느릴까요? 서로 완전히 다른 두 문자열(abcd... vs ABCD...)로 길이를 늘려 가며 함수 호출 횟수와 시간을 재 봤습니다. 오른쪽은 DP 표가 채우는 칸 수입니다.
길이 재귀 호출 수 시간(ms) DP 칸 수
4 481 0.0 16
6 13483 0.0 36
8 398593 1.2 64
10 12146179 35.2 100
12 377393953 1284.0 144
14 11885772379 36473.5 196
길이가 2 늘 때마다 호출이 약 30배씩 늘어 길이 14에서 118억 번, 36초입니다. 길이 20이면 하루가 넘습니다. DP는 같은 답을 196칸으로 냅니다. 왜 이런 차이가 날까요? 재귀는 ed(a, 5, b, 5)를 수백만 번 다시 계산합니다. 세 갈래로 갈라지는 호출들이 서로 다른 경로로 같은 (i, j)에 도달하기 때문입니다. 5주차 피보나치의 폭발과 같은 현상이고, 규모는 더 큽니다.
DP 표는 그 중복 계산을 없앱니다. 각 (i, j)를 딱 한 번만 계산해 표에 적어 두고, 필요하면 꺼내 씁니다. O(n × m)입니다. 이것이 동적 계획법(Dynamic Programming, DP)의 본질입니다.
큰 문제의 답 = 작은 문제 답들의 조합. 그 작은 답들을 표에 저장해 재사용한다.
사실 우리는 이미 DP를 만난 적이 있습니다. 14주차의 플로이드-워셜이 “경유지를 하나씩 늘려 가며 이전 결과를 재활용”했죠. 다음 주 17주차에서 DP를 본격적으로 파고듭니다.
10.5 실전 응용
맞춤법 검사기: 입력 단어가 사전에 없으면, 사전의 모든 단어와 편집 거리를 계산해 가장 가까운 것을 제안합니다. 출력의 aple → apple, ample, maple(모두 거리 1)이 그 예입니다. 사전이 수십만 단어라도 단어 길이가 짧아 표가 작으니 충분히 빠릅니다.
anlge → angle, angel(거리 2)도 흥미롭습니다. n과 l이 바뀐 오타인데, 편집 거리로는 교체 2번입니다. 인접한 두 글자의 교환을 1로 치는 다메라우-레벤슈타인 거리를 쓰면 거리 1이 됩니다. 사람의 오타는 대부분 인접 교환이라 실제 맞춤법 검사기들이 이 변형을 씁니다.
diff 명령: 두 파일의 줄 단위 편집 거리를 구하고, 표를 오른쪽 아래에서 거꾸로 따라가면 “어느 줄이 추가되고 삭제되었는지”가 나옵니다. git diff가 보여 주는 그 화면입니다(연습 문제 8번).
DNA 서열 비교: GATTACA vs GCATGCA의 거리 3. 두 서열의 유사도를 재는 기본 도구입니다. 실제로는 삽입·삭제·교체마다 다른 비용을 주는 변형(니들만-분쉬 알고리즘)을 씁니다.
검색 엔진의 “혹시 이것을 찾으셨나요?”: 검색어와 인기 검색어들의 편집 거리를 계산합니다. 물론 실제로는 검색 기록 통계까지 결합합니다.
11. 한글과 \0 — 바이트 단위 알고리즘의 함정
이번 주 알고리즘은 전부 char 단위, 즉 바이트 단위로 동작합니다. 4주차에서 한글 한 글자는 UTF-8로 3바이트라고 배웠습니다. 그럼 한글 텍스트에 이 알고리즘들을 쓰면 어떻게 될까요? 직접 확인했습니다.
strlen("안녕하세요 C 언어") = 24 (글자는 10개)
"녕" 의 바이트: eb 85 95
단순 검색 "하세" -> 바이트 위치 6 (글자로는 2번째)
검색 자체는 됩니다. 하세의 바이트열 6개가 텍스트의 바이트열 안에 그대로 있으니 브루트포스든 KMP든 보이어-무어든 찾습니다. 다만 결과가 바이트 위치입니다. “6번째 바이트”를 “3번째 글자”로 바꾸려면 한글이 3바이트임을 알고 나눠야 합니다. 그리고 보이어-무어의 last[256] 표는 바이트 기준이라, 한글 텍스트에서는 eb, 85 같은 바이트가 패턴에 거의 항상 들어 있어 점프가 짧아집니다. DNA 텍스트에서 본 것과 같은 현상입니다.
문제는 “글자 하나”라는 개념을 쓰는 알고리즘에서 생깁니다. 12절의 정규식 엔진에 한글을 넣어 봤습니다.
정규식 엔진에 한글:
/^.$/ ~ "안" -> 불일치 (. 은 1바이트만 먹는다)
/^...$/ ~ "안" -> 매치 (3바이트 = 점 3개)
/^[가-힣]$/ ~ "안" -> 불일치 (클래스도 바이트 단위라 뜻이 깨진다)
/^[가-힣]+$/ ~ "안" -> 매치
.은 “아무 글자 하나”인데 1바이트만 먹으니 안(3바이트)과 맞지 않습니다. [가-힣]은 더 심각합니다. 가의 첫 바이트 ea부터 힣의 첫 바이트까지를 바이트 범위로 읽고 뒤의 바이트들은 낱글자로 취급하기 때문에, 원래 뜻(“한글 한 글자”)과 전혀 다른 조건이 됩니다. 마지막 줄이 매치된 것도 의도한 결과가 아니라 우연입니다.
편집 거리도 마찬가지입니다.
편집 거리(바이트 단위):
"안녕" vs "안녕!" = 1
"가" vs "나" = 3 (한 글자 차이인데)
"가" vs "각" = 1
가=ea b0 80 나=eb 82 98 각=ea b0 81
가와 나는 사람 눈에 한 글자 차이지만 바이트가 셋 다 달라 거리 3이고, 가와 각은 마지막 바이트만 달라 거리 1입니다. 한글 맞춤법 검사기를 이 코드로 만들면 가→나 오타를 가→각보다 세 배 먼 것으로 봅니다.
해법은 두 가지입니다. UTF-8을 디코딩해 글자 단위 정수 배열(int 또는 wchar_t)로 바꾼 뒤 같은 알고리즘을 돌리거나, 라이브러리(PCRE의 UTF 모드 등)를 쓰는 것입니다. 이번 주 코드는 원리를 보이기 위한 바이트 단위 구현이라는 것을 기억해 두세요.
마지막으로 \0입니다. 모든 코드가 strlen으로 길이를 재므로, 데이터 중간에 \0이 있으면 거기서 끝난 것으로 봅니다.
\0 이 끼면: "ab\0cd" 에서 "cd" 검색 -> -1 (strlen 이 2 에서 멈추니 뒤는 없는 셈)
텍스트 파일이라면 문제없지만, 이미지나 실행 파일 같은 바이너리 데이터에서 패턴을 찾으려면 길이를 따로 받아야 합니다. 12절의 compress_tool이 fgetc로 바이트를 하나씩 세고 strlen을 쓰지 않는 이유가 이것입니다.
12. 실습 프로젝트
projects/ 폴더에는 이번 주 알고리즘으로 만든 실제로 쓸 수 있는 도구 세 개가 있습니다. make로 이미 빌드되어 있습니다.
프로젝트 1: grep 클론 (mini_grep.c)
매일 쓰는 grep을 직접 만듭니다. 진짜 grep처럼 보이어-무어로 각 줄을 검색하고, 옵션도 실제와 같습니다. 인자 없이 실행하면 내장 샘플로 데모를 돌립니다.
$ ./build/mini_grep
mini grep - 보이어-무어 기반 텍스트 검색
=====================================
샘플 파일(grep_sample.txt) 내용:
--------------------------------------
The quick brown fox jumps over the lazy dog
Programming in C is powerful
The Linux kernel is written in C
Python is easier but slower than C
the fox returned to the forest
Kernel modules extend the kernel
--------------------------------------
>>> 기본 검색: 'kernel'
The Linux [kernel] is written in C
Kernel modules extend the [kernel]
>>> -i (대소문자 무시): 'kernel'
The Linux [kernel] is written in C
[Kernel] modules extend the kernel
>>> -n (줄 번호): 'The'
1:[The] quick brown fox jumps over the lazy dog
3:[The] Linux kernel is written in C
>>> -c (개수만): 'C'
3
>>> -v (반전): 'C'가 없는 줄
The quick brown fox jumps over the lazy dog
the fox returned to the forest
Kernel modules extend the kernel
직접 사용: ./mini_grep [-inc v] 패턴 파일
파이프도 지원: cat 파일 | ./mini_grep 패턴
실제 파일로 써 봅시다. notes.txt에 네 줄을 넣어 두었습니다.
$ ./build/mini_grep kernel notes.txt
The Linux [kernel] is written in C
Kernel modules extend the [kernel]
$ ./build/mini_grep -in kernel notes.txt
1:The Linux [kernel] is written in C
3:[Kernel] modules extend the kernel
$ ./build/mini_grep -c kernel notes.txt
2
$ ./build/mini_grep zzz notes.txt; echo $?
1
$ cat notes.txt | ./build/mini_grep -v kernel
Python is easier
no match here
$ ./build/mini_grep -x a notes.txt
알 수 없는 옵션: -x
$ ./build/mini_grep kernel notes.txt nofile.txt
nofile.txt: 열 수 없음
notes.txt:The Linux [kernel] is written in C
notes.txt:Kernel modules extend the [kernel]
$ echo $?
2
프로그램의 뼈대는 이렇습니다.
typedef struct {
int ignore_case; /* -i */
int line_numbers; /* -n */
int count_only; /* -c */
int invert; /* -v */
} Options;
void bm_prepare(const char *pattern, int m); /* 나쁜 문자 표 */
int bm_search(const char *text, int n, const char *pattern, int m);
void print_highlighted(const char *line, int pos, int m);
void to_lower_string(char *dst, const char *src, size_t cap);
int grep_stream(FILE *fp, const char *filename, ...); /* 핵심 루프 */
눈여겨볼 점 1 — 유닉스 도구의 예법. 이 프로그램은 1주차에서 배운 쉘의 약속 세 가지를 지킵니다.
- 파일 인자가 없으면 표준 입력을 읽는다: 그래서
cat notes.txt | ./build/mini_grep -v kernel이 동작합니다. 파이프라인에 끼워 넣을 수 있는 도구가 되는 것이죠. - 종료 코드가 의미를 갖는다: 1주차의
echo $?를 기억하세요. 찾으면 0, 없으면 1, 파일을 못 여는 등 오류가 있으면 2입니다. 진짜grep과 같은 약속이라, 쉘 스크립트에서if ./build/mini_grep pattern file; then ...처럼 조건문에 쓸 수 있습니다. - 결과는 표준 출력, 오류는 표준 오류로:
nofile.txt: 열 수 없음은fprintf(stderr, ...)로 나갑니다. 결과를 파이프로 넘길 때 오류 메시지가 섞이지 않습니다.
여러분이 만든 도구가 유닉스 생태계의 일원이 되는 순간입니다. 18주차 이후 시스템 프로그래밍에서 이 규약들을 훨씬 자세히 다룹니다.
눈여겨볼 점 2 — 대소문자 무시의 구현. -i 옵션은 텍스트와 패턴을 모두 소문자로 바꾼 사본을 만들어 검색합니다(to_lower_string, 4주차 tolower에 (unsigned char)를 씌운 그 코드입니다). 매치 위치를 찾은 뒤 출력은 원본으로 하므로 화면에는 원래 대소문자가 그대로 나옵니다([Kernel]). 비교용 사본과 표시용 원본을 분리하는 것은 텍스트 처리에서 자주 쓰는 패턴입니다.
눈여겨볼 점 3 — 옵션 파싱. -in처럼 옵션을 붙여 쓸 수 있는 것은 argv[arg][0] == '-'인 인자의 글자를 하나씩 switch로 처리하기 때문입니다. 3주차 switch와 7주차에서 본 argv(문자열 포인터 배열)의 조합입니다.
확장 아이디어: -r 재귀 디렉터리 검색(22주차 파일 시스템 예고), 정규식 통합(프로젝트 3과 합체), ANSI 컬러 출력, 한 줄에 여러 번 나올 때 전부 강조
프로젝트 2: 허프만 압축 도구 (compress_tool.c)
9절의 허프만을 진짜 파일 압축기로 완성합니다. 예제와 격이 다른 두 가지가 추가됩니다.
추가 1 — 비트 패킹. 예제에서는 코드를 '0', '1' 글자로 다뤘습니다. 이해하기는 쉽지만 실제로는 비트 하나가 1바이트를 차지하니 압축이 아니라 8배 팽창입니다. 이 프로젝트는 진짜 비트로 씁니다.
static void bw_put(BitWriter *w, int bit) {
w->buffer = (unsigned char)((w->buffer << 1) | (bit & 1));
if (++w->bits == 8) {
fputc(w->buffer, w->fp);
w->buffer = 0;
w->bits = 0;
}
}
비트를 buffer에 8개 모아 1바이트로 씁니다. << 1로 한 칸 밀고 | bit로 새 비트를 끝에 붙입니다. 3주차에서 배운 비트 연산이 여기서 제 역할을 합니다. bw_flush는 마지막에 8개를 못 채우고 남은 비트를 0으로 채워 내보냅니다. 이걸 빼먹으면 파일 끝의 몇 글자가 사라집니다.
추가 2 — 자기 완결 파일 형식. 압축 파일만 가지고 복원할 수 있어야 합니다. 그러려면 같은 허프만 트리를 다시 만들 수 있어야 하고, 그래서 헤더에 빈도표를 저장합니다.
[매직 "HUF1"][원본 크기 8B][심볼 수 2B][심볼 1B + 빈도 8B] x 심볼 수 [압축 비트스트림...]
실제 파일을 압축해서 헤더를 들여다봤습니다. 이 글의 원고 자체(105,712바이트)입니다.
$ ./build/compress_tool -c article.md article.huf
article.md: 105712 -> 79632 바이트 (75.3%)
$ ./build/compress_tool -d article.huf article.back
$ cmp article.md article.back && echo "동일"
동일
$ od -A d -t x1 -N 24 article.huf
0000000 48 55 46 31 f0 9c 01 00 00 00 00 00 a7 00 0a 9d
0000016 09 00 00 00 00 00 00 20
9주차에서 배운 od로 읽어 봅시다.
| 바이트 | 값 | 뜻 |
|---|---|---|
| 0~3 | 48 55 46 31 |
"HUF1". 매직 넘버. 이 파일이 우리 형식인지 확인용 |
| 4~11 | f0 9c 01 00 00 00 00 00 |
원본 크기. 리틀 엔디언(8주차)으로 읽으면 0x00019cf0 = 105,712 |
| 12~13 | a7 00 |
심볼 수 0x00a7 = 167종 |
| 14 | 0a |
첫 심볼 = 10 = \n |
| 15~22 | 9d 09 00 ... |
\n의 빈도 0x099d = 2,461번 |
| 23 | 20 |
둘째 심볼 = 32 = 공백 |
원고에 줄바꿈이 2,461개라는 것까지 헤더에서 읽힙니다. 해제할 때는 이 빈도표로 트리를 다시 만듭니다. 같은 빈도 → 같은 알고리즘 → 같은 트리이므로 정확히 복원됩니다. 원본 크기를 저장하는 이유는 마지막 바이트의 패딩 비트를 글자로 오독하지 않기 위해서입니다. “몇 글자까지 읽을지”를 알아야 멈출 수 있습니다.
gzip과 비교하면 어떨까요?
$ gzip -9 -k article.md
$ ls -l article.md article.huf article.md.gz
105712 article.md
79632 article.huf
33097 article.md.gz
허프만만으로는 75%, gzip은 31%입니다. gzip(deflate)은 LZ77로 반복되는 문자열을 먼저 참조로 바꾸고 그 결과를 허프만으로 줄입니다. 이 원고에는 printf, pattern 같은 단어가 수백 번 반복되니 LZ 단계의 효과가 큽니다. 9.7절에서 말한 “노리는 중복이 다르다”의 실제 크기입니다.
아주 작은 파일도 압축해 봤습니다.
$ printf 'aaaa' > four.txt
$ ./build/compress_tool -c four.txt four.huf
four.txt: 4 -> 24 바이트 (600.0%)
4바이트가 24바이트가 됐습니다. 헤더(매직 4 + 크기 8 + 심볼 수 2 + 심볼 1 + 빈도 8 = 23바이트)에 본문 1바이트입니다. 8절의 교훈 그대로, 압축에는 고정 비용이 있어서 작은 데이터는 오히려 커집니다.
프로그램의 데모 모드는 세 종류의 데이터를 만들어 압축률을 비교합니다.
$ ./build/compress_tool
...
[영어 텍스트 (빈도 차이 큼)]
demo_input.bin: 11220 -> 6277 바이트 (55.9%)
라운드트립 검증: 원본과 완전 일치!
[편중 데이터 ('a'가 70%)]
demo_input.bin: 12000 -> 2648 바이트 (22.1%)
라운드트립 검증: 원본과 완전 일치!
[난수 데이터 (빈도 균등)]
demo_input.bin: 12000 -> 14318 바이트 (119.3%)
라운드트립 검증: 원본과 완전 일치!
...
압축 도구
세 결과가 8절 RLE의 교훈을 다시 확인해 줍니다. 허프만은 빈도 편차를 먹고 사는 알고리즘이므로, 빈도가 균등한 난수는 오히려 커집니다. 여기에 빈도표 헤더(256종 × 9바이트 = 2.3KB) 비용까지 더해져 119%가 된 것입니다. 그리고 세 경우 모두 라운드트립 검증을 통과했다는 점이 중요합니다. 1바이트라도 다르면 그 압축기는 쓸모가 없습니다.
확장 아이디어: 앞단에 RLE나 간단한 LZ77 붙이기(ZIP에 한 걸음 더), 헤더의 long을 고정 크기 uint64_t로 바꿔 다른 컴퓨터와 호환(9주차 바이너리 교훈), 큰 파일을 블록 단위로 처리
프로젝트 3: 정규식 엔진 (mini_regex.c)
grep과 에디터의 심장인 정규식 엔진을 백트래킹 방식으로 만듭니다. 롭 파이크가 『The Practice of Programming』에서 선보인 유명한 20줄 매처의 확장판입니다.
지원 문법:
c 리터럴 . 아무 문자 하나
^ 줄 시작 $ 줄 끝
* 0회 이상 + 1회 이상 ? 0 또는 1회
[a-z] 문자 클래스 [^abc] 부정 클래스
$ ./build/mini_regex
미니 정규식 엔진 (백트래킹)
=====================================
=== 리터럴과 . ===
[OK] "my cat is cute" ~ /cat/ -> 매치
[OK] "my dog is cute" ~ /cat/ -> 불일치
[OK] "cut and cot" ~ /c.t/ -> 매치
=== 앵커 ^ $ ===
[OK] "cat food" ~ /^cat/ -> 매치
[OK] "my cat" ~ /^cat/ -> 불일치
[OK] "my cat" ~ /cat$/ -> 매치
[OK] "cat food" ~ /cat$/ -> 불일치
[OK] "cat" ~ /^cat$/ -> 매치
=== 수량자 * + ? ===
[OK] "ac" ~ /ab*c/ -> 매치
[OK] "abbbc" ~ /ab*c/ -> 매치
[OK] "ac" ~ /ab+c/ -> 불일치
[OK] "abc" ~ /ab+c/ -> 매치
[OK] "color" ~ /colou?r/ -> 매치
[OK] "colour" ~ /colou?r/ -> 매치
=== 문자 클래스 [ ] ===
[OK] "bat" ~ /[abc]at/ -> 매치
[OK] "rat" ~ /[abc]at/ -> 불일치
[OK] "hello" ~ /[a-z]+/ -> 매치
[OK] "abc" ~ /[0-9]+/ -> 불일치
[OK] "5a5" ~ /[^0-9]/ -> 매치
=== 조합: 실전 패턴 ===
[OK] "user@example.com" ~ /^[a-z]+@[a-z]+/ -> 매치
[OK] "not an email" ~ /^[a-z]+@[a-z]+/ -> 불일치
[OK] "42" ~ /^[0-9][0-9]?[0-9]?$/ -> 매치
[OK] "1234" ~ /^[0-9][0-9]?[0-9]?$/ -> 불일치
[OK] "hello world" ~ /h.*o/ -> 매치
[OK] "# comment line" ~ /^#.*$/ -> 매치
=== 백트래킹이 일하는 순간 ===
[OK] "aaa" ~ /a*a/ -> 매치
(a*가 aaa를 다 먹으면 실패 -> 두 개만 먹게 '되돌아가서' 성공)
=====================================
테스트 결과: 26 / 26 통과
=====================================
한계와 다음 단계 (심화 예고):
1. 백트래킹은 최악에 지수 시간 - (a*)*b 류의 패턴 폭탄!
(ReDoS 공격: 서비스를 정규식 하나로 멈추게 하는 실제 보안 이슈)
2. 해결책: 톰슨 구성법 - 정규식을 NFA(상태 기계)로 바꿔
O(nm)을 보장 (grep, Go, Rust 정규식 라이브러리의 방식)
3. 괄호 그룹, |, 역참조 등은 확장 과제로
핵심은 상호 재귀 + 백트래킹입니다. 함수 다섯 개가 서로를 부릅니다.
int match_class(const char *cls, char c, int *cls_len); /* [a-z] 처리 */
int match_one(const char *pattern, char c, int *elem_len);/* 한 요소 매치 */
int match_star(const char *elem, const char *rest, const char *text);
int match_here(const char *pattern, const char *text); /* 상호 재귀의 중심 */
int regex_match(const char *pattern, const char *text);
regex_match: 패턴이^으로 시작하면 텍스트 처음에서만, 아니면 모든 시작 위치에서match_here를 시도합니다. 1절의 브루트포스와 같은 바깥 루프입니다.match_here: “패턴이 텍스트의 여기서부터 맞는가”를 답합니다. 패턴이 비었으면 성공,$면 텍스트가 끝났는지 확인, 그 외에는 요소 하나(match_one)와 그 뒤의 수량자를 보고 갈라집니다.match_one: 요소 하나(리터럴,.,[...])가 글자 하나와 맞는지, 그리고 그 요소가 패턴에서 몇 글자를 차지하는지(elem_len) 알려 줍니다.[a-z]는 5글자짜리 요소입니다.match_star:X*처리. “0개 먹고 나머지 시도, 안 되면 1개 먹고 나머지 시도, …”를 반복합니다.
? 처리에 백트래킹이 가장 잘 보입니다.
if (quant == '?') {
/* X? = X 있는 버전 먼저, 안 되면 없는 버전 (백트래킹!) */
if (first && match_here(pattern + elem_len + 1, text + 1)) return 1;
return match_here(pattern + elem_len + 1, text);
}
“일단 X가 있다고 보고 나머지를 맞춰 본다. 실패하면 되돌아와서 X가 없다고 보고 다시 맞춰 본다.” 14주차 DFS에서 본 그 백트래킹입니다.
/a*a/가 "aaa"에 매치되는 과정이 백미입니다. match_star는 a*가 0개, 1개, 2개, 3개 먹는 경우를 차례로 시도합니다. 0개 먹으면 나머지 패턴 a가 텍스트 첫 a와 맞아 바로 성공합니다. 예제 코드는 “적게 먹는 것부터” 시도하는 방식이라 되돌아갈 일이 적지만, 진짜 정규식 엔진들은 “최대한 많이 먹고(탐욕) 안 되면 뱉는” 방식이라 a*가 셋을 다 먹은 뒤 하나를 뱉어야 성공합니다. 어느 쪽이든 “해 보고 안 되면 다른 길”이라는 구조는 같습니다.
26개 테스트가 전부 통과한다는 점도 봐 주세요. 정규식 엔진처럼 경우의 수가 많은 코드는 테스트 없이 만들 수 없습니다. 매치되어야 할 것과 되면 안 될 것을 양쪽 다 검사하는 것도 중요합니다. test() 함수의 셋째 인자가 기대값이고, 프로그램의 종료 코드는 테스트가 하나라도 실패하면 1입니다. 5주차 make처럼 자동화된 검사에 끼워 넣을 수 있는 구조입니다.
실험: 정직한 한계 — ReDoS. 백트래킹은 “가능한 모든 길”을 시도하므로, 길이 많은 패턴에서는 폭발합니다. 우리 엔진으로 /a*a*a*a*a*b/를 b가 없는 a n개에 매치시켜 봤습니다.
패턴 /a*a*a*a*a*b/ 를 'a' n개(b 없음)에 매치 시도:
n 시간(ms)
10 0.1
15 0.9
20 3.4
25 9.6
30 23.9
35 50.6
40 97.9
a* 다섯 개가 a 40개를 “누가 몇 개씩 먹을지” 모든 조합을 시도합니다. n이 2배(20 → 40) 될 때 시간이 29배(3.4 → 97.9ms) 늘었습니다. 입력이 40글자인데 100ms입니다. 괄호 그룹을 지원하는 엔진에서 (a*)*b 같은 패턴을 쓰면 조합이 지수적으로 늘어 글자 30개로도 사실상 영원히 안 끝납니다.
이것이 ReDoS(Regular expression Denial of Service)라는 실제 보안 취약점입니다. 사용자 입력을 취약한 패턴으로 검사하는 서버는 요청 하나로 CPU가 100%에 고정될 수 있습니다. 2019년 Cloudflare의 전 세계 장애가 정규식 하나에서 시작됐습니다.
해결책은 백트래킹을 버리고 정규식을 상태 기계(NFA)로 변환해 텍스트를 한 번만 훑는 것입니다(톰슨 구성법). grep, Go, Rust의 정규식 라이브러리가 그렇게 동작하고, 어떤 패턴이든 O(n × m)이 보장됩니다. 참고 자료의 Russ Cox 글이 이 차이를 가장 잘 설명합니다.
확장 아이디어: 그룹 (), 선택 |, 이스케이프 \d \w, 최소 매치 *?, mini_grep에 탑재, UTF-8 디코딩(11절)
13. 자주 하는 실수와 함정
이번 주 실험에서 실제로 일으켜 본 것들입니다.
1. KMP 실패 함수의 후퇴를 if로. while (len > 0 && ...)이어야 합니다. 2.4절에서 AAAAB의 실패 함수가 틀리고, 없는 매치를 찾는 것까지 봤습니다.
2. 매치 후 j = 0으로 리셋. 겹치는 매치(AAAA에서 AA)를 놓칩니다(2.6절). j = fail[j-1]로.
3. 라빈-카프에서 해시만 믿기. MOD = 7 실험에서 가짜 양성이 6번 나왔습니다(3.5절). 해시 일치 후 반드시 문자로 재확인하세요.
4. 롤링 해시의 뺄셈. (x - y) % MOD는 부호 있는 타입에서는 음수, 부호 없는 타입에서는 거대한 수가 됩니다(3.4절). (x + MOD - y) % MOD로.
5. 해시에 char를 그대로. 128 이상 바이트가 음수로 읽혀 해시가 어긋납니다. (unsigned char)로.
6. 보이어-무어에서 점프 하한 누락. if (jump < 1) jump = 1;이 없으면 패턴이 뒤로 가고 배열 밖을 읽습니다(4.4절).
7. Z 알고리즘의 구분자 누락. 패턴 + 텍스트를 그냥 붙이면 일치가 텍스트로 이어져 Z값이 패턴 길이를 넘고, 진짜 매치를 놓칩니다(5.4절). 양쪽에 없는 글자를 끼우세요.
8. RLE의 개수 한계 미검사. 256이 1바이트에 담기며 0이 되어 데이터가 조용히 사라집니다(8.4절).
9. 허프만에서 문자 한 종류뿐인 입력. 트리가 잎 하나가 되어 코드 길이가 0입니다(9.5절). 특수 처리 필수.
10. 비트 스트림의 flush 누락. 마지막 8비트 미만이 파일에 안 써져 끝이 잘립니다.
11. 압축 파일에 원본 크기 미저장. 패딩 비트를 글자로 오독해 끝에 쓰레기가 붙습니다.
12. 편집 거리를 메모 없는 재귀로. 길이 14에 36초입니다(10.4절). DP 표가 정답.
13. 바이트 단위 코드에 한글. .이 1바이트만 먹고 [가-힣]이 깨집니다(11절). 글자 단위로 디코딩하거나 라이브러리를 쓰세요.
14. 백트래킹 정규식에 신뢰할 수 없는 패턴. ReDoS 위험입니다(12절). 시간 제한을 두거나 NFA 방식을 쓰세요.
15. 압축 후 라운드트립 검증 생략. “얼마나 줄었나”보다 “정확히 복원되나”가 먼저입니다.
16. 고정 크기 버퍼. fail[256], joined[1024] 같은 학습용 버퍼는 긴 입력에서 넘칩니다. 실전 코드라면 길이를 검사하거나 malloc으로.
14. 연습 문제
기본 문제
- 실패 함수 손 계산:
ABCDABD와AAAAAA의 실패 함수를 2.1절의 표 형식으로 구하고,naive_vs_kmp.c의build_failure를 불러 확인하세요. - KMP로 회전 판정: 두 문자열이 서로 회전한 관계인지 판정하세요(
"abcde"와"cdeab"). 힌트 —s + s에서 다른 쪽을 검색하면 됩니다. - 대소문자 무시 검색: 보이어-무어에 대소문자 무시 옵션을 추가하세요. 나쁜 문자 표를 어떻게 바꿔야 할까요?
mini_grep의 방식(사본을 소문자로)과 비교해 보세요. - 모든 등장 위치 찾기: 접미사 배열 검색을 lower_bound / upper_bound로 바꿔 모든 위치를 돌려주게 하세요. 7.4절의 출력이 나와야 합니다.
- RLE 개선: 연속이 2 이하일 때는 그대로 두는 형식을 설계해, 반복 없는 데이터에서 크기가 늘지 않게 하세요. “어떤 데이터가 그 형식에서 늘어나는지”도 답하세요(8.3절의 원리상 반드시 있습니다).
- 비교 횟수 세기: 1.2절의 표를
naive_search에printf를 붙여 직접 재현하세요. 그리고 텍스트AAAAAAAAAA, 패턴AAB에서 비교 횟수를 먼저 계산한 뒤 실행해 맞추세요.
심화 문제
- 두 문자열의 최장 공통 부분 문자열: 두 문자열을 구분자로 이어 붙여 접미사 배열을 만들고, LCP가 큰 이웃 중 서로 다른 원본에서 온 쌍을 찾으세요. 표절 검사의 핵심입니다.
- 편집 거리 경로 역추적: DP 표에서 오른쪽 아래부터 거꾸로 따라가며 “어떤 연산을 어디에 했는지”를 출력하세요.
kitten→sitting에서 “교체 k→s, 교체 e→i, 삽입 g”가 나와야 합니다.diff의 원리입니다. - 아호-코라식 맛보기: 13주차 트라이에 실패 링크(KMP의 실패 함수를 트라이로 확장)를 붙이면 여러 패턴을 한 번에 찾을 수 있습니다. 원리를 조사하고 작은 예로 구현해 보세요.
- LZ77 맛보기: 앞서 나온 문자열을 (거리, 길이) 쌍으로 참조하는 간단한 LZ77을 구현하고,
compress_tool앞에 붙여 이 글 원고의 압축률이 75%에서 얼마나 내려가는지 재 보세요. - UTF-8 편집 거리: 11절의 문제를 풀어 보세요. 문자열을 글자 단위
int배열로 디코딩한 뒤 편집 거리를 구해가와나의 거리가 1이 되게 하세요. - 정규식에 그룹과 선택 추가:
mini_regex에()와|를 추가하세요. 그리고(a*)*b가 정말 폭발하는지 12절의 방법으로 시간을 재 보세요.
마치며
이번 주에 배운 것을 정리합니다.
- 검색 4대장: KMP(실패에서 학습, 스트림), 라빈-카프(롤링 해시, 멀티 패턴), 보이어-무어(건너뛰기,
grep), Z(구조 분석 겸용). 그리고 실전에서는strstr가 그 넷을 다 이긴다는 것. - 접미사 배열: 텍스트를 전처리하는 색인. 이진 탐색 + LCP로 반복 조각 발견.
- 압축: RLE(연속), 허프만(빈도). 패턴이 없으면 압축도 없고, 모든 것을 줄이는 압축은 존재할 수 없다.
- 편집 거리: DP 표 한 장 = 오타 교정,
diff, DNA 정렬. 재귀로 풀면 118억 번. - 한글: 바이트 단위 알고리즘은 검색은 되지만 “글자 하나”가 필요한 곳에서 깨진다.
- 정규식: 백트래킹은 우아하지만 폭탄(ReDoS)을 안고 있다.
이번 주에 반복해 나온 주제도 정리해 두겠습니다.
첫째, 전처리의 가치. KMP의 실패 함수, 보이어-무어의 나쁜 문자 표, 접미사 배열, 허프만 트리. 전부 “미리 계산해 두고 반복 사용”하는 구조입니다. 무엇을 언제 전처리할지 판단하는 것이 알고리즘 설계의 큰 축입니다.
둘째, 이전 주차의 재활용. 해시(13주차)가 라빈-카프로, 힙과 트리(12주차)가 허프만으로, 이진 탐색(15주차)이 접미사 배열로, 트라이의 DFS(13주차)가 코드 추출로, 백트래킹(14주차)이 정규식으로. 새 지식이 아니라 같은 도구의 새 용도였습니다.
셋째, 정직한 측정. KMP가 일상 텍스트에서는 브루트포스보다 느리다는 것, 허프만이 난수 데이터를 키운다는 것, if 하나 잘못 쓴 KMP가 대부분의 테스트를 통과한다는 것. 알고리즘의 자랑만 외우지 않고 한계까지 숫자로 아는 것이 실력입니다. 이 글의 표들은 전부 여러분 컴퓨터에서 다시 만들 수 있습니다. 숫자가 다르게 나오면 왜 다른지 생각해 보세요. 그것이 다음 주 최적화의 출발점입니다.
이번 주로 여러분은 grep, ZIP, 맞춤법 검사기, 정규식 엔진의 원리를 전부 직접 구현해 봤습니다. “도구를 쓰는 사람”에서 “도구를 만들 수 있는 사람”으로 한 걸음 더 나아간 것입니다.
다음 주는 Part 2의 대미, 고급 알고리즘과 최적화입니다. 편집 거리에서 맛본 동적 계획법을 본격적으로 파고들고, 탐욕법과 분할 정복까지 알고리즘 설계 패러다임을 정리합니다.
체크리스트
- [ ] 브루트포스 검색의 비교 횟수를 작은 예에서 손으로 셀 수 있고, 최악이 언제 발생하는지 안다
- [ ] 실패 함수를 손으로 계산할 수 있다 (
ABABC→ 0 0 1 2 0,AABAACAABAA→ 0 1 0 1 2 0 1 2 3 4 5) - [ ] 실패 함수 계산에
while이 필요한 이유와,if로 쓰면 어떤 일이 생기는지 안다 - [ ] KMP에서 텍스트 포인터가 후진하지 않는다는 것과 그 의미(스트림, O(n+m))를 안다
- [ ] 겹치는 매치를 놓치지 않는 방법(
j = fail[j-1])을 안다 - [ ] 다항식 해시를 256진법으로 설명하고, 롤링 해시의 O(1) 갱신 식을 쓸 수 있다
- [ ]
(a + MOD - b) % MOD가 필요한 이유를 부호 있는/없는 타입 양쪽에서 설명할 수 있다 - [ ] 해시 일치 후 문자 재확인이 필수인 이유를 실험 결과로 설명할 수 있다
- [ ] 보이어-무어의 나쁜 문자 점프를 5단계 그림으로 그릴 수 있다
- [ ] 긴 패턴·큰 알파벳이 보이어-무어에 유리하고 DNA에서는 불리한 이유를 안다
- [ ] Z 배열의 정의와 Z-박스 재활용 아이디어를 안다
- [ ] Z로 패턴 검색할 때 구분자가 필요한 이유를 안다
- [ ] 네 검색 알고리즘과
strstr의 실전 성능 순서를 안다 - [ ] 접미사 배열이 무엇이고 왜 이진 탐색이 가능한지 안다
- [ ] LCP 최댓값이 최장 반복 부분 문자열인 이유를 설명할 수 있다
- [ ] RLE가 역효과 나는 조건과 “만능 압축은 불가능”의 이유를 안다
- [ ] 허프만 트리 구축(드문 둘 묶기)을
aaaabbbccd로 손으로 할 수 있다 - [ ] 접두사 코드가 구분자 없이 해독되는 이유를 안다
- [ ] 허프만에서 문자 한 종류뿐인 경계 조건을 안다
- [ ] 비트 패킹과 flush, 헤더의 빈도표와 원본 크기가 왜 필요한지 안다
- [ ] 편집 거리 DP 표를
cat→cut으로 손으로 채울 수 있다 - [ ] 같은 논리를 재귀로 짜면 왜 지수 시간인지 숫자로 설명할 수 있다
- [ ] 바이트 단위 알고리즘이 한글에서 어디까지 되고 어디서 깨지는지 안다
- [ ] 백트래킹 정규식의 동작과 ReDoS 위험을 안다
- [ ]
mini_grep의 종료 코드 0/1/2가 각각 언제 나오는지 안다 - [ ] 세 프로젝트를 빌드하고 검증 통과를 확인했다
- [ ] (도전)
mini_grep에mini_regex를 합체시켜 봤다
참고 자료
- CLRS(Introduction to Algorithms) Chapter 32 (String Matching)
- Rob Pike, “The Practice of Programming” 9장 — 20줄 정규식 매처의 원전
- Russ Cox, “Regular Expression Matching Can Be Simple And Fast” — ReDoS와 NFA의 명문
- VisuAlgo — Suffix Array
- Huffman coding (Wikipedia)
man 3 strstr,man 3 regcomp— C 표준 라이브러리와 POSIX 정규식- 다음 주차: 17주차 고급 알고리즘과 최적화 (DP, 탐욕법, 분할 정복)