1.1 명제 Propositions

증명을 이야기하기 전에 먼저 "무엇을" 증명하는지부터 분명히 해야 합니다. 수학에서 증명의 대상은 항상 명제(proposition)입니다. 명제란 참(true)인지 거짓(false)인지가 분명히 정해지는 평서문을 말합니다. 명령문이나 의문문, 감탄문은 명제가 아닙니다. "문 좀 닫아줘"는 참도 거짓도 아니니까요.

여러 명제를 "그리고", "또는", "아니다", "~이면 ~이다" 같은 연결사로 묶으면 합성 명제(compound proposition)가 됩니다. 예컨대 \( P \)가 "비가 온다", \( Q \)가 "땅이 젖는다"라면, \( P \implies Q \)는 "비가 오면 땅이 젖는다"라는 새로운 명제입니다. 우리는 곧 이런 연결사들을 도구처럼 다루게 될 거예요.

1.2 술어 Predicates

방금 본 \( x + 1 = 2 \)는 명제가 아니었습니다. 그런데 변수 \( x \)에 구체적인 값을 넣으면 명제가 되지요. 이렇게 변수가 들어가서 그 변수의 값에 따라 진릿값이 달라지는 문장을 술어(predicate)라고 부릅니다. 보통 \( P(x) \), \( Q(n) \) 같은 표기를 씁니다.

술어가 중요한 이유는, 수학의 거의 모든 흥미로운 주장이 "모든 \( n \)에 대해 \( P(n) \)이 성립한다" 또는 "어떤 \( n \)이 존재해서 \( P(n) \)이 성립한다" 형태이기 때문입니다. 이 두 가지를 각각 전칭(universal) 양화와 존재(existential) 양화라고 부르고, 기호로 \( \forall n,\ P(n) \), \( \exists n,\ P(n) \)이라 씁니다. 양화 기호의 자세한 사용법은 다음 챕터에서 다룹니다. 지금은 술어가 명제의 "변수 버전"이라는 것만 기억하면 충분해요.

1.3 공리적 방법 The Axiomatic Method

"증명한다"는 게 도대체 무엇일까요? 머리에 떠오르는 그럴듯한 설명을 하는 것? 그림을 그려 보는 것? 수많은 예를 확인하는 것? 셋 다 영감을 주지만, 셋 다 수학적 증명은 아닙니다. 수학에서 증명이란 이미 받아들인 사실들로부터 논리적으로 새 사실을 이끌어내는 과정입니다.

그러면 그 "이미 받아들인 사실"은 어디서 올까요? 끝없이 거슬러 올라갈 수는 없으니, 어딘가에서 멈춰야 합니다. 그 출발점을 공리(axiom)라고 부릅니다. 공리는 증명 없이 참이라고 합의하는 명제입니다. 그리고 공리로부터 논리만 사용해 증명한 명제를 정리(theorem)라 부르고, 그 과정 자체가 증명(proof)입니다.

이 사고방식은 기원전 300년경 유클리드(Euclid)의 『원론(Elements)』에서 시작되었습니다. 유클리드는 다섯 개의 공준과 몇 개의 공통 관념에서 출발해 평면기하 전체를 쌓아 올렸어요. 2200년이 지난 후 힐베르트(Hilbert)는 유클리드의 빈틈을 메워 더 엄밀한 공리계를 제시했고, 20세기 들어 페아노(Peano), 체르멜로–프렝켈(ZF) 같은 산술/집합론 공리계가 자리를 잡았습니다.

1.4 우리의 공리들 Our Axioms

이 책에서는 공리계를 처음부터 모두 형식적으로 까는 대신, 학부 1학년 수준의 수학에서 자연스럽게 사용하는 표준 사실들을 공리로 받아들이겠습니다. 즉, 다음과 같은 것들이에요.

• 산술 공리: 정수, 유리수, 실수의 사칙연산 법칙 — 결합법칙, 교환법칙, 분배법칙, \( 0, 1 \)의 항등 성질, 역원의 존재 등.
• 순서 공리: 실수의 \( < \) 관계가 가지는 추이성과 삼분법.
• 집합론의 기초: 합집합, 교집합, 부분집합, 빈집합 같은 개념과 그 기본 성질.
• 자연수의 잘 정렬성: 자연수의 공집합이 아닌 부분집합은 항상 최소 원소를 가진다 (수학적 귀납법의 기반).

이 공리들은 너무 친숙해서 "굳이 공리라고 부를 필요가 있나?" 싶을 정도지만, 정확히 그 친숙함이 함정이기도 합니다. 한 단계 한 단계의 추론이 정말로 이런 공리만 쓰는지 자기 자신에게 묻는 습관을 들여야 해요.

1.5 함의 증명 Proving an Implication

가장 흔히 마주치는 명제 형태가 \( P \implies Q \), 즉 "\( P \)이면 \( Q \)이다" 꼴의 함의(implication)입니다. 이걸 어떻게 증명할까요? 가장 직접적인 방법은 이렇습니다.

이때 한 가지 헷갈리는 지점이 있습니다. \( P \)가 거짓일 때 \( P \implies Q \)는 무엇일까요? 수학에서는 약속에 의해 \( P \)가 거짓이면 \( P \implies Q \)는 자동으로 참이 됩니다. "전제가 무너지면 무엇이든 결론으로 삼아도 된다"라는 뜻이에요. 이걸 공허한 참(vacuously true)이라고 부릅니다.

또 한 가지, 대우(contrapositive)와 역(inverse)을 구분해야 합니다. \( P \implies Q \)에 대해

• 대우: \( \lnot Q \implies \lnot P \). 원래 명제와 같은 진릿값을 가집니다.
• 역: \( Q \implies P \). 원래 명제와 진릿값이 다를 수 있습니다.
• 이(inverse): \( \lnot P \implies \lnot Q \). 역과 같은 진릿값을 가집니다(즉 일반적으로 원래와 다릅니다).

예를 들어 "비가 오면 땅이 젖는다"의 대우는 "땅이 젖지 않으면 비가 오지 않았다"이고 항상 같이 참/거짓이지만, 역인 "땅이 젖었으면 비가 왔다"는 원래 명제가 참이어도 거짓일 수 있습니다(스프링클러가 있으니까요). 시험에서 가장 자주 실수하는 지점이니 꼭 기억해 둡시다.

1.6 동치 증명 Proving an "If and Only If"

명제가 \( P \iff Q \) 꼴이라면, 이는 "\( P \)와 \( Q \)는 동시에 참이거나 동시에 거짓이다"라는 뜻입니다. 이걸 증명하는 방법은 두 가지가 흔합니다.

두 번째 방법은 동치 사슬(chain of equivalences)을 만드는 것입니다. \( P \iff P_1 \iff P_2 \iff \cdots \iff Q \)처럼 한 단계씩 동치 변환만으로 \( P \)에서 \( Q \)까지 가는 방식이에요. 단, 모든 단계가 정말로 동치 관계여야 합니다. 한 군데서 한쪽으로만 함의되면 사슬이 깨져요.

1.7 경우 분리 증명 Proof by Cases

때로는 명제를 한 번에 증명하기보다, 가능한 모든 상황을 몇 개의 경우로 나눠 각각에서 증명하는 게 훨씬 편합니다. 이걸 경우 분리 증명(proof by cases)이라 합니다.

경우 분리에서 가장 중요한 점은 모든 경우를 빠짐없이 다루었는가입니다. 한 경우라도 누락되면 그 영역에서 명제가 거짓일 가능성이 남아 증명이 무너지죠. 때문에 "이 외의 경우는 가능하지 않다"는 한 줄이라도 명시하는 습관이 좋습니다.

1.8 모순법 Proof by Contradiction

직접 증명이 막힐 때 강력하게 작동하는 무기가 모순법(proof by contradiction)입니다. 핵심 아이디어는 단순합니다. \( P \)를 보이고 싶다면, "\( P \)가 거짓이라고 가정해 보자"라고 시작해서 그 가정으로부터 명백한 모순(예: \( 0 = 1 \) 같은 것)을 끌어냅니다. 그러면 \( \lnot P \)는 받아들일 수 없고, 따라서 \( P \)가 참이어야 합니다.

모순법은 강력하지만 남용은 좋지 않습니다. 직접 증명이 가능한 명제를 굳이 모순법으로 쓰면, 독자가 "왜 부정에서 시작했지?" 하고 흐름을 따라가기 힘들어요. 직접 증명으로 풀리면 직접, 막히면 모순법, 정도로 생각하면 됩니다.

1.9 좋은 증명의 실제 Good Proofs in Practice

지금까지 본 증명 기법들은 도구일 뿐이고, 실제로 좋은 증명을 쓰는 일은 그 도구를 어떤 태도로 다루느냐에 달려 있습니다. 정답이 정해진 일은 아니지만, 경험적으로 다음 원칙들이 도움이 됩니다.

• 독자에게 친절할 것. 증명은 자기 자신을 위한 메모가 아니라 다른 사람에게 보내는 편지입니다. "왜 이 단계가 정당한가"를 독자가 따라올 수 있도록 충분히 설명합니다. 너무 친절해서 길어진 증명이, 너무 짧아서 막히는 증명보다 거의 항상 낫습니다.
• 흐름을 보여줄 것. 증명의 첫 줄에 "이 증명은 \( n \)에 대한 귀납이다", "이 증명은 모순법으로 진행한다" 같은 이정표를 두면 독자가 길을 잃지 않습니다.
• 정직할 것. 막힌 단계를 "쉽게 알 수 있다"라는 말로 덮으면 안 됩니다. 정말 쉬우면 한 줄을 더 적어서 보여 주고, 어려우면 어렵다고 인정하고 도움말을 줍니다.
• 예제로 검증할 것. 증명을 끝낸 뒤 작은 예 한두 개로 결론이 진짜 맞는지 확인하는 습관을 들여 두세요. 예제는 증명을 대체하지는 못하지만, 잘못된 증명을 잡아내는 가장 쉬운 방법입니다.
• 표기와 변수를 정리할 것. "여기서 \( n \)이 의미하는 게 정수 변수임을 명시", "이 \( k \)는 새로 잡은 정수임" 같은 사소한 한 줄이 독자의 두통을 막습니다.

마지막으로, 증명은 처음에 잘 안 써지는 게 정상이라는 점을 기억하세요. 실제 수학자들도 종이 한 면을 채우는 증명을 위해 십수 장의 낙서를 거칩니다. 머릿속에서 떠오른 아이디어를 정돈하고, 빈자리를 메우고, 다시 짧게 다듬는 과정이 곧 수학을 하는 일입니다. 이 책의 다음 챕터부터 우리는 이 도구들을 본격적으로 휘두르며 명제논리, 술어논리, 집합, 함수, 그래프, 이산확률에 이르기까지 이산수학의 풍경을 함께 걷게 될 거예요.

2.1 정렬 원리 증명 Well Ordering Proofs

먼저 원리부터 정확히 적어 봅시다. 자연수 집합을 \( \mathbb{N} = \{0, 1, 2, 3, \ldots\} \)로 쓰겠습니다. (0을 자연수에 포함시키느냐 마느냐는 책마다 다르지만, 이 노트에서는 0을 포함합니다. 한국 교과서 관습과 다를 수 있으니 헷갈리면 \( \mathbb{N} \)을 "음수가 아닌 정수"라고 읽어 주세요.)

너무 당연해 보이죠? 자연수 몇 개를 한 줌 집어 놓고 보면 그중 가장 작은 게 있을 수밖에 없잖아요. 그런데 이 "당연함"이 증명에 동원되면 의외로 강력합니다. 핵심 트릭은 이렇습니다. 어떤 명제가 모든 자연수에서 성립한다고 주장하고 싶을 때, 우리는 반례들의 집합을 잡습니다. 그 반례 집합이 비어 있지 않다고 가정하면, 정렬 원리에 의해 가장 작은 반례가 존재합니다. 그런데 그 "가장 작은 반례"의 성질을 자세히 들여다보면 보통 모순이 튀어나와요. 그러면 반례 집합은 처음부터 공집합이었다는 결론에 도달하고, 명제는 참이 됩니다.

이 전략을 가장 고전적인 결과 하나로 시연해 봅시다. 그리스 수학자들이 발견했을 때 충격을 받았다는 그 사실, 바로 \( \sqrt{2} \)가 유리수가 아니라는 정리입니다.

흔히 알려진 증명("\( a, b \)를 서로소로 잡으면 둘 다 짝수가 되어 모순")과는 사뭇 다른 분위기죠? 사실 두 증명은 정신은 같습니다. 둘 다 "유리수 표현이 있다면 더 단순한 표현이 또 있다"는 무한강하법(infinite descent)의 변주예요. 정렬 원리 버전은 그 무한 내려가기를 "가장 작은 반례"라는 한 번의 모순으로 깔끔하게 묶어 줍니다.

2.2 WOP 증명 템플릿 Template for WOP Proofs

앞 절의 증명을 들여다보면, 정렬 원리를 쓰는 증명은 거의 같은 골격을 따릅니다. 이걸 한 번 정리해 두면, 비슷한 문제를 만났을 때 빈칸 채우기 게임처럼 풀 수 있어요.

여기서 가장 까다로운 단계는 5번이에요. "더 작은 반례를 어떻게 만드느냐"는 명제마다 다르고, 그게 사실상 증명의 본체입니다. \( \sqrt{2} \) 증명에서는 \( n_1 = n_0(\sqrt{2} - 1) \)이라는 영리한 한 수를 둬서 \( n_1 \)이 \( n_0 \)보다 작은데도 여전히 \( C \)에 속하게 만들었죠.

한 가지만 더. 모순을 이끄는 방법은 두 가지 결이 있습니다.

• "하강(descent)" 모순: 위처럼 \( n_0 \)보다 작은 반례 \( n_1 \)을 명시적으로 구성해서 "최소"라는 성질에 직접 모순을 줌.
• "부정(refutation)" 모순: \( n_0 \)가 사실은 \( P(n_0) \)을 만족함을 보여서 \( n_0 \in C \)에 모순을 줌. 이 경우 \( n_0 \)가 \( C \)의 최소 원소라는 사실 자체보다도 \( n_0 \in C \)라는 더 약한 정보를 모순의 재료로 씀.

실전에서는 둘 중 어느 쪽이든 자연스러운 쪽으로 가면 됩니다. 다음 절에서 보여줄 소인수분해 증명은 하강의 변형으로 풀어 보겠습니다.

2.3 소인수분해 Factoring into Primes

이번엔 좀 더 묵직한 결과로 가 봅시다. 학교에서부터 익숙한 사실 — "모든 1보다 큰 자연수는 소수들의 곱으로 쓸 수 있다" — 을 정렬 원리로 정확하게 증명해 보겠습니다. 정확한 진술은 이렇습니다.

잠깐 컴퓨터과학 사이드로 빠지자면, 이 증명은 사실상 재귀적 분해 알고리즘의 정당성을 그대로 보여줍니다. 어떤 \( n \)이 들어왔을 때 (1) 소수면 그대로 반환, (2) 합성수면 \( n = ab \)인 \( a, b \)를 찾아 각각 재귀적으로 분해, 처럼 짠 함수가 항상 종료한다는 것 — 이게 정렬 원리가 보장해 주는 것이에요. 매번 더 작은 자연수에서 호출되니까, 무한히 내려갈 수가 없는 거죠. 5장의 강한 귀납법(strong induction)도 같은 사실을 다른 각도에서 말합니다.

2.4 정렬집합 Well Ordered Sets

정렬 원리는 \( \mathbb{N} \)의 특별한 성질이지만, 같은 아이디어를 다른 순서집합에도 일반화할 수 있습니다. 일반화된 개념의 이름은 정렬집합(well ordered set)이에요.

"전순서"라는 단서는, 임의의 두 원소 \( x, y \in S \)에 대해 항상 \( x \le y \)이거나 \( y \le x \)가 성립한다는 뜻입니다. (둘 다 성립하면 \( x = y \).) 이게 보장돼야 "최소"라는 말이 의미를 가지죠.

몇 가지 예를 봅시다.

일반화의 한 좋은 예로 사전식 순서(lexicographic order)를 봅시다. 두 자연수 쌍 \( (a, b), (c, d) \in \mathbb{N} \times \mathbb{N} \)에 대해

\[ (a, b) \le_{\text{lex}} (c, d) \iff a < c \;\;\text{또는}\;\; (a = c \text{ 이고 } b \le d). \]

로 정의합시다. 사전에서 단어를 정렬하는 방식과 정확히 같죠. 이 순서로 \( \mathbb{N}^2 \)는 정렬집합이 됩니다.

이 결과는 단순히 추상적 호기심이 아닙니다. 알고리즘에서 종료성을 증명할 때 단일 자연수 카운터로는 안 되는 경우, "사전식 순으로 줄어드는 (a, b) 쌍"을 잡아 종료를 보이는 기법이 자주 등장합니다. 예를 들어 두 카운터 중 하나가 가끔 늘어나도, 사전식 순서로는 전체가 줄어든다면 알고리즘은 반드시 종료하죠. 이 사실의 정당화가 정확히 정리 2.4.3이에요.

여기까지가 정렬 원리의 첫 만남입니다. 핵심을 다시 한 줄로 추리면 이렇습니다. "가장 작은 반례"는 종종 자기 자신을 부정한다 — 그러므로 처음부터 반례는 없었다. 이 한 문장이 \( \sqrt{2} \)의 무리수성에서부터 소인수분해 존재성, 알고리즘 종료성에 이르기까지 폭넓게 작동합니다. 다음 장부터는 같은 정신을 또 다른 모습으로 — 명제논리의 추론 규칙들로, 그리고 5장에서는 귀납법의 옷으로 — 다시 만나게 될 거예요.

3.1 명제로 명제 만들기 Propositions from Propositions

2장에서 우리는 "명제"를 참 또는 거짓 둘 중 하나로 판정되는 진술이라고 약속했습니다. 그런데 실제로 우리가 쓰는 진술들은 보통 작은 명제 여러 개를 이어 붙인 모양을 하고 있습니다. "오늘 비가 오면 우산을 챙긴다"처럼 말이죠. 이렇게 작은 명제로 큰 명제를 만드는 도구가 논리 연산자입니다.

이걸 한눈에 정리한 게 그 유명한 진리표입니다. T는 참(true), F는 거짓(false)입니다.

또 자주 등장하는 친구가 배타적 논리합(XOR), 기호로는 \(P \oplus Q\)입니다. "둘 중 정확히 하나만 참"일 때 참이 됩니다. 일상에서 "커피 아니면 차"라고 말할 때 보통 둘 다 마시겠다는 뜻이 아니죠 — 그게 XOR입니다.

3.2 컴퓨터 프로그램 속 명제논리 Propositional Logic in Computer Programs

프로그램이 분기하는 곳마다 명제가 숨어 있습니다. if (x > 0 && y != 0) 한 줄을 보면 \(P = (x > 0)\), \(Q = (y \neq 0)\)인 \(P \land Q\)예요. while 루프의 종료 조건도 마찬가지고요. 그래서 코드를 검증하거나 리팩터링할 때 우리는 알게 모르게 명제논리 변형을 하고 있습니다.

if x != 0 and 100 / x > 5:
    do_something()

또 한 가지, 회로 설계의 세계는 명제논리가 그대로 하드웨어가 되는 곳입니다. 트랜지스터로 AND, OR, NOT 게이트를 만들고, 그것들을 모아 가산기·메모리·CPU를 짭니다. 회로 한 칸의 출력은 입력에 대한 어떤 부울 함수이고, 그 함수의 명세가 곧 우리가 이번 챕터 내내 다루는 논리식입니다.

3.3 동치와 타당성 Equivalence and Validity

같은 의미를 다르게 쓴 두 식이 있다면 — 진리표를 만들어서 모든 행이 같은지 보면 됩니다. 그게 핵심입니다.

또 하나 중요한 개념이 타당성(validity)입니다. 어떤 식이 항진명제이면 — 즉 어떤 진릿값을 넣어도 참이라면 — 우리는 그 식을 타당하다고 말하고, 증명에 그대로 쓸 수 있습니다. \(P \land (P \to Q) \to Q\) (이름하여 modus ponens), \(((P \to Q) \land (Q \to R)) \to (P \to R)\) (가정 삼단논법) 같은 게 그렇습니다. 추론 규칙은 결국 항진명제의 모음집이에요.

3.4 명제의 대수 The Algebra of Propositions

진리표를 매번 그리는 건 변수가 \(n\)개면 \(2^n\)줄이라 금방 폭발합니다. 그래서 우리는 동치를 대수 법칙처럼 쓰는 법을 익혀야 해요. 곱셈 분배법칙처럼, 논리식도 한 모양에서 다른 모양으로 변형할 수 있습니다.

이런 변형을 충분히 하면 어떤 명제든 정해진 모양으로 맞출 수 있습니다. 두 가지 표준형이 특히 자주 등장합니다.

3.5 SAT 문제 The SAT Problem

변수 \(n\)개짜리 식이 충족가능한지 — 즉 어떤 진릿값 배정에서 참이 되는지 — 를 물어보는 문제가 SAT입니다. 이름부터가 "satisfiability". 단순해 보이지만, 컴퓨터과학에서 가장 유명한 어려운 문제 중 하나예요.

변수가 \(n\)개면 가능한 배정은 \(2^n\)가지. 가장 단순한 알고리즘은 모두 시도해 보는 것이고, \(n=60\)만 되어도 \(10^{18}\) 근처라 현실적이지 않습니다. 이걸 다항시간에 푸는 알고리즘이 있느냐? — 그게 그 유명한 \(\mathsf{P}\) vs \(\mathsf{NP}\) 문제입니다.

3.4절의 정규형 변환과 합치면 그림이 또렷해집니다. 임의의 명제를 CNF로 옮길 수 있으므로 "충족가능성을 묻는 문제"의 정규 형태는 CNF-SAT이고, 거의 모든 SAT solver는 CNF 입력을 받습니다. 이 작은 사실 — 모든 부울 추론을 CNF 한 통에 욱여넣을 수 있다는 사실 — 이 컴퓨터로 논리를 다루는 일을 가능하게 만든 결정적 한 수예요.

3.6 술어식 Predicate Formulas

명제논리는 "참/거짓이 정해진 진술"만 다뤘습니다. 그런데 수학에서 우리는 자주 "\(x > 0\)"이나 "\(x\)는 소수다" 같이 변수에 따라 참/거짓이 갈리는 진술을 씁니다. 이런 걸 술어(predicate)라고 해요.

양화사 식의 부정은 자주 쓰니 외워둘 가치가 있습니다.

이제 진짜 흥미로운 부분으로. 양화사가 두 개 이상 붙으면 순서가 의미를 결정합니다.

술어식까지 갖추면 우리는 이 책 뒷부분에서 만날 거의 모든 수학적 진술을 정밀하게 적을 수 있습니다. "모든 자연수 \(n\)에 대해 어떤 소수 \(p\)가 있어 \(p > n\)이다"라는 진술은 그대로 \(\forall n \in \mathbb{N}.\, \exists p \in \mathrm{Prime}.\, p > n\)이고, 이걸 증명하면 소수가 무한히 많다는 정리가 됩니다 (유클리드, 곧 4장에서).

4.1 집합 Sets

가장 단순한 그릇부터 시작합시다. 집합(set)은 그저 "물건들의 모임"입니다. 그런데 보통의 모임과 다른 점이 두 가지 있어요. 첫째, 순서가 없습니다. 둘째, 중복이 없습니다. 그래서 \(\{1, 2, 3\}\)과 \(\{3, 1, 2\}\), 그리고 \(\{1, 1, 2, 2, 3\}\)은 모두 같은 집합입니다. 파이썬의 set을 떠올리면 거의 그대로예요.

집합을 적는 방법은 두 가지입니다. 원소를 그대로 나열하는 외연적 표기와, 조건으로 거르는 내포적 표기입니다. 예를 들어 \(\{2, 4, 6, 8\}\)은 외연적이고, \(\{n \in \mathbb{N} \mid n \text{이 짝수이고 } n \le 8\}\)은 내포적입니다. 후자는 "어떤 우주집합 \(\mathbb{N}\)에서 조건에 맞는 것만 골라낸다"는 뜻이에요.

특별한 집합 몇 개는 기호가 정해져 있습니다. \(\mathbb{N}\)은 자연수, \(\mathbb{Z}\)는 정수, \(\mathbb{Q}\)는 유리수, \(\mathbb{R}\)은 실수, \(\mathbb{C}\)는 복소수입니다. 그리고 원소가 하나도 없는 집합을 공집합(empty set)이라 하고 \(\emptyset\) 또는 \(\{\}\)로 씁니다. \(\emptyset\)은 단 하나뿐이라는 점이 중요합니다 (외연성 공리로부터 따라 나옵니다).

두 집합이 서로 부분집합이면 같습니다. 이 사실은 의외로 자주 쓰여요. 어떤 집합이 다른 집합과 같다는 것을 직접 보이기 어려울 때, 양방향 포함을 따로따로 보이는 전략이 자연스럽게 나옵니다.

이제 집합끼리 섞고 빼는 연산을 봅시다. 두 집합 \(A, B\)에 대해

• 합집합: \(A \cup B = \{x \mid x \in A \text{ 또는 } x \in B\}\)
• 교집합: \(A \cap B = \{x \mid x \in A \text{ 그리고 } x \in B\}\)
• 차집합: \(A \setminus B = \{x \mid x \in A \text{ 그리고 } x \notin B\}\)
• 여집합: 어떤 우주집합 \(U\)가 정해져 있을 때 \(\overline{A} = U \setminus A\)

이 연산들은 명제논리의 ∨, ∧, ¬와 정확히 짝을 이룹니다. 그래서 명제논리의 항등식이 집합 항등식으로 그대로 옮겨가요. 예컨대 드모르간 법칙 \(\overline{A \cup B} = \overline{A} \cap \overline{B}\)는 \(\neg(p \lor q) \equiv \neg p \land \neg q\)의 집합 버전입니다.

4.2 수열 Sequences

집합은 순서가 없습니다. 하지만 살다 보면 "1번, 2번, 3번"처럼 자리가 정해져 있는 모임이 필요할 때가 있어요. 사람 줄, 시간순 이벤트, 좌표 \((x, y)\) 같은 것들이죠. 그래서 수학자들은 수열(sequence) 또는 튜플(tuple)이라는 두 번째 자료구조를 만들었습니다.

집합과 수열의 차이를 분명히 해두겠습니다. \(\{1, 2\} = \{2, 1\}\)이지만 \((1, 2) \neq (2, 1)\)이에요. 또 \(\{1, 1\} = \{1\}\)이지만 \((1, 1) \neq (1)\)입니다. 한국어 강의에서 "튜플"이라는 말을 영어 그대로 쓸 때가 많은데, 본질은 순서 있는 모음입니다.

4.3 함수 Functions

이제 본격적인 무대입니다. 함수(function)는 "입력을 받으면 출력을 돌려주는 규칙"입니다. 고등학교에서 \(f(x) = x^2\) 같은 식으로 만났겠지만, 수학에서 함수를 정의할 때는 식이 있어야 한다고 요구하지 않습니다. 식 없이 그냥 "어떤 입력에 어떤 출력이 대응되는가"만 명시하면 충분합니다.

여기서 두 가지를 강조하고 싶어요. 첫째, "정확히 하나씩"이 핵심입니다. 입력 하나에 출력이 두 개 나오면 함수가 아닙니다. 둘째, 공역과 치역은 다릅니다. 공역은 "출력이 살 수 있는 집"이고, 치역은 "실제로 살고 있는 집"입니다. 한국어 학생들이 자주 헷갈리는 지점이에요.

함수의 성격은 입출력의 짝짓기 패턴에 따라 세 가지로 분류됩니다.

그림으로 보면 직관이 더 빠릅니다.

   단사 (injective)        전사 (surjective)       전단사 (bijective)
   ------------------     -------------------     -------------------
   A         B            A         B             A         B
   1 ──────► a            1 ──────► a             1 ──────► a
   2 ──────► b            2 ─┐                    2 ──────► b
   3 ──────► c            3 ─┴────► b             3 ──────► c
             d (남음)                  c
   서로 다른 → 서로 다른     모든 b가 화살을 받음       둘 다 만족

단사는 "겹치지 않는다", 전사는 "남는 게 없다", 전단사는 "둘 다"라고 외워두면 좋아요. 영어로는 "into" vs "onto"라는 표현도 자주 등장하는데, "into"는 그냥 함수, "onto"는 전사를 가리킵니다.

4.4 이항관계 Binary Relations

함수보다 더 일반적인 개념이 이항관계입니다. 직관적으로 "이 두 원소는 어떤 식으로든 관련이 있다"를 가리키는 표시예요. 예를 들어 정수에서 \(\le\), 사람들 사이에서 "친구다", 도시들 사이에서 "직항이 있다" 같은 것들이 모두 이항관계입니다.

처음 보면 "관계가 부분집합이라고?" 하고 갸웃할 수 있어요. 이렇게 생각해 보세요. 어떤 두 원소가 관계가 있느냐 없느냐는 결국 yes/no 질문이고, 관련 있는 쌍들만 모아두면 그게 곧 \(A \times B\)의 부분집합이 됩니다. 모든 쌍에 대해 한 번씩 답을 적어둔 표가 바로 \(R\)이에요.

다시 말해 함수는 "왼쪽 입력마다 짝이 정확히 하나"인 관계입니다. 관계 일반은 짝이 0개여도, 여러 개여도 괜찮아요. 그래서 함수는 관계의 "엄격한 부분집합"인 거죠.

합성은 화살표를 이어 붙이는 것입니다. \(a\)에서 \(R\) 화살을 따라가서 \(b\)에 도착하고, 거기서 \(S\) 화살을 따라가서 \(c\)에 도착할 수 있다면 \((a, c)\)는 합성 관계에 들어갑니다. 함수의 합성 \((g \circ f)(x) = g(f(x))\)이 바로 이 일반 정의의 특수한 경우예요.

역도 마찬가지입니다. 일반 관계의 역은 항상 잘 정의됩니다 (그냥 쌍을 뒤집으면 끝). 하지만 함수의 역은 전단사일 때만 함수가 된다고 했죠. 그게 바로 관계와 함수의 차이를 보여주는 좋은 예입니다.

4.5 유한 기수 Finite Cardinality

마지막은 "집합의 크기"입니다. 유한집합의 크기는 그냥 원소의 개수예요. 직관적으로는 너무 당연해서 정의할 필요가 있나 싶지만, 큰 집합이나 무한집합으로 가면 "크기"라는 말 자체가 엄밀해야 합니다. 이 챕터에서는 유한 케이스만 다루고, 무한집합의 기수는 한참 뒤(15장쯤)에서 다시 등장합니다.

기수의 산수에는 몇 가지 기본 규칙이 있어요.

• \(|A \cup B| = |A| + |B| - |A \cap B|\) (포함-배제 원리, 11장에서 자세히)
• \(|A \times B| = |A| \cdot |B|\)
• \(|A^n| = |A|^n\)
• \(|\mathcal{P}(A)| = 2^{|A|}\)

이걸 함수의 단사/전사로 다시 쓸 수 있습니다. 유한집합 \(A, B\) 사이에 단사 \(f: A \to B\)가 있다면 \(A\)의 원소들이 \(B\) 안으로 겹치지 않게 들어간 것이니 \(|A| \le |B|\)예요. 거꾸로 전사 \(g: A \to B\)가 있다면 \(B\)의 모든 원소가 화살을 받았으니 \(A\)가 그것들을 모두 만들어낼 수 있어야 하고, 그래서 \(|A| \ge |B|\). 그리고 전단사가 있다면 \(|A| = |B|\).

이 정리가 강력한 이유는, 크기를 직접 세지 않고도 함수를 만들어 비교할 수 있다는 점입니다. 무한집합으로 일반화할 때 진짜 빛을 발해요. "두 집합이 같은 크기다"를 "전단사가 있다"로 정의하는 게 칸토어의 통찰이었거든요.

이름이 귀엽죠. "비둘기집(pigeonhole) 원리"라 부르는 이유는, 비둘기 \(n+1\)마리를 둥지 \(n\)개에 넣으면 어떤 둥지에는 비둘기가 두 마리 이상 들어간다는 그림으로 외우면 쉽기 때문입니다. 단순해 보이지만 조합론, 그래프이론, 알고리즘 분석 곳곳에서 결정적으로 쓰이는 무기예요. 11장에서 본격적으로 다시 만납니다.

5.1 일반 귀납법 Ordinary Induction

자연수 \( n \)에 대해 어떤 명제 \( P(n) \)이 모두 참이라는 사실을 증명하고 싶다고 합시다. 무한히 많은 \( n \)을 하나하나 검사할 수는 없습니다. 이때 등장하는 묘책이 바로 귀납법입니다.

가장 흔한 비유는 도미노입니다. 길게 늘어선 도미노가 무한히 있어요. 우리가 보장하고 싶은 건 "모든 도미노가 결국 쓰러진다"는 사실입니다. 그러려면 두 가지만 확인하면 충분합니다. 첫째, 첫 번째 도미노를 우리가 직접 손가락으로 밀어 쓰러뜨립니다. 둘째, 임의의 \( k \)번째 도미노가 쓰러지면 \( k+1 \)번째도 반드시 쓰러진다는 보장이 있습니다. 이 두 가지가 동시에 성립하면, 첫 번째 도미노가 두 번째를 쓰러뜨리고, 두 번째가 세 번째를 쓰러뜨리고… 끝없이 이어져 모든 도미노가 쓰러집니다. 한 번도 손대지 않은 백만 번째 도미노조차도요.

이 직관을 그대로 수학 언어로 옮긴 것이 일반 귀납법입니다.

여기서 귀납 단계의 \( P(k) \)를 귀납 가설(induction hypothesis)이라고 부릅니다. 증명을 쓸 때 우리는 보통 "어떤 \( k \)에 대해 \( P(k) \)가 성립한다고 가정하자"라고 운을 떼고, 그 가정으로부터 \( P(k+1) \)을 끌어냅니다. 가정을 일단 하나 사 놓고, 그것을 사다리 삼아 한 칸 위로 올라가는 것이라고 봐도 됩니다.

처음 보면 "어? 이게 정말로 모든 \( n \)을 증명하는 거 맞아?"라는 의심이 들 수 있습니다. 그도 그럴 것이, 우리는 어디에서도 "구체적인 \( n=27 \)일 때"를 따로 증명하지 않았으니까요. 비밀은 도미노의 사슬에 있습니다. \( P(1) \)이 참이고, \( P(1) \implies P(2) \)이니 \( P(2) \)도 참. 이어서 \( P(2) \implies P(3) \)이니 \( P(3) \)도 참. 이렇게 27단계를 거치면 \( P(27) \)에 도달합니다. 우리가 증명에서 한 일은 사실상 "어떤 \( k \)를 가져와도 다음 칸으로 넘어갈 수 있는 보편적인 한 줄짜리 사다리"를 만든 것이고, 그 사다리가 무한히 반복 사용 가능하기 때문에 모든 \( n \)이 자동으로 따라옵니다.

이제 학생들에게 정말 깊이 새겨야 할 위험한 함정을 하나 보여드리겠습니다. 귀납법의 두 단계 중 어느 한 곳이라도 부주의하면 명백히 거짓인 명제도 "증명"되는 듯 보인다는 점입니다.

이 함정의 교훈은 분명합니다. 귀납 단계가 "모든 \( k \)에 대해" 성립한다고 주장할 때, 우리가 사용한 모든 보조 사실(여기서는 두 집합의 교집합이 비지 않는다는 사실)이 정말로 모든 \( k \)에서 통하는지 검증해야 합니다. 작은 \( k \)에서 한 번이라도 사슬이 끊기면 전체 증명이 무너집니다.

5.2 강한 귀납법 Strong Induction

일반 귀납법은 \( P(k) \) 하나만으로 \( P(k+1) \)을 끌어내는 방식이었습니다. 그러나 어떤 명제는 한 칸 전이 아니라 지금까지 쌓아온 모든 결과를 동시에 활용해야 다음 칸을 증명할 수 있습니다. 이때 등장하는 게 강한 귀납법(strong induction)입니다. 이름이 거창하지만 사실은 가설을 더 풍부하게 사용해도 된다는 허락일 뿐이에요.

일반 귀납법과의 차이를 다시 강조하자면, 귀납 가설로 사용할 수 있는 정보의 폭이 다릅니다. 일반 귀납법은 직전 한 칸 \( P(k) \)만 손에 쥐고 \( P(k+1) \)을 만들지만, 강한 귀납법은 \( P(0) \)부터 \( P(k) \)까지 전부 손에 쥐고 \( P(k+1) \)을 만듭니다. 무기고가 더 빵빵해진 셈이죠. 그래서 "더 강한" 귀납법이라고 부릅니다. 도미노 비유로는, 다음 도미노를 쓰러뜨릴 때 단지 직전 한 개의 도미노가 부딪힌 충격만이 아니라, 지금까지 쓰러진 모든 도미노가 만들어낸 누적 효과를 활용해도 된다는 뜻입니다.

강한 귀납법이 진가를 발휘하는 대표적인 예가 바로 정수론의 출발점, 소인수분해 존재성입니다.

여기서 결정적인 점은, \( P(k+1) \)을 증명하기 위해 우리가 \( P(k) \)가 아니라 \( P(a) \)와 \( P(b) \)를 가져다 썼다는 사실입니다. \( a \)와 \( b \)는 \( k+1 \)보다 작은 어떤 값일 뿐, 정확히 \( k \)는 아닙니다. 일반 귀납법에서는 직전 한 칸의 결과만 사용 가능하므로 이런 식의 증명을 곧장 쓰기가 어색하지만, 강한 귀납법에서는 자연스럽습니다.

한 가지 더 강조할 점이 있습니다. 강한 귀납법과 일반 귀납법은 결국 같은 결론을 증명할 수 있다는 의미에서 동치입니다. 강한 귀납법으로 증명되는 모든 명제는 일반 귀납법으로도 증명할 수 있고, 그 반대도 마찬가지입니다. 다만 강한 귀납법으로 쓰면 증명이 자연스럽고 깔끔해지는 경우가 많을 뿐입니다.

실전에서는 "이 문제는 일반 귀납이냐 강한 귀납이냐"를 너무 고민하지 말고, 증명 도중 \( k+1 \) 이전의 어떤 값을 가져다 쓰고 싶어지는지를 보고 자연스럽게 강한 귀납을 쓰면 됩니다. 컴퓨터과학에서 분할정복 알고리즘의 정당성 증명, 재귀 호출의 종료 증명, 자료구조의 불변식 증명 같은 데서 강한 귀납법이 거의 표준적으로 등장합니다.

5.3 강귀납 vs 일반 귀납 vs 정렬원리 Strong Induction vs. Induction vs. Well Ordering

4장에서 우리는 정렬원리(Well Ordering Principle)를 만났습니다. 다시 적어두면 다음과 같습니다.

그리고 이번 챕터에서 일반 귀납법과 강한 귀납법을 만났습니다. 놀랍게도 이 셋은 서로 동치입니다. 즉 셋 중 어느 하나라도 자연수 체계의 공리로 받아들이면 나머지 둘이 따라옵니다. "다른 모자를 쓴 같은 사람"이라고 부를 만합니다.

증명의 큰 그림을 먼저 보고 갑시다. 서로 동치임을 보이려면 일반적으로 셋을 한 사이클로 잇는 함의를 보입니다. 즉

   ┌─── (WO) ───┐
   │            │
   ▼            │
  (SI)          │
   │            │
   ▼            │
   (I) ─────────┘
    

방향으로 \( (WO) \implies (SI) \implies (I) \implies (WO) \)를 보이면, 어느 둘 사이의 함의도 사이클을 한 바퀴 돌아 얻을 수 있습니다.

이 사이클이 보여주는 바는 강력합니다. 자연수 위의 명제를 증명할 때 어떤 도구를 고를지는 사실 스타일의 문제이지 능력의 문제가 아닙니다. 정렬원리로 풀리는 모든 문제는 일반 귀납법으로도 풀 수 있고, 강한 귀납법으로 풀리는 모든 문제는 정렬원리로도 풀 수 있습니다. 다만 어떤 문제는 한쪽 옷이 더 잘 맞을 뿐이에요.

마지막으로 한 가지 직관을 덧붙이고 싶습니다. 자연수가 "잘 정렬된" 집합이라는 사실 — 즉 비어 있지 않은 어떤 부분집합도 반드시 가장 작은 원소를 가진다는 사실 — 은 자연수 체계의 가장 본질적인 성질 중 하나입니다. 도미노가 줄지어 있다는 그림과, 부분집합에 항상 출발점이 있다는 그림은 결국 같은 그림의 두 얼굴입니다. 한쪽은 "처음을 미는 손가락"의 관점이고, 다른 한쪽은 "가장 처음에 있는 도미노"의 관점입니다. 우리가 원리 셋을 자유자재로 오갈 수 있게 되는 순간, 이 두 얼굴이 하나의 얼굴로 보이기 시작합니다.

이번 챕터의 도구들은 앞으로 그래프 이론, 알고리즘, 수론, 형식언어 어디에서나 다시 만날 겁니다. 한 번에 다 익숙해지지 않더라도, 새 단원에서 귀납을 다시 마주칠 때마다 이 챕터로 돌아와 도미노와 정렬, 그리고 "유한한 손가락질로 무한을 다루는 마법"을 떠올려보길 권합니다.

6.1 상태와 전이 States and Transitions

일상적인 비유부터 시작해 봅시다. 신호등은 빨강, 노랑, 초록 세 가지 "상태"를 갖고, 일정한 규칙에 따라 한 색에서 다음 색으로 바뀝니다. 자판기는 동전을 넣은 만큼의 "잔고 상태"를 기억하고, 버튼을 누르거나 동전을 더 넣을 때마다 상태가 변합니다. 이런 시스템들의 공통점은 (1) 가능한 상태들의 집합이 명확하고, (2) 한 상태에서 다른 상태로 가는 규칙이 정해져 있다는 점이에요. 우리가 다루는 알고리즘이나 프로그램도 본질적으로 똑같습니다.

전이를 함수로 보지 않고 관계로 정의한 이유는, 같은 상태에서 여러 다음 상태로 갈 수 있는 비결정적(nondeterministic) 시스템도 다루기 위해서예요. 만약 모든 \( q \)에 대해 \( q \to q' \)인 \( q' \)가 정확히 하나뿐이면, 이를 결정적(deterministic) 상태 기계라 부릅니다.

그래프로 그리면 직관이 확 살아나요. 각 상태를 노드로, 전이를 화살표로 표현하면 상태 기계는 방향 그래프가 됩니다. 시작 상태를 진하게 표시하고, 거기서부터 화살표를 따라 갈 수 있는 모든 노드들이 도달 가능한 상태들의 집합이지요.

프로그램을 상태 기계로 보는 시각의 강력함은, "변수들의 현재 값"이라는 추상적 개념을 "상태"라는 수학적 대상으로 끌어올린다는 데 있습니다. 일단 이렇게 모델링하고 나면, 우리는 프로그램의 실행을 그래프 위의 산책으로 바꿔 분석할 수 있어요.

6.2 불변량 원리 The Invariant Principle

상태 기계가 만들 수 있는 도달 가능한 상태들의 집합은 보통 어마어마하게 큽니다. 모든 상태를 일일이 검사해서 "이 시스템은 절대 나쁜 상태에 빠지지 않는다"고 말할 수는 없죠. 그러면 어떻게 해야 할까요? 답은 5장에서 배운 귀납을 한 번 더 변주하는 데 있습니다. 바로 불변량(invariant)이라는 아이디어예요.

형식만 보면 5장의 수학적 귀납과 거의 똑같죠? "기저: 시작 상태에서 성립한다", "귀납 단계: 한 걸음 가도 보존된다." 차이는 자연수 위가 아니라 상태 기계의 실행 위에서 귀납을 한다는 점뿐이에요. 그래서 불변량 원리를 실행 귀납(induction on executions)이라고도 부릅니다.

이 예제의 매력은, 무한히 많은 가능한 경로를 일일이 따져보지 않고도 단 한 줄의 색깔 불변량으로 결론을 내렸다는 점이에요. 좋은 불변량을 찾는 것이 곧 좋은 증명을 찾는 것입니다.

6.3 부분 정확성과 종료 Partial Correctness and Termination

알고리즘이 "옳다"는 말에는 사실 두 가지 약속이 들어 있습니다. 첫째, 끝날 때 답이 맞아야 한다(부분 정확성, partial correctness). 둘째, 무한히 돌지 않고 언젠가는 끝나야 한다(종료성, termination). 둘은 별개의 문제예요. 영원히 도는 알고리즘은 답을 절대 틀리지 않을 수 있고(왜냐하면 답을 절대 안 내놓으니까), 빨리 끝나는 알고리즘이 엉뚱한 답을 줄 수도 있죠. 그래서 두 가지를 따로 증명합니다.

부분 정확성은 6.2의 불변량 원리로 증명합니다. "지금까지 계산한 값과 입력 사이에 어떤 관계가 항상 성립한다"는 불변량을 잡고, 이 불변량이 종료 상태에서 정답을 함의하도록 만들면 끝이에요. 종료성은 새 도구가 필요한데, 이름은 variant입니다.

def fast_pow(a, n):
    r = 1
    x = a
    k = n
    while k > 0:
        if k % 2 == 1:
            r = r * x
        x = x * x
        k = k // 2
    return r

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

이 두 예제에서 강조하고 싶은 건, "복잡한 코드를 한 줄씩 따라가며 머리로 시뮬레이션"하지 않는다는 점이에요. 우리는 한 줄짜리 수학적 성질 두 개(invariant + variant)를 잡고 그게 보존되는지만 검사했습니다. 코드가 길어져도 같은 원칙이 그대로 작동하는 게 이 방법의 위력입니다.

6.4 안정 결혼 문제 The Stable Marriage Problem

이제 지금까지 배운 도구를 진짜 알고리즘에 적용해 봅시다. 무대는 다소 낭만적이지만 정작 수학은 차갑고 정확해요. \( n \)명의 남자와 \( n \)명의 여자가 있고, 각자가 모든 이성을 자기 마음대로 1등부터 \( n \)등까지 줄을 세워 둔 선호 순위를 갖고 있습니다. 우리의 임무는 \( n \)쌍의 결혼을 짝지어 주는 것. 단, 결과가 "안정적"이어야 해요. 어떤 의미에서?

도주 쌍이 있다는 건 두 사람이 동시에 "지금 내 짝보다 너랑이 낫겠다"고 생각한다는 뜻이에요. 그러면 이 둘은 각자의 현재 짝을 버리고 서로에게 도망갈 동기가 충분합니다. 안정 매칭이란 그런 일이 절대 일어나지 않는 매칭이지요. 인기 비유로 말하면 아무도 환승 결혼을 시도할 이유가 없는 상태예요.

두 가지 자연스러운 질문이 떠오릅니다. (1) 어떤 선호 순위가 주어지든 안정 매칭이 항상 존재할까? (2) 존재한다면, 효율적으로 찾을 수 있을까? 둘 다 답은 "예"이고, 그 답을 동시에 주는 것이 1962년 게일과 섀플리(Gale & Shapley)의 알고리즘입니다.

약간 일방적이고 구식인 설정이지만(실제로 게일·섀플리가 1962년에 쓴 그대로의 비유입니다), 알고리즘의 수학적 성질을 분석하기에는 깔끔해요. 우선 진짜로 끝나긴 하는지부터 확인합시다.

다음으로, 끝났을 때 진짜로 모두가 짝지어지는지를 확인해야 합니다.

이건 알고리즘 정의에서 바로 따라옵니다. 새 청혼자로 갈아탈 때는 무조건 더 마음에 드는 쪽으로만 갈아타니까요. 이 단조성에서 또 하나가 따라 나옵니다.

이제 가장 중요한 안정성을 증명할 차례예요. 핵심 아이디어는 매혹적일 만큼 단순합니다.

그림으로 정리하면 이래요. \( B \)는 자기 선호 순위의 꼭대기에서부터 차례로 청혼하니까 \( G' \)와 짝이 됐다는 건 \( G \)에게 이미 거절당한 적이 있다는 증거고, 거절당했다는 건 \( G \)에게 그때 더 좋은 사람이 있었다는 증거고, 보류는 단조 증가하니까 종료 시점에는 더 좋아졌으면 좋아졌지 나빠질 수 없다. 한마디로 청혼하는 쪽이 위에서 아래로 내려간다는 사실과, 받는 쪽이 받은 사람들 사이에서 위로 올라간다는 사실이 만나는 지점에서 도주 쌍은 살 자리가 없습니다.

안정성과 종료성에 더해, Gale-Shapley 알고리즘에는 한 가지 흥미로운 성질이 더 있어요.

증명의 핵심 아이디어만 짚을게요. 어떤 남자 \( B \)가 자기의 "이론상 가능한 최고 짝" \( G \)를 못 받았다고 가정해 봅시다. 즉 알고리즘 진행 중 \( G \)가 \( B \)를 거절하는 첫 번째 순간이 있어요. 그 순간 \( G \)는 \( B \)보다 더 좋은 누군가 \( B^* \)를 보류로 잡고 있었던 거고, 그러면 \( B^* \)도 그 시점까지 자기 선호 순위 위쪽에서 거절당하지 않은 채 \( G \)에게 도달한 거예요. 이 \( B^* \)에게도 \( G \)가 안정 매칭 가능한 짝이라는 가정을 풀어 보면, \( B^* \)의 "이론상 가능한 최고 짝"보다 \( G \)가 위에 있다는 결론이 나오고, 그것을 안정 매칭의 정의와 결합하면 도주 쌍이 만들어져 모순. 즉 "거절당하는 첫 번째 남자"가 존재할 수 없습니다.

이 챕터를 한 줄로 요약하면 이렇게 됩니다. 프로그램은 상태 기계, 옳음의 증명은 불변량, 끝남의 증명은 variant. 도구는 단순하지만 적용 범위는 넓어요. 그리고 그 도구의 뿌리는 결국 5장의 귀납이라는 한 가지 원리입니다. 다음 챕터로 가면 이 도구들이 더 큰 구조 — 그래프와 그 위의 알고리즘 — 에서 어떻게 쓰이는지 보게 될 거예요.

7.1 재귀 정의와 구조적 귀납 Recursive Definitions and Structural Induction

어떤 집합을 정의할 때, 원소 하나하나를 일일이 나열하기보다 "재료 + 조립 규칙"으로 묘사하면 훨씬 깔끔합니다. 자연수 \( \mathbb{N} \) 을 떠올려 보세요. \( 0 \in \mathbb{N} \) 이고, \( n \in \mathbb{N} \) 이면 \( n+1 \in \mathbb{N} \) 이다. 이 두 줄이면 무한히 많은 자연수를 모두 길어 올릴 수 있어요. 이게 재귀 정의의 본질입니다.

"가장 작은 집합"이라는 마지막 조건이 핵심이에요. 이게 없으면 별난 원소를 끼워 넣어도 정의를 만족할 수 있거든요. 이 조건 덕분에 \( R \) 의 모든 원소는 기저에서 시작해서 구성자를 유한 번 적용한 결과로 얻어집니다.

자연수의 귀납법은 기저 \( \{0\} \) 에 구성자 \( n \mapsto n+1 \) 하나뿐인 특수 사례예요. 구조적 귀납은 기저와 구성자가 더 풍부할 뿐, 같은 정신입니다. 재귀로 정의된 집합 위에서 함수를 정의할 때도 같은 틀을 씁니다 — 기저 원소에서 값을 정하고, 구성자에는 "입력값에서 출력값을 만드는 규칙"을 적어 두면 끝.

7.2 균형 괄호 문자열 Strings of Matched Brackets

이제 구체적인 예로 들어가 봅시다. 알파벳 \( \{ \, [\,, \,] \, \} \) 위의 문자열 중에서 "괄호가 잘 짝지어진" 것들의 모임 \( \mathrm{RecMatch} \) 를 정의하고 싶어요. 직관적으로는 [][[]] 같은 건 OK, ][ 같은 건 NO.

예를 들어 \( s = t = \lambda \) 면 \( [\,]\, \lambda = [] \) 가 만들어지고, 거기서 다시 \( [\, []\, ] \, [] = [[]][] \) 같은 문자열이 자라납니다. 이 정의 한 줄로 무한히 많은 균형 문자열이 모두 나오는 게 신기해요.

그런데 같은 집합을 다르게 정의할 수도 있습니다. 다른 책에서는 다음 정의를 만나곤 해요.

"정의가 다른데 같은 집합"이라는 건 모델링에서 흔히 쓰는 트릭이에요. 어떤 정의는 증명에 편하고, 어떤 정의는 알고리즘에 편하니까 상황에 따라 골라 쓸 수 있게 둘이 같다는 사실을 챙겨 두는 거죠.

7.3 비음 정수 위 재귀 함수 Recursive Functions on Nonnegative Integers

\( \mathbb{N} \) 자체가 재귀 데이터 타입이니, 그 위에서 정의되는 함수들도 자연스레 재귀로 적습니다. 가장 단순한 친구는 팩토리얼.

두 번째 줄에 우변에 \( n! \) 이 다시 등장하는 게 재귀의 핵심이에요. "다음 값"을 "이전 값"으로 표현합니다. 피보나치 수열은 직전 두 값을 모두 참조하는 점만 다를 뿐 같은 패턴.

여기서 한 발 더 나가면 아커만 함수가 기다립니다. 정말 묘한 친구예요.

손으로 \( A(2, 2) \) 정도까지 펼쳐 보면 금방 \( A(2,2) = 7 \) 이 나오지만, \( A(4, 2) \) 는 우주 원자 수보다 큰 값입니다. 더 무서운 건 이 함수가 "원시 재귀(primitive recursive)" 의 틀로는 절대 표현되지 않는다는 사실이에요. 즉, 단순 for-loop의 합성으로는 흉내 낼 수 없는, "진짜 재귀"가 필요한 함수의 대표주자입니다.

7.4 산술식 Arithmetic Expressions

"(3 + 4) * 5" 같은 산술식을 컴퓨터가 어떻게 다루는지 들여다봅시다. 문자열로 보면 골치 아프지만, 재귀 데이터 타입으로 보면 단정해요.

이 정의가 실제로 만들어내는 건 우리가 컴파일러 강의에서 보는 추상 구문 트리(AST)예요. 잎(leaf)은 상수와 변수, 내부 노드는 연산자. 식 위의 함수 \( \mathrm{eval}(e, \sigma) \) — 변수 환경 \( \sigma \) 아래에서 식의 값을 매기는 — 도 재귀로 깔끔하게 적힙니다.

트리에 대해 자주 묻는 두 양은 깊이 \( d(e) \) 와 크기 \( s(e) \) 입니다. 각각도 재귀로: \( d(c) = d(x) = 0 \), \( d((e_1 \star e_2)) = 1 + \max(d(e_1), d(e_2)) \); \( s(c) = s(x) = 1 \), \( s((e_1 \star e_2)) = 1 + s(e_1) + s(e_2) \).

구조적 귀납을 적용하면 "이진트리에서 \( s(e) \le 2^{d(e)+1} - 1 \)" 같은 사실을 깔끔히 증명할 수 있어요. AST에서 함수형 인터프리터, 그리고 컴파일러 최적화의 정확성 증명까지 — 모두 이 작은 재귀 정의에서 출발합니다.

7.5 재귀 데이터로 본 게임 Games as a Recursive Data Type

체스나 틱택토 같은 두 사람 결정 게임도 사실은 재귀 데이터 타입의 한 사례예요. "게임 상태"는 곧 그 상태에서 가능한 다음 상태들의 리스트이고, 이게 끝나는 지점은 "승/패/무"가 결정된 단말 상태.

이 위에서 미니맥스 값이 재귀로 정의돼요. 내가 둘 차례면 자식 값들의 \( \max \), 상대가 둘 차례면 \( \min \). 잎에서는 결과 그 자체.

이 정리 덕분에 체스도 "이론적으론 결정 게임"이라는 표현이 가능합니다. 다만 트리가 너무 커서 우리가 모를 뿐이에요. 재귀 정의 + 구조적 귀납이 추상적인 존재성 증명을 얼마나 가볍게 해주는지 보여주는 멋진 예입니다.

7.6 검색 트리 Search Trees

자료구조 강의의 단골인 이진 검색 트리(BST)도 재귀로 정의해 두면 정리/삽입/검색 알고리즘을 매끈하게 다룰 수 있어요.

검색은 한 줄로 적힙니다.

def find(t, x):
    if t is Nil: return False
    if x < t.key: return find(t.left, x)
    if x > t.key: return find(t.right, x)
    return True

삽입도 같은 흐름. 빈 자리를 찾을 때까지 한쪽으로 내려가서 새 노드를 매답니다.

"BST 조건"이라는 작은 불변량 하나가 알고리즘의 정확성을 통째로 보장한다는 점에 주목하세요. 재귀 데이터 타입의 정의 안에 알고리즘 분석의 핵심이 미리 들어가 있는 셈입니다.

7.7 컴퓨터과학에서의 귀납 Induction in Computer Science

마지막으로 한 발 물러서서 큰 그림을 봅시다. 알고리즘이 정확함을 증명하려고 할 때, 우리는 거의 항상 어떤 형태의 귀납을 씁니다.

• 반복문의 정확성은 루프 불변량을 자연수에 대한 귀납으로 증명.
• 재귀 함수의 정확성은 입력 크기 또는 입력의 구조에 대한 구조적 귀납으로.
• 컴파일러/타입시스템의 안정성(soundness)은 프로그램의 추상 구문 트리에 대한 구조적 귀납으로.
• 그래프/트리 알고리즘은 보통 깊이 또는 정점 수에 대한 (강한) 귀납으로.

한 마디로, 자료구조가 재귀로 정의되어 있다면 그 위 알고리즘의 정확성 증명은 그 정의를 그대로 따라가는 구조적 귀납이 됩니다. 자료구조 정의 → 함수 정의 → 정확성 증명, 이 세 단계가 같은 모양으로 펼쳐지는 거예요.

자, 자연수의 귀납이 "더 일반적인 귀납"으로 확장되는 풍경을 한 번 봤어요. 다음 챕터부터는 이 도구를 들고 무한 합, 점근 분석, 그래프 같은 더 큰 무대로 나갑니다. 도구는 같으니 겁먹지 말고 가요.

8.1 무한 기수 Infinite Cardinality

유한 집합이라면 크기 비교는 쉽습니다. 사과 5개와 배 5개는 같은 개수이고, 사과 5개와 배 7개는 배가 더 많죠. 하지만 자연수 \(\mathbb{N} = \{0, 1, 2, 3, \dots\}\)와 짝수 전체 \(2\mathbb{N} = \{0, 2, 4, 6, \dots\}\)는 누가 더 많을까요?

"짝수는 자연수의 절반이니까 자연수가 두 배 많지!" — 이게 직관적인 답이지만, 무한의 세계에서는 직관이 자주 무너집니다. 19세기 칸토어(Cantor)가 제시한 답은 깔끔합니다. 두 집합 사이에 일대일 대응(전단사)이 존재하면 같은 크기다. 짝수와 자연수 사이엔 \(n \mapsto 2n\)이라는 전단사가 있으니, 두 집합은 같은 크기입니다. "전체와 일부가 같은 크기"라는 게 무한의 본질이에요.

유한 집합에서 이 정의는 우리가 아는 "원소 개수"와 정확히 일치합니다. 그리고 이 정의는 무한 집합으로 자연스럽게 확장돼요. 단, 직관과 충돌할 각오는 해야 합니다.

가산무한이라는 건 결국 "원소를 \(a_0, a_1, a_2, \dots\)로 줄세울 수 있다"는 뜻입니다. 자연수와 일대일 대응이라는 건 자연수 인덱스를 붙일 수 있다는 거니까요.

1/1  1/2  1/3  1/4  ...
2/1  2/2  2/3  2/4  ...
3/1  3/2  3/3  3/4  ...
 .    .    .    .
순서: 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, ...
      

여기까지 보면 "어쩌면 모든 무한이 다 같은 크기 아닌가?" 싶죠. 칸토어 본인도 한동안 그렇게 의심했다고 합니다. 그런데 1874년경 그는 충격적인 사실을 발견합니다. 실수 \(\mathbb{R}\)은 자연수와 같은 크기가 아니다. 더 큽니다.

이 기법이 그 유명한 칸토어 대각선 논법(Cantor's diagonal argument)입니다. 표를 만들어놓고 대각선을 골라 그것과 다른 무언가를 만든다는 발상이에요. 이 발상은 다음 절에서 컴퓨터과학을 뒤흔들게 됩니다.

8.2 정지 문제 The Halting Problem

"이 프로그램이 무한 루프에 빠지나, 아니면 언젠가 끝나나?" — 코드를 짜본 사람이라면 누구나 떠올린 질문일 겁니다. 이걸 자동으로 판정해주는 도구가 있다면 디버깅이 얼마나 편해질까요. 컴파일러가 무한 루프를 미리 잡아주면 좋잖아요. 그런데 1936년 앨런 튜링(Alan Turing)이 결정적인 답을 줬습니다. 그런 도구는 원리적으로 만들 수 없다.

여기서 "프로그램"은 임의의 알고리즘을 의미합니다. 파이썬, C, 튜링 기계, 람다 계산 — 표현 방식이 무엇이든 상관없어요. 핵심은 다음 함수를 계산하는 알고리즘이 존재하느냐는 것입니다:

"그냥 돌려보면 되지 않나?" 싶지만, 무한 루프인 경우엔 영원히 결과를 알 수 없습니다. 우리가 원하는 건 유한 시간 안에 항상 정확한 답을 내는 알고리즘이에요.

def Trouble(P):
    if Halt(P, P) == True:
        while True:
            pass        # 일부러 무한 루프
    else:
        return          # 그냥 정지

이 증명은 정확히 칸토어의 대각선 논법과 같은 골격입니다. 칸토어는 "모든 실수의 목록"을 가정하고, 대각선의 \(i\)번째 자리를 뒤집어서 목록에 없는 실수를 만들었어요. 튜링은 "모든 프로그램에 대한 정지 판정"을 가정하고, "자기 자신에 대한 답"을 뒤집은 \(\text{Trouble}\)을 만들었습니다. 둘 다 "표의 대각선을 부정하면 모순"이라는 같은 패턴이에요.

실용적으로 보면 슬픈 결과지만, 한편으론 컴파일러 작성자에게 면죄부이기도 합니다. "왜 무한 루프 못 잡아줘?"에 대해 "그건 원리적으로 불가능합니다"라고 답할 수 있게 됐으니까요.

8.3 집합의 논리 The Logic of Sets

지금까지 \(|A| = |B|\)는 전단사로, \(|A| \le |B|\)는 단사로 정의했습니다. 그런데 정말 이 정의가 우리의 직관처럼 작동할까요? 예를 들어 "\(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\)다"라는 명제는 당연해 보이지만, 무한 집합에선 증명이 필요합니다. 이게 바로 슈뢰더-베른슈타인 정리예요.

증명은 여기선 생략하지만, 핵심 아이디어는 이렇습니다. 각 원소의 "출신 사슬"을 거꾸로 거슬러 올라가서, 사슬이 \(A\)에서 시작했는지 \(B\)에서 시작했는지에 따라 \(f\)를 쓸지 \(g^{-1}\)을 쓸지 골라 \(h\)를 정의합니다. 손으로 그림 그려보면 의외로 깔끔해요.

이제 한 단계 더 나아가, "주어진 집합보다 더 큰 집합을 항상 만들 수 있는가?"라는 질문을 던져봅시다. 답은 그렇습니다 — 그것도 매우 자연스러운 방법으로요. 멱집합을 쓰면 됩니다.

또 대각선 논법이에요! \(D\)를 정의할 때 "\(a \in f(a)\)라는 진술을 부정"한 게 본질적으로 대각선을 뒤집은 것입니다. 칸토어 대각선 논법, 정지 문제, 칸토어 정리 — 모두 같은 도구로 같은 형태의 결론을 끌어냅니다.

이 정리는 무한의 위계가 끝없이 올라간다는 뜻이기도 합니다. \(\mathbb{N}\)보다 큰 \(\mathcal{P}(\mathbb{N})\), 그보다 큰 \(\mathcal{P}(\mathcal{P}(\mathbb{N}))\), \(\dots\) 무한히 많은 "다른 크기의 무한"이 존재해요. 칸토어 본인이 이걸 발견하고 한참 어지러워했다고 합니다. 그럴 만 하죠.

참고로 이 모든 논의가 깔끔하게 이뤄지려면 "집합"이 무엇인지를 엄밀하게 정의해야 합니다. 현대 수학은 ZFC(Zermelo-Fraenkel + 선택공리)라는 공리계 위에서 작동해요. 9개 정도의 공리들이 "이런 집합은 만들 수 있다", "이렇게 모으면 또 집합이다"를 정해놓은 것입니다. 우리가 쓴 모든 집합론 기법 — 합집합, 교집합, 멱집합, 함수, 카르테시안 곱 — 이 거기서 파생됩니다.

8.4 이게 다 진짜 작동하는가? Does All This Really Work?

여기까지 따라오셨다면 한 번쯤 이런 의심이 드실 거예요. "임의의 조건으로 자유롭게 집합을 모을 수 있다면, 뭔가 위험한 일이 일어나지 않을까?" 정확한 직감입니다. 1901년 버트런드 러셀(Bertrand Russell)이 그 위험을 정확히 짚었어요.

이건 또 대각선 논법의 변형이에요(이쯤 되면 패턴이 보이죠). 그리고 이 역설은 19세기 말 프레게가 막 완성하려던 "조건만 있으면 어떤 집합이든 만들어진다"는 소박한 집합론을 무너뜨립니다. 프레게는 책이 인쇄소에 있을 때 러셀의 편지를 받고 충격을 받았다는 일화가 유명해요.

해법은 "어떤 조건이든 집합을 만든다"를 포기하는 것입니다. 대신 더 신중하게, 안전한 방식으로만 집합을 만들 수 있도록 공리를 깔아요. 그게 ZFC의 핵심 아이디어입니다. 예를 들어 "이미 있는 집합 \(A\) 안에서 조건 \(\varphi\)를 만족하는 원소들만 모은다"는 분리 공리만 허용하면 \(R = \{S : S \notin S\}\) 같은 정체불명의 모음은 원천 차단됩니다. \(R\)을 만들려면 "모든 집합"이라는 모집단이 있어야 하는데, ZFC는 그것을 집합으로 인정하지 않거든요.

그럼 ZFC 자체가 무모순인지는 어떻게 아나요? 슬프게도, 안에서 증명할 수 없습니다. 1931년 쿠르트 괴델(Kurt Gödel)의 불완전성 정리가 이걸 보여줬어요.

이 정리는 "수학 전체를 단 하나의 완전한 공리계로 환원하자"는 힐베르트의 꿈을 영구히 종결시켰습니다. 흥미롭게도 괴델의 증명도 핵심에 자기참조와 대각선 기법이 있어요. "이 명제는 증명 불가능하다"라는 명제를 산술 안에서 코딩한 다음, 정지 문제 비슷한 모순 구조를 끌어냅니다.

또 하나, 앞서 잠깐 언급한 연속체 가설 — "\(\aleph_0 < \kappa < \mathfrak{c}\)인 무한 기수 \(\kappa\)는 없다" — 도 운명이 비슷합니다. 괴델(1940)과 코언(1963)의 결과를 합치면, 연속체 가설은 ZFC로 증명할 수도 반증할 수도 없습니다. 즉 ZFC와 독립이에요. "참인지 거짓인지 정해지지 않은 명제가 있다"는 게 아니라, "ZFC가 결정해주지 않는 명제가 있다"는 거죠. 누군가는 이걸 두고 "수학은 우리가 생각한 것보다 자유롭다"고 말하기도 합니다.

이 챕터를 한 줄로 요약하면 이렇습니다. 무한은 한 종류가 아니고, 어떤 무한은 다른 무한보다 진짜로 크다. 그 사실을 증명한 도구(대각선 논법) 하나로 우리는 비가산성, 정지 문제의 결정 불가능성, 멱집합의 위계, 그리고 러셀과 괴델의 역설까지 한 번에 꿰뚫었습니다. 한 기법이 이렇게 멀리 데려다주는 경우는 흔치 않아요. 마음이 살짝 흔들렸다면, 정상입니다.

9.1 가분성 Divisibility

정수의 세계에서 가장 먼저 익혀야 할 동사는 "나눈다"입니다. 다만 우리가 보통 쓰는 "나누기"와 달리, 정수론에서는 결과가 정수로 딱 맞아떨어지는 경우만 의미가 있어요. 예를 들어 \( 6 = 2 \cdot 3 \)이니 \( 2 \)는 \( 6 \)을 나누지만, \( 7 \)은 \( 6 \)을 나누지 못합니다.

몇 가지 즉시 따라오는 성질이 있습니다. \( a \mid b \)이고 \( a \mid c \)이면 어떤 정수 \( s, t \)에 대해서도 \( a \mid (sb + tc) \)예요. 즉 약수는 정수계수 선형결합 안에서도 살아남습니다. 또 \( 0 \)은 모든 정수를 약수로 가지지만 자기 자신만 \( 0 \)을 나눌 수 있는 특수한 값이고, \( 1 \)과 \( -1 \)은 모든 정수의 약수예요.

이 정리는 너무 당연해 보여서 처음에는 "이걸 왜 정리라고 부르지?" 싶지만, 사실 \( \gcd \)부터 모듈러 산술, 다항식 나눗셈까지 정수론의 거의 모든 알고리즘이 이 한 문장 위에 서 있어요. 나머지를 \( r = a \bmod n \)으로 표기합니다.

9.2 최대공약수 The Greatest Common Divisor

두 정수의 공통된 약수 중 가장 큰 것을 최대공약수라 부르고 \( \gcd(a,b) \)로 씁니다. 초등학교에서는 약수를 모조리 나열해서 비교했지만, 큰 수에서는 이 방법이 끔찍하게 비효율적이에요. 다행히 기원전 300년경에 유클리드가 너무나 우아한 알고리즘을 남겼습니다.

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

그런데 유클리드 알고리즘은 단지 값만 알려주는 게 아니라, 거꾸로 따라가면 \( \gcd \)를 \( a \)와 \( b \)의 정수계수 결합으로 쓰는 방법까지 줍니다. 이게 베주의 정리예요.

예제로 위의 \( \gcd(252, 198) = 18 \)을 거꾸로 풀면 \( 18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 \), 다시 \( 54 = 252 - 198 \)이므로 \( 18 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198 \). 즉 \( x = 4, y = -5 \)입니다. 이 \( x, y \)는 9.9에서 곱셈 역원을 만들 때 결정적으로 쓰이니 잘 기억해 두세요.

9.3 소수의 신비 Prime Mysteries

1보다 큰 정수 \( p \)가 \( 1 \)과 자기 자신 외의 양의 약수를 갖지 않으면 소수(prime)라고 부릅니다. 그렇지 않은 정수는 합성수(composite)예요. 사람들은 2300년 넘게 소수를 들여다봤는데도 여전히 풀지 못한 문제가 산처럼 쌓여 있습니다.

"그럼 소수가 얼마나 자주 나오나?"가 다음 질문이에요. \( \pi(n) \)을 \( n \) 이하의 소수 개수라고 하면, 가우스가 십대 시절에 추측하고 1896년에 증명된 결과가 다음과 같습니다.

한편 풀리지 않은 거대 추측들도 있어요. 쌍둥이 소수 추측은 \( p \)와 \( p+2 \)가 동시에 소수인 쌍이 무한히 많다고 주장합니다. 골드바흐 추측은 \( 4 \) 이상의 짝수는 모두 두 소수의 합으로 쓸 수 있다는 250년 묵은 문제예요. 컴퓨터로 \( 4 \cdot 10^{18} \)까지는 확인됐지만, 증명은 아직 없습니다.

9.4 산술 기본정리 The Fundamental Theorem of Arithmetic

"모든 정수는 소수의 곱"이라는 사실은 너무 익숙해서 정리라는 자각조차 못하기 쉬워요. 그런데 정말 따져 보면, 이 분해가 항상 가능하다는 것과 게다가 유일하다는 것은 그 자체로 묵직한 정리입니다.

겉보기엔 당연하지만, 이 유일성은 사실 일반적인 수 체계에서 깨질 수 있어요. 예를 들어 \( \mathbb{Z}[\sqrt{-5}] \)에서는 \( 6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) \)처럼 분해가 두 가지 나옵니다. 이걸 다루려고 19세기 수학자들이 "이데알(ideal)" 개념을 발명했죠. 정수에서 유일성이 성립한다는 건 결코 공짜가 아니에요.

9.5 앨런 튜링 Alan Turing

앨런 튜링(Alan Turing, 1912-1954)은 24살에 "계산 가능 함수"의 보편 모델인 튜링 기계를 정의해 컴퓨터 과학의 토대를 놓은 사람이에요. 제2차 세계대전 동안 영국 블레츨리 파크에서 독일군의 에니그마(Enigma) 암호를 깨뜨리는 데 결정적 기여를 했고, 그 덕에 전쟁이 수년 앞당겨 끝났다고 평가됩니다. 전후에는 동성애를 이유로 영국 정부에 의해 화학적 거세형을 받았고 1954년 청산가리 묻은 사과를 베어 문 채 발견됐어요(자살로 추정). 2009년 영국 총리, 2013년 여왕의 공식 사면이 있었지만 너무 늦었죠. 이 챕터에서 우리가 보게 될 모듈러 산술과 RSA는 모두 튜링이 평생 매달렸던 "암호 깨기"의 직계 후손입니다.

9.6 모듈러 산술 Modular Arithmetic

시계는 \( 12 \)를 넘으면 다시 \( 1 \)로 돌아갑니다. 13시는 1시와 "같은 자리"예요. 이 직관을 정수 전체에 적용한 게 모듈러 산술입니다.

같은 말로, \( a \)와 \( b \)를 \( n \)으로 나눈 나머지가 같다는 뜻이에요. 이 관계는 정수 위의 동치관계입니다. 반사성·대칭성·추이성을 모두 만족하니까요. 동치관계가 있으면 동치류로 분할이 따라옵니다. \( n = 5 \)일 때 정수는 다섯 개의 동치류로 쪼개져요: \( [0], [1], [2], [3], [4] \). 각 동치류는 \( \{ \dots, -5, 0, 5, 10, \dots \} \) 같은 무한집합이에요.

모듈러 산술이 강력한 진짜 이유는 합과 곱이 동치류 위에서 잘 정의된다는 점입니다.

증명은 간단합니다. \( a - a' \)와 \( b - b' \)가 \( n \)의 배수이면 \( (a+b) - (a'+b') \)와 \( ab - a'b' = a(b-b') + b'(a-a') \)도 모두 \( n \)의 배수예요. 그래서 우리는 큰 수를 다룰 때 거추장스럽게 끌고 다닐 필요 없이, 매 단계마다 \( \bmod n \)으로 나머지를 취해도 결과가 같다는 자유를 얻습니다.

9.7 나머지 산술 Remainder Arithmetic

합동을 동치관계로 보고 동치류 자체를 원소로 삼는 새 집합을 만들 수 있어요. 이 집합을 \[ \mathbb{Z}_n = \{0, 1, 2, \dots, n-1\} \] 라고 쓰고, 각 원소를 "그 동치류의 대표 나머지"로 봅니다.

\( \mathbb{Z}_n \)에서의 덧셈과 곱셈은 정수의 덧셈·곱셈을 한 뒤 \( n \)으로 나머지를 취하는 것으로 정의해요. 9.6에서 이게 잘 정의된다는 걸 봤습니다. 결과적으로 \( \mathbb{Z}_n \)은 가환환(commutative ring)이 됩니다. 곧, 결합법칙·교환법칙·분배법칙이 모두 성립하고, \( 0 \)과 \( 1 \)이라는 항등원을 갖습니다.

한편 \( \mathbb{Z}_6 \)에서는 사정이 다릅니다. \( 2 \cdot 3 = 6 = 0 \)이거든요. 두 0이 아닌 원소를 곱했는데 0이 나오는 일이 벌어집니다. 이런 \( \mathbb{Z}_n \)을 "영인자(zero divisor)가 있다"고 말해요. \( n \)이 합성수일 때 일어나는 현상이고, 이게 9.9에서 나올 곱셈 역원의 존재 조건과 직결됩니다.

9.8 튜링의 코드 v2.0 Turing's Code Version 2.0

아주 단순한 암호 시나리오를 그려 봅시다. 앨리스가 밥에게 메시지 \( m \)(어떤 \( \mathbb{Z}_p \) 안의 수, \( p \)는 큰 소수)을 보내려고 합니다. 둘은 사전에 비밀키 \( k \)를 공유했고, 앨리스는 \[ c = m \cdot k \pmod{p} \] 로 암호화해서 \( c \)를 보냅니다. 밥은 \( k \)의 곱셈 역원 \( k^{-1} \)을 알고 있으니 \[ m = c \cdot k^{-1} \pmod{p} \] 로 복호화하면 끝이에요. 깔끔해 보이죠?

그런데 이 방식엔 치명적 약점이 있습니다. 공격자 이브가 메시지 두 개 \( c_1 = m_1 k \), \( c_2 = m_2 k \)를 가로챘다고 합시다. 이브는 \( c_1 \cdot c_2^{-1} = m_1 \cdot m_2^{-1} \pmod{p} \)를 계산할 수 있어요. 키 \( k \)가 깨끗이 사라집니다. 이브가 만약 메시지 한 개의 평문을 우연히 알게 된다면 — 가령 인사말 "안녕"이 거의 매번 들어간다면 — 다른 모든 메시지의 평문도 같이 무너져요.

9.9 곱셈 역원과 소거 Multiplicative Inverses and Cancelling

\( \mathbb{Z}_n \)에서 \( a \)의 곱셈 역원이란 \( a \cdot a^{-1} \equiv 1 \pmod{n} \)을 만족하는 원소입니다. 어떤 \( a \)는 역원을 가지고 어떤 건 못 가져요. 그 기준이 정확히 무엇일까요?

특히 \( n = p \)가 소수면 \( 1, 2, \dots, p-1 \) 모두가 \( p \)와 서로소이므로 모두 역원을 가져요. 그래서 \( \mathbb{Z}_p \)는 단지 환을 넘어 체(field)가 됩니다.

역원의 존재는 곧 "소거(cancellation)"의 가능 여부를 결정합니다. \( ab \equiv ac \pmod n \)에서 \( a \)를 양쪽에서 지우려면 \( a^{-1} \)을 곱해야 하는데, 그러려면 \( \gcd(a, n) = 1 \)이 필수예요. 이 조건이 없으면 일반적으로 소거가 안 됩니다. 예를 들어 \( \mathbb{Z}_6 \)에서 \( 2 \cdot 1 \equiv 2 \cdot 4 \pmod 6 \)이지만 \( 1 \not\equiv 4 \).

9.10 오일러 정리 Euler's Theorem

\( \mathbb{Z}_n \)에서 역원을 가지는 원소의 개수를 세는 함수가 오일러의 토션트(totient) \( \varphi(n) \)입니다.

몇 가지 사실. \( p \)가 소수면 \( 1, 2, \dots, p-1 \)이 모두 \( p \)와 서로소이므로 \( \varphi(p) = p - 1 \). \( p, q \)가 서로 다른 소수면 곱셈성을 이용해 \[ \varphi(pq) = (p-1)(q-1). \] 이 한 줄이 RSA의 심장이에요.

특수한 경우로 \( n = p \)(소수)면 \( \varphi(p) = p-1 \)이라 다음이 즉시 따라와요.

9.11 RSA 공개키 암호 RSA Public Key Encryption

이제 모든 재료가 모였어요. RSA(Rivest-Shamir-Adleman, 1977)는 인류 역사상 가장 널리 쓰인 공개키 암호이자, 정수론이 일상에 직접 들어온 사건입니다. 핵심은 "인수분해는 어렵고, 멱승은 쉽다"는 비대칭성이에요.

암호화·복호화는 단순한 멱승이에요. 평문 \( m \in \mathbb{Z}_n \)에 대해 \[ \text{암호화: } c = m^e \bmod n, \quad \text{복호화: } m = c^d \bmod n. \]

왜 안전할까요? 이브가 공개키 \( (n, e) \)와 \( c \)를 봐도 \( m \)을 복원하려면 \( d \)가 필요하고, \( d \)를 알려면 \( \varphi(n) \)이 필요한데, \( \varphi(n) \)을 알려면 \( n \)을 \( pq \)로 인수분해해야 합니다. 그런데 1024비트, 2048비트짜리 \( n \)을 인수분해하는 알려진 알고리즘은 모두 너무 느려요. 슈퍼컴퓨터로도 수십억 년이 걸린다고 추정됩니다.

9.12 SAT은 무슨 상관? What has SAT got to do with it?

RSA의 안전은 "큰 정수의 인수분해가 어렵다"는 가정 위에 있어요. 그런데 진짜로 어렵다는 게 증명됐을까요? 슬프게도 답은 "아직 모름"입니다. 인수분해 문제 FACTOR는 NP에 속해요. 검증은 쉬우니까요. 어떤 \( n \)과 후보 \( (p, q) \)를 받으면 곱셈 한 번으로 \( pq = n \)인지 확인 가능합니다.

여기서 4장의 SAT가 등장합니다. SAT(논리식 충족 가능성)은 NP-완전 문제예요. 만약 \( P = NP \)가 증명된다면, SAT를 다항시간에 풀 수 있고, 그러면 NP에 있는 모든 문제(인수분해 포함)도 다항시간에 풀려서 RSA가 무너집니다. 반대로 \( P \neq NP \)가 증명되어도, 그것만으로는 인수분해가 어렵다는 결론이 자동으로 따라오진 않아요. 인수분해는 NP-완전성이 알려져 있지 않은 "중간 난이도" 문제로 분류되거든요.

요약하면, 우리가 매일 누리는 인터넷의 보안은 "인수분해는 어렵고 멱승은 쉽다"는 한 줄의 비대칭성에 걸려 있고, 그 비대칭성의 정확한 이유는 컴퓨터 과학에서 가장 큰 미해결 문제인 \( P \) vs \( NP \)와 깊이 얽혀 있습니다. 가장 순수하다던 정수론이 가장 실용적인 분야로 변신한 이야기, 이것이 이 챕터의 진짜 결말이에요.

10.1 정점 차수 Vertex Degrees

유향 그래프(digraph)는 정점 집합 \(V\)와 정점들의 순서쌍을 원소로 갖는 간선 집합 \(E \subseteq V \times V\) 로 이루어진 쌍 \(G = (V, E)\)입니다. 무향 그래프와 달리 \((u, v)\)와 \((v, u)\)는 서로 다른 간선이에요. 화살표 \(u \to v\)는 "\(u\)에서 \(v\)로 가는 방향이 있다"는 뜻이고, 거꾸로는 가지 못할 수도 있습니다. 트위터의 팔로우 관계가 정확히 이런 구조죠. 내가 누군가를 팔로우한다고 그 사람이 나를 팔로우하는 건 아니니까요.

무향 그래프에서는 모든 차수의 합이 간선 수의 두 배라는 악수 정리가 있었죠. 유향 그래프에서는 한 간선이 한쪽엔 나가는 차수 1, 다른 쪽엔 들어오는 차수 1로만 기여하므로 다음이 성립합니다.

10.2 워크와 경로 Walks and Paths

그래프 위에서 화살표를 따라 정점들을 옮겨다니는 행위를 형식화합시다. 길이 \(k\)인 워크(walk)는 정점-간선 교대 수열 \(v_0, e_1, v_1, e_2, \dots, e_k, v_k\)이고, 각 \(e_i\)가 \(v_{i-1} \to v_i\)인 간선이어야 합니다. 정점이나 간선이 반복되어도 괜찮아요. 같은 모서리를 두 번 지나지 않으면 트레일(trail), 같은 정점을 두 번 지나지 않으면 단순 경로(simple path)라고 부릅니다.

한국어 학생들이 자주 헷갈리는 지점이 하나 있어요. 경로의 길이는 정점 수가 아니라 간선 수입니다. 정점 \(a, b, c\)를 지나는 경로 \(a \to b \to c\)의 길이는 2이지 3이 아닙니다. 사람을 셀 때는 두 명이 손을 잡으면 한 줄, 세 명이면 두 줄이듯, 간선이 한 칸이라고 생각하면 편해요.

10.3 인접 행렬 Adjacency Matrices

유향 그래프를 컴퓨터에 저장하는 가장 깔끔한 방법은 행렬을 쓰는 것입니다. 정점이 \(n\)개일 때, \(n \times n\) 행렬 \(A\)를 다음과 같이 정의해요. \(A_{ij} = 1\)이면 간선 \(v_i \to v_j\)가 있고, 아니면 \(0\). 이 행렬을 인접 행렬(adjacency matrix)이라 부릅니다. 무향 그래프와 달리 일반적으로 대칭이 아니에요.

이 정리는 단순한 산수처럼 보이지만 강력합니다. 길이 \(k\) 워크의 수를 일일이 세지 않고 행렬 곱셈만으로 답을 얻을 수 있고, 빠른 거듭제곱 알고리즘을 쓰면 \(O(n^3 \log k)\)에 끝납니다.

10.4 워크 관계 Walk Relations

그래프 위에서 "\(u\)에서 \(v\)로 갈 수 있는가?"라는 질문은 곧 도달가능성(reachability) 문제입니다. 유향 그래프 \(G\) 위에서 워크 관계 \(G^*\)를 다음과 같이 정의합시다. \(u\, G^*\, v\) 라는 것은 \(u\)에서 \(v\)로 가는 길이 \(\geq 0\)인 워크가 존재한다는 의미입니다 (길이 0 워크는 자기 자신이에요).

워크 관계 \(G^*\)는 두 가지 좋은 성질을 갖습니다. 첫째, 반사적이에요. 모든 정점 \(u\)에 대해 길이 0 워크가 자명히 있죠. 둘째, 추이적입니다. \(u G^* v\)이고 \(v G^* w\)이면 두 워크를 이어 붙여 \(u G^* w\)가 됩니다. 이 두 성질을 만족하는 관계를 일반적으로 전순서(preorder)라고 부릅니다.

10.5 DAG와 스케줄링 Directed Acyclic Graphs & Scheduling

유향 그래프 중에서 사이클이 없는 것을 DAG(directed acyclic graph)라고 부릅니다. 일상 어디에나 등장해요. 메이크파일의 빌드 의존성, 강의 계획표의 선수과목, 스프레드시트의 셀 의존성, 깃 커밋 이력 모두 DAG 구조를 갖죠. "A를 하기 전에 B와 C를 끝내야 한다"라는 종류의 제약은 모두 DAG로 표현됩니다.

증명의 핵심은 "DAG에는 들어오는 차수가 0인 정점이 항상 존재한다"는 보조정리예요. 만약 모든 정점의 \(\deg^- \geq 1\)이면, 어디서든 거꾸로 화살표를 따라 무한히 갈 수 있는데 정점이 유한하므로 비둘기집에 의해 사이클이 생깁니다 ― 모순. 그래서 \(\deg^-(v) = 0\)인 정점을 골라 맨 앞에 두고 그 정점을 지운 뒤 재귀하면 위상 정렬이 만들어집니다. 이걸 알고리즘으로 옮긴 게 칸(Kahn)의 알고리즘이에요.

def topo_sort(V, E):
    indeg = {v: 0 for v in V}
    for (u, v) in E:
        indeg[v] += 1
    ready = [v for v in V if indeg[v] == 0]
    order = []
    while ready:
        u = ready.pop()
        order.append(u)
        for (a, b) in E:
            if a == u:
                indeg[b] -= 1
                if indeg[b] == 0:
                    ready.append(b)
    if len(order) != len(V):
        raise ValueError("graph has a cycle")
    return order

10.6 부분 순서 Partial Orders

10.5의 의존성 관계를 추상화하면 부분 순서가 됩니다. 직관적으로 부분 순서는 "어떤 둘은 비교 가능하지만, 어떤 둘은 비교 불가능"한 상황을 모형화해요.

예시는 흔합니다. 자연수 위의 \(\leq\), 양의 정수 위의 정수 나눗셈 \(|\) (\(a \mid b\)는 \(a\)가 \(b\)를 나눈다는 뜻), 집합 위의 부분집합 관계 \(\subseteq\) 등이 모두 부분 순서예요. 자연수의 \(\leq\)는 모든 둘이 비교되지만, 정수 나눗셈에서는 3과 5가 서로 나누지도 나누어지지도 않으므로 비교 불가능합니다.

10.7 집합 포함으로 표현 Representing Partial Orders by Set Containment

겉모습은 다양해 보이지만, 사실 모든 부분 순서는 깊은 의미에서 본질적으로 한 가지 모양을 합니다. 그게 바로 집합 포함 관계 \(\subseteq\)예요.

이 정리는 단순하지만 철학적으로 시원합니다. "어떤 추상적인 순서든 결국 ‘이 원소 아래에 어떤 원소들이 있는가’의 집합 포함으로 환원된다." 즉 부분 순서론의 모든 일반론은 \(\subseteq\) 의 일반론과 같다는 뜻이에요. 컴퓨터 과학에서 타입의 서브타이핑(subtyping), 권한 격자(lattice of capabilities) 같은 구조도 결국 이 표현 정리의 그림자입니다.

10.8 전순서 Linear Orders

부분 순서 중에서 특히 임의의 두 원소가 비교 가능한 경우를 전순서(linear order, total order)라 부릅니다. 직관적으로 한 줄로 쭉 세울 수 있다는 뜻이에요.

전순서의 대표 예는 자연수 \((\mathbb{N}, \leq)\), 정수 \((\mathbb{Z}, \leq)\), 실수 \((\mathbb{R}, \leq)\), 그리고 사전식 순서로 정렬한 문자열들입니다. 반면 부분집합 \(\subseteq\)나 정수 나눗셈 \(\mid\)는 전순서가 아니에요.

이 정리의 알고리즘적 사촌이 바로 위상 정렬(10.5)이에요. DAG의 도달가능성 부분 순서를 어떤 전체적 일렬 순서(스케줄)로 확장한 것이 위상 정렬이거든요. 그래서 위상 정렬은 일반적으로 유일하지 않아요. 비교 불가능했던 두 원소를 어느 쪽이 먼저인지 자유롭게 선택할 수 있기 때문입니다.

10.9 곱 순서 Product Orders

두 포셋이 있으면 자연스럽게 그 곱집합 위에 새 부분 순서를 만들 수 있습니다. 이를 곱 순서라 해요. 컴퓨터과학에서는 다차원 좌표 비교, 다중 우선순위 정렬, 동적 계획법의 부분 문제 의존 관계 등에 끊임없이 등장합니다.

주의할 점: 두 인자 \((A, \preceq_A)\)와 \((B, \preceq_B)\)가 모두 전순서라 해도 곱 순서는 전순서가 아닙니다. 예를 들어 \((\mathbb{N}, \leq)\)와 자기 자신의 곱을 보면, \((1, 2)\)와 \((2, 1)\)은 어느 쪽도 다른 쪽을 좌표별로 지배하지 못해요. 비교 불가능합니다.

덧붙이자면, 사전식 순서는 곱 순서와 다른 또 한 가지 자연스런 곱 구조예요. \((a_1, b_1) <_{\text{lex}} (a_2, b_2)\)는 "\(a_1 < a_2\) 또는 \(a_1 = a_2\)이고 \(b_1 < b_2\)". 사전식 순서는 두 인자가 전순서이면 곱도 전순서로 유지되지만 직관과 어긋나는 결과(\(\epsilon\)-우월 같은)를 낳기도 하니 상황에 맞게 골라 써야 합니다.

10.10 동치관계 Equivalence Relations

부분 순서가 "어떤 것이 다른 것보다 더 큰가"를 다룬다면, 동치관계는 "두 원소가 같은 종류인가"를 다룹니다. 약간 다른 세계지만 정의 형식은 비슷해요.

동치관계의 가장 친숙한 예가 모듈로 합동 \(a \equiv b \pmod n\)입니다. 같은 나머지를 갖는 정수들끼리 같다고 보는 거죠. 또 7장에서 다뤘던 함수의 동치, 도형의 합동 등도 모두 동치관계입니다.

이 정리 덕분에 "동치관계"와 "분할"은 같은 개념의 두 얼굴이라고 봐도 됩니다. 한쪽에서 다른 쪽으로 자유롭게 오갈 수 있어요. 컴퓨터과학에서는 그래프의 강한 연결요소(SCC), 합동 연산을 통한 자료구조(union-find), 컴파일러의 등가 변수 분석 등에서 매일같이 등장합니다.

10.11 관계 성질 요약 Summary of Relational Properties

10장에서 등장한 다양한 관계의 성질을 한 표로 정리하고 마무리합시다. 각 행은 관계의 종류이고, 각 열은 그 관계가 만족해야 하는 조건이에요. 같은 정의를 외우려 하기보단, 어떤 조합이 어떤 의미를 갖는지 음미하면 좋습니다.

다음 챕터에서는 화살표 방향을 잊은 무향 그래프로 돌아가, 연결성과 트리의 세계를 본격적으로 탐험합니다. 거기서 만나는 도구들도 결국 이 챕터에서 다진 관계의 언어 위에 세워진 것임을 기억하면 좋겠어요.

11.1 라우팅 Routing

네트워크라고 하면 거창해 보이지만, 본질은 단순합니다. 입력이라 부르는 점들 \(I_1, I_2, \dots, I_N\)이 있고, 출력이라 부르는 점들 \(O_1, O_2, \dots, O_N\)이 있습니다. 그리고 각 입력은 어딘가의 출력으로 메시지를 보내고 싶어 합니다. 데이터 센터에서는 입력이 서버, 출력도 서버. 멀티코어 칩에서는 입력이 코어, 출력은 메모리 뱅크. 본질은 같습니다.

문제는 입력과 출력 사이를 직선으로 잇는 것이 비현실적이라는 점이에요. \(N\)개 입력과 \(N\)개 출력을 모두 직접 연결하면 선이 \(N^2\)개 필요합니다. \(N=10^6\)이면 선이 \(10^{12}\)개. 이걸 진짜로 깔 사람은 없겠죠. 그래서 가운데에 스위치(switch)들을 두고, 메시지가 스위치를 거쳐 가도록 만듭니다. 결국 우리가 다루는 건 정점이 입력·스위치·출력이고 간선이 통신선인 그래프예요.

이 위에서 진짜 풀어야 할 문제는 무엇일까요? 어떤 입력이 어떤 출력으로 가고 싶다는 요청이 한꺼번에 들어옵니다. 이 요청을 깔끔하게 모델링한 것이 순열 라우팅(permutation routing)입니다.

여기서 우리는 라우팅이 가능한가만 묻는 게 아니라, 얼마나 좋게 가능한가를 묻고 싶어집니다. 경로가 너무 길면 지연(latency)이 커지고, 한 간선에 너무 많이 몰리면 병목이 되니까요. 그래서 다음 절에서는 네트워크의 품질을 재는 자(尺)들을 정의합니다.

11.2 라우팅 측정 Routing Measures

네트워크를 평가하는 자는 크게 네 가지입니다. 지름, 혼잡도, 비용(스위치 수), 그리고 대역폭. 하나만 가지고는 좋은 네트워크를 못 만들고, 항상 트레이드오프가 있다는 점을 미리 강조해 둡니다.

혼잡도 정의가 살짝 어지러울 수 있어요. "최악의 순열을 가져와 보세요. 그래도 우리는 라우팅을 잘 골라서 한 간선당 통과 메시지 수를 이 정도로 막을 수 있어요." 이 약속의 보증치가 \(\mathrm{cong}(G)\)입니다.

이제 자(尺)는 다 만들었으니, 실제 네트워크 디자인들을 그 자에 대 봅시다.

11.3 네트워크 디자인 Network Designs

네트워크 토폴로지의 동물원에는 별별 친구들이 다 있지만, 교과서에 빠지지 않는 네 가지를 살펴봅니다. 완전 이분 그래프, 2D 메시, 버터플라이, 그리고 베네스 네트워크.

완전 이분 그래프 \(K_{N,N}\)

모든 입력을 모든 출력에 직접 연결한 구조입니다. 입력과 출력 사이 간선이 \(N^2\)개. 지름은 1, 혼잡도는 1(각 입력은 자기 출력으로 가는 한 줄만 쓰면 끝). 완벽해 보이죠? 그런데 비용이 \(\Theta(N^2)\)이라 \(N\)이 커지면 미친 짓이 됩니다.

2D 메시(grid)

\(N = n^2\)개의 입력과 출력을 \(n \times n\) 격자에 늘어놓은 구조입니다. 각 격자칸이 작은 스위치이고, 옆 칸끼리만 직접 연결됩니다. 만들기 쉽고(인접 연결만 있으니까) 비용도 \(\Theta(N)\)으로 매우 쌉니다. 대신 한 끝에서 다른 끝까지 가려면 격자를 가로질러야 해서 지름이 \(\Theta(\sqrt{N})\)에 달해요.

버터플라이 네트워크

\(N = 2^n\)일 때, 입력 측 \(N\)개·출력 측 \(N\)개와 가운데 \(n+1\)개 층을 두고, 각 층마다 비트 하나씩을 "고를지 말지" 결정하는 스위치를 배치하는 구조입니다. 입력에서 출력까지 정확히 \(n+1\) 단계를 거치고, 각 단계에서 한 비트를 결정하면 모든 출력에 도달할 수 있어요.

지름이 \(\log N\)으로 정말 작아진다는 점에 주목하세요. 메시 대비 지수적으로 짧습니다. 대신 어떤 못된 순열을 가져오면 한 간선에 \(\sqrt{N}\) 개의 경로가 몰리는 일이 벌어집니다. "빠르긴 한데 운 나쁜 패턴에서는 막힌다"가 버터플라이의 성격이에요.

베네스(Beneš) 네트워크

버터플라이의 혼잡도 문제를 해결하는 영리한 트릭은, 버터플라이를 두 개 등을 맞대고 붙여 거의 거울처럼 이어붙이는 것입니다. 이렇게 만든 것이 베네스 네트워크예요. 지름은 \(2\log_2 N\) 정도로 살짝 늘지만, 어떤 순열이 와도 혼잡도 1로 라우팅이 가능하다는 굉장한 성질을 얻습니다.

한눈에 보는 비교표

네 가지 디자인을 같은 자(尺)로 정렬하면 다음과 같습니다.

마지막으로 이 챕터의 메시지를 한 줄로 정리해 두면. 통신 네트워크 설계는 지름·혼잡도·비용이라는 삼각형 안에서 어디에 무게를 둘지 고르는 게임입니다. 그래프라는 한 가지 언어로 셋을 모두 정량화할 수 있다는 사실이, 이산수학이 시스템 설계에 끼친 가장 우아한 기여 중 하나예요. 다음 챕터에서는 이 그래프 위에서 걷기가 갖는 또 다른 면 — 연결성, 트리, 색칠 — 을 살펴봅니다.

12.1 정점 인접과 차수 Vertex Adjacency and Degrees

그래프 이론에서 가장 먼저 배우는 종류의 그래프는 단순 그래프입니다. "단순"이라는 말은 두 가지 제한을 뜻해요. 같은 두 정점을 잇는 변이 두 개 이상 존재하지 않고(다중변 금지), 자기 자신을 잇는 변(루프)도 없다는 것이죠. 단순 그래프는 사람·도시·웹페이지처럼 "쌍이 관계 있느냐 없느냐"만 묻는 이산 구조에 자연스럽게 들어맞습니다.

변이 정점에 닿아 있을 때 우리는 그 변이 그 정점에 접속(incident)한다고 말합니다. 정점 \( v \)에 접속하는 변의 개수를 \( v \)의 차수(degree)라 하고 \( \deg(v) \)로 씁니다. 단순 그래프에서는 자기 자신과 잇는 루프가 없으므로 \( \deg(v) \)는 그냥 \( v \)의 이웃의 개수와 같습니다.

우연이 아닙니다. 모든 변은 양 끝의 두 정점 차수에 각각 1씩 기여합니다. 그래서 모든 정점의 차수를 더하면, 모든 변이 두 번씩 세어지죠.

이름이 "악수 보조정리"인 까닭은 이래요. 파티에서 사람들이 악수를 했을 때, 모든 사람이 악수한 횟수의 합은 항상 짝수다 — 모든 악수는 두 사람의 카운트를 1씩 올리니까요. 컴퓨터과학에서는 그래프의 평균 차수 \( \bar d = 2|E|/|V| \)를 추정할 때 이 식이 그대로 들어갑니다.

12.2 인구 통계의 이상 Sexual Demographics in America

핸드셰이크 보조정리는 작은 식 같지만, 통계 기사를 비판하는 무기로 쓰일 수 있습니다. 미국에서 흔히 인용되던 설문 결과 하나를 가져와 봅시다. "남성은 평생 평균 7명의 이성 파트너를 가지며, 여성은 4명을 가진다." 이런 식의 보고서, 어디서 본 적 있죠? 그래프 이론으로 5초만 생각해 보면 이 숫자는 동시에 옳을 수 없다는 것을 알 수 있습니다.

이성 관계라는 그래프 \( G \)를 그려 봅시다. 정점은 사람이고, 변은 "이 두 사람이 한 번이라도 이성 파트너 관계였다"는 사실. 그러면 한쪽 끝은 남자, 다른 쪽 끝은 여자인 변만 있는 셈이죠. 이런 그래프를 우리는 곧 이분 그래프(bipartite)라 부르게 됩니다.

남성 집합을 \( M \), 여성 집합을 \( W \)라 하고, 모든 변의 양 끝이 한쪽은 \( M \), 한쪽은 \( W \)라고 합시다. 핸드셰이크 보조정리에서 차수의 합은 변 개수의 2배지만, 이 합을 두 그룹으로 쪼개면 \[ \sum_{m \in M} \deg(m) \;+\; \sum_{w \in W} \deg(w) = 2|E|. \] 그런데 이분 그래프에서는 한 변마다 \( M \) 쪽 차수에 1, \( W \) 쪽 차수에 1을 더하므로 \[ \sum_{m \in M} \deg(m) = |E| = \sum_{w \in W} \deg(w). \] 즉 남자들의 파트너 수의 합과 여자들의 파트너 수의 합은 정확히 같아야 합니다.

그래서 이 종류의 통계는 수학적으로 동시에 참일 수 없습니다. 누군가는 거짓말을 하거나, 기억을 잘못하거나, 표본이 편향되었거나 — 적어도 둘 중 하나는 사실과 거리가 멉니다. 사회학자들이 이미 알고 있는 현상이지만, 핵심을 한 줄로 잡아 주는 것은 결국 핸드셰이크 보조정리예요. 그래프적 사고는 가끔 신문 기사 한 면을 통째로 의심하게 만듭니다.

12.3 흔히 보는 그래프들 Some Common Graphs

그래프 이론을 공부하다 보면 같은 모양의 그래프가 반복해서 등장합니다. 이름을 붙여 두면 편하니까, 자주 보는 다섯 종류만 정리해 둡시다.

12.4 동형 Isomorphism

두 그래프가 그림으로 보면 다르게 생겼는데, 정점 이름만 바꿔 주면 사실은 같은 그래프인 경우가 많습니다. 이 "이름 바꾸기로 같다"는 관계가 동형입니다.

쉽게 말해 정점에 이름표를 다시 붙여서 변의 모임이 정확히 일치하게 만들 수 있느냐는 것이죠. 동형은 동치 관계입니다(반사·대칭·추이). 그래서 그래프를 분류할 때 우리는 보통 동형류(isomorphism class) 단위로 셉니다.

두 그래프가 동형인지 보이려면 적절한 \( f \)를 구체적으로 제시하면 됩니다. 동형이 아님을 보이는 게 더 흥미로운데, 이때 쓰는 도구가 동형 invariant입니다. 동형이라면 보존되어야 하는 양 — 정점 수, 변의 수, 차수 수열, 사이클의 길이, 연결 성분의 개수, 보 그래프의 차수 수열 등 — 가운데 하나라도 다르면 두 그래프는 절대 동형일 수 없습니다.

12.5 이분 그래프와 매칭 Bipartite Graphs & Matchings

이분 그래프는 정점을 두 그룹 \( L, R \)로 쪼갤 수 있고, 모든 변의 두 끝이 한쪽씩에 들어가는 그래프입니다(같은 쪽 안에서는 변이 없음). 12.2의 이성 파트너 그래프, 학생-수업 그래프, 작업자-할 일 그래프, 이미지 픽셀-라벨 그래프 등 현실에서 정말 흔히 나옵니다.

완전 매칭이 존재하기 위한 깔끔한 조건이 있습니다. 부분집합 \( S \subseteq L \)에 대해 \( S \)의 이웃들의 집합 \( N(S) = \{ r \in R : \exists \ell \in S, \{\ell, r\} \in E \} \)를 봅시다. 만약 어떤 \( S \)에 대해 \( |N(S)| < |S| \)라면, \( S \) 안의 사람들이 \( N(S) \) 안의 자리 안에서 서로 다른 짝을 모두 찾을 수 없죠 — 비둘기집 원리. 놀라운 것은 이 비둘기집 조건의 역도 성립한다는 것입니다.

홀의 정리는 결혼 정리(marriage theorem)라고도 불립니다. \( L \)을 신부, \( R \)을 신랑이라 두고 누가 누구와 결혼할 수 있는지를 변으로 표시했을 때, 모든 신부가 자기가 받아들일 수 있는 사람과 짝을 이룰 수 있는 조건이 위와 같다는 동화 같은 해석이 있죠. 컴퓨터과학에서는 작업 분배, 강좌 배정, 네트워크 흐름 등에 곧장 적용됩니다.

12.6 채색 Coloring

그래프의 정점을 색칠할 때, 변으로 이어진 두 정점은 서로 다른 색이어야 한다는 제한을 둬 봅시다. 이런 식의 제약 만족 문제가 의외로 많은 응용을 갖습니다. 시험 시간표 짜기(과목이 정점, 시간 충돌이 변), 무선 주파수 할당(기지국이 정점, 간섭이 변), 컴파일러 레지스터 할당(변수가 정점, 동시 활성이 변) 같은 문제 모두 결국 그래프 채색이죠.

채색수의 일반적 결정은 어렵습니다 — 정확히는 NP-완전. 하지만 평면 위에 변의 교차 없이 그릴 수 있는 그래프(평면 그래프)에 대해서는 이 세상에서 가장 유명한 그래프 정리가 답을 줍니다.

12.7 단순 그래프의 워크 Walks in Simple Graphs

그래프 안에서 정점들 사이를 변을 타고 이동하는 길을 정확히 정의해 둡시다. 일상어 "경로"와 수학 용어가 미묘하게 다르므로 주의가 필요합니다.

단순 그래프에서는 변이 한 쌍의 정점으로 결정되니, 변을 명시하지 않고 정점만 \( v_0, v_1, \dots, v_k \)로 적어도 워크가 잘 정의됩니다. 이 표기를 보통 더 자주 씁니다.

12.8 연결성 Connectivity

워크가 정의되면 자연스레 따라오는 개념이 연결성입니다. 두 정점이 같은 "덩어리"에 있는지 묻는 것이죠.

연결 성분은 그래프를 여러 덩어리로 깔끔하게 쪼개는 분할입니다. 그래프 알고리즘에서 가장 먼저 하는 전처리 중 하나가 BFS/DFS로 연결 성분을 모두 찾아 라벨링하는 일이죠. 시간 복잡도는 \( O(|V| + |E|) \).

12.9 특수한 워크와 투어 Special Walks and Tours

그래프 이론은 18세기 쾨니히스베르크라는 도시의 다리 일곱 개에서 시작되었습니다. 시민들의 일요일 산책 퀴즈: "일곱 다리를 모두 정확히 한 번씩 건너서 출발지로 돌아올 수 있을까?" 1736년 오일러가 답했죠 — "할 수 없습니다." 그리고 그 이유를 일반화해 그래프 이론의 첫 정리가 탄생합니다.

오일러 회로의 특징은 변을 빠짐없이 한 번씩, 해밀턴 회로의 특징은 정점을 빠짐없이 한 번씩 — 한 글자 차이지만 난이도가 천양지차입니다.

쾨니히스베르크 다리는 네 정점(섬·강안)의 차수가 각각 5, 3, 3, 3으로 모두 홀수, 홀수 차수 정점이 4개이므로 오일러 회로도 트레일도 불가능. 오일러는 이 단순한 기준으로 산책 문제에 종지부를 찍었습니다.

12.10 k-연결 그래프 k-connected Graphs

연결 그래프는 한 덩어리지만, 정점 하나만 빼면 두 덩어리로 쪼개질 수도 있죠. 이런 "약한 연결"과 "튼튼한 연결"을 구분하기 위한 개념이 \( k \)-연결성입니다.

1-연결은 보통의 연결과 같습니다. 2-연결 이상은 흔히 "안전한 네트워크"와 관련됩니다. 라우터 한 대가 죽어도 인터넷이 죽지 않으려면 라우팅 그래프가 2-연결이어야 하죠. 데이터센터 토폴로지나 항공 노선망 설계에서 \( k \)-연결성은 핵심 지표입니다.

멩거의 정리는 그래프 이론의 모든 "최소 컷 = 최대 흐름" 류 정리들의 원형이며, 알고리즘적으로는 네트워크 흐름으로 환원해 효율적으로 풀 수 있습니다.

12.11 숲과 트리 Forests & Trees

마지막으로 그래프 이론에서 가장 깔끔한 가족, 트리를 만나봅시다. 컴퓨터과학 전체의 자료구조 절반을 떠받치고 있는 구조죠.

트리는 동치인 정의가 여러 개여서, 어떤 게 가장 자연스럽냐는 책마다 다릅니다. 다음 정리가 핵심입니다.

13.1 평면에 그래프 그리기 Drawing Graphs in the Plane

그래프를 종이에 그릴 때, 우리는 정점을 점으로 찍고 간선을 곡선으로 잇습니다. 그런데 간선들이 서로 가로지르지 않게 그릴 수 있을까요? 어떤 그래프는 손쉽게 가능하지만, 어떤 그래프는 아무리 돌려봐도 어딘가는 꼭 교차합니다. 이 차이를 수학적으로 다루는 게 바로 평면 그래프 이론이에요.

가장 유명한 도입 문제가 있습니다. 바로 세 집-세 우물 문제(three utilities puzzle)예요. 세 채의 집이 나란히 있고, 그 앞에 세 개의 우물(가스, 물, 전기라고 해도 좋아요)이 있습니다. 모든 집은 모든 우물에 연결되어야 하는데, 파이프들이 서로 교차하면 안 된다는 조건이 붙어요. 자, 종이 위에서 이걸 해낼 수 있을까요?

이 문제는 그래프 언어로 옮기면 \(K_{3,3}\), 즉 양쪽에 정점이 3개씩 있는 완전이분그래프를 평면에 교차 없이 그릴 수 있느냐는 질문이 됩니다. 결론부터 말하면, 답은 "안 된다"입니다. 그리고 왜 안 되는지를 증명하는 게 이 챕터의 핵심 도구가 돼요.

비슷하게 \(K_5\) — 정점 5개가 모두 서로 연결된 완전그래프 — 도 평면에 그릴 수 없습니다. 이 두 그래프, \(K_5\)와 \(K_{3,3}\)은 "평면 그래프가 아닌 가장 작은 두 가지" 같은 위치를 차지해요. 나중에 쿠라토프스키 정리에서 더 멋진 의미를 갖게 됩니다.

13.2 평면 그래프의 정의 Definitions of Planar Graphs

이제 정의를 엄밀하게 적어봅시다. 직관은 충분히 쌓였으니까요.

주의할 점이 있어요. 평면 그래프인 것과 평면에 "교차 없이 그려진" 것은 약간 다릅니다. 같은 그래프를 어떤 식으로 그리느냐에 따라 교차가 생길 수도 있고 없을 수도 있어요. 평면 그래프란 "교차 없이 그릴 수 있는 방법이 적어도 하나 존재하는" 그래프를 말합니다.

평면 위에 교차 없이 그려진 그래프는 평면을 여러 영역으로 나눕니다. 이 각 영역을 면(face)이라고 불러요.

13.3 오일러 공식 Euler's Formula

위 예제들을 다시 봅시다. \(V-E+F\)를 계산해보세요.

• \(K_3\): \(3-3+2=2\)
• \(C_4\): \(4-4+2=2\)
• \(K_4\): \(4-6+4=2\)

전부 \(2\)예요. 우연이 아닙니다.

오일러 공식은 단순해 보이지만 굉장히 강력합니다. \(V, E\) 둘 중 하나만 알아도 면 수에 제약이 생기고, 곧 보겠지만 평면 그래프의 간선 수에 상한을 강제하기까지 합니다.

13.4 평면 그래프 간선 수 한계 Bounding the Number of Edges in a Planar Graph

평면 그래프는 정점 수에 비해 너무 많은 간선을 가질 수 없습니다. 직관적으로, 정점이 \(V\)개라도 간선이 너무 많으면 어느 순간 교차하지 않고는 그릴 수가 없거든요. 이걸 수식으로 깔끔하게 잡아봅시다.

핵심 아이디어는 면-간선 이중 계산(double counting)입니다. 각 면의 경계 길이(둘러싼 간선 수)를 모두 합하면 어떻게 될까요? 모든 간선은 양쪽에 면이 하나씩 붙어 있으니까(같은 면이 양쪽일 수도 있지만 그래도 두 번 카운트됨), 이 합은 정확히 \(2E\)와 같습니다.

13.5 \(K_5\)와 \(K_{3,3}\)로의 회귀 Returning to K5 and K3,3

13.1에서 미뤄둔 약속을 갚을 시간이에요. \(K_5\)와 \(K_{3,3}\) 둘 다 평면 그래프가 아니라는 사실을 13.4의 부등식으로 정확히 증명할 수 있습니다.

드디어 세 집-세 우물 퍼즐의 답이 나왔어요. 절대로 못 그립니다. 종이에서 못 그릴 뿐 아니라, 평면이라는 공간 자체에서 불가능합니다(도넛 표면 같은 데서는 가능하답니다, 흥미롭게도).

13.6 평면 그래프의 채색 Coloring Planar Graphs

지도를 색칠할 때, 인접한 나라(국경을 맞댄 나라)에 같은 색을 쓰지 않으려면 색이 몇 개 필요할까요? 각 나라를 정점으로, 인접한 나라끼리 간선으로 잇는 그래프를 만들면, 이 그래프는 자연스럽게 평면 그래프가 됩니다. 따라서 지도 색칠 문제는 곧 평면 그래프의 채색수(chromatic number) 문제예요.

13.7 다면체 분류 Classifying Polyhedra

오일러 공식의 가장 우아한 응용 중 하나는 정다면체(Platonic solid)가 정확히 5개뿐이라는 사실의 증명입니다. 정다면체란 모든 면이 합동인 정다각형이고 모든 꼭짓점이 동일한 모양으로 만나는 볼록다면체예요.

왜 평면 그래프가 다면체랑 관련이 있을까요? 볼록다면체를 잡고 그 한 면을 풍선 늘이듯이 평면 위로 펼치면, 다면체의 정점-간선 구조가 평면 그래프가 됩니다. 그러면 오일러 공식 \(V-E+F=2\)를 그대로 적용할 수 있어요(여기서 \(F\)는 다면체의 면 수와 일치하고, 외부면이 곧 펼친 그 면에 해당합니다).

각 면이 \(p\)각형이고 각 꼭짓점에 \(q\)개의 면이 모인다고 합시다. 그러면:

• 면 수 × 면당 변 수는 간선을 두 번 셈: \(pF = 2E\), 즉 \(F=2E/p\).
• 꼭짓점 수 × 꼭짓점당 모이는 면(=간선 수)은 간선을 두 번 셈: \(qV = 2E\), 즉 \(V=2E/q\).

오일러 공식에 대입하면 \[ \frac{2E}{q} - E + \frac{2E}{p} = 2 \quad\Rightarrow\quad \frac{1}{p}+\frac{1}{q} = \frac{1}{2}+\frac{1}{E}. \] \(E>0\)이므로 우변 \(>1/2\), 즉 \[ \frac{1}{p}+\frac{1}{q} > \frac{1}{2}. \] 또한 \(p\geq 3\)(다각형이니), \(q\geq 3\)(꼭짓점에 최소 3면 모임).

이 부등식 \(\frac{1}{p}+\frac{1}{q}>\frac{1}{2}\)에 \(p,q\geq 3\)인 정수해를 모두 찾아봅시다.

• \(p=3\)이면 \(\frac{1}{q}>\frac{1}{6}\), 즉 \(q<6\). 가능한 \(q=3,4,5\).
• \(p=4\)이면 \(\frac{1}{q}>\frac{1}{4}\), 즉 \(q<4\). 가능한 \(q=3\).
• \(p=5\)이면 \(\frac{1}{q}>\frac{3}{10}\), 즉 \(q\leq 3\). 가능한 \(q=3\).
• \(p\geq 6\)이면 \(\frac{1}{p}+\frac{1}{q}\leq \frac{1}{6}+\frac{1}{3}=\frac{1}{2}\)라 부등식 위반. 불가능.

따라서 가능한 \((p,q)\)는 정확히 5쌍: \((3,3),(3,4),(3,5),(4,3),(5,3)\). 이 다섯이 정사면체부터 정이십면체까지 다섯 정다면체에 대응합니다.

각 행의 \(V-E+F\)를 계산해보면 모두 \(2\)예요. 오일러 공식이 다면체의 세계에서도 그대로 살아있다는 게 정말 멋지죠.

13.8 평면 그래프의 또 다른 특성 Another Characterization for Planar Graphs

지금까지 본 부등식 \(E\leq 3V-6\)은 평면 그래프가 되기 위한 필요조건이지만 충분조건은 아닙니다. 즉, 부등식을 만족하는데도 평면이 아닌 그래프가 있을 수 있어요. 그러면 평면 그래프를 그래프 자체의 구조만으로 완전히 특징지을 방법이 있을까요?

놀랍게도 답은 "예"입니다. 그것도 \(K_5\)와 \(K_{3,3}\)을 다시 만나면서요.

여기서 분할이란 어떤 간선의 중간에 새로운 차수-2 정점을 끼워넣는 연산을 반복해서 얻는 그래프를 말합니다. 직관적으로는 간선을 "여러 토막으로 잘라낸" 그래프예요. 본질적으로는 같은 그래프인 셈이죠.

이 정리의 의미는 깊습니다. 평면이 아닌 모든 그래프는 그 안에 어떤 식으로든 \(K_5\)나 \(K_{3,3}\)을 "숨기고" 있다는 말이거든요. 이 둘이 비평면성의 근원적인 두 가지 패턴이라는 거예요.

평면 그래프의 인식 자체는 효율적으로 풀 수 있는 문제이기도 합니다. 1974년 호프크로프트와 타잔이 \(O(V)\) 시간에 평면성을 판정하는 알고리즘을 제시했어요. 그래프 이론과 알고리즘이 만나는 멋진 지점이죠.

이 챕터를 마치면서, 평면 그래프가 단지 "예쁜 그림"의 문제가 아니라는 걸 다시 강조하고 싶어요. 회로 기판 설계에서는 평면성이 곧 단일 층에 인쇄 가능한지를 결정하고, 컴퓨터 그래픽에서는 평면 메시 분해가 텍스처 매핑의 기반이 됩니다. 단순한 정의에서 출발한 이론이 이렇게 풍부한 응용으로 뻗어나간다는 점이, 이산수학을 공부하는 즐거움 중 하나예요.

14.1 연금의 가치 The Value of an Annuity

합 이야기를 금융에서 시작하는 건 좀 의외일 수 있는데, 사실 등비급수 공식이 가장 자연스럽게 등장하는 무대 중 하나가 연금(annuity)입니다. 시나리오는 단순해요. 매년 \( m \)원씩 \( n \)년 동안 받기로 한 계약이 있다고 해 봅시다. 이 계약의 "지금 가치"는 얼마일까요?

핵심은 돈에는 시간 가치가 있다는 점입니다. 1년 뒤 받는 1만 원은 오늘 받는 1만 원과 같지 않아요. 오늘 1만 원이 있으면 은행에 넣어 이자를 받을 수 있으니까요. 이자율을 연 \( p \)라 하면, 오늘 1원은 1년 뒤 \( 1+p \)원이 되고, 거꾸로 1년 뒤 1원은 오늘 \( \frac{1}{1+p} \)원의 가치만큼만 됩니다. \( r = \frac{1}{1+p} \)라 두면 \( k \)년 뒤 1원의 현재 가치는 \( r^k \)입니다.

이 합을 손으로 닫아 봅시다. 등비급수의 정석 트릭은 "원래 합과 \( r \)배 한 합을 빼는" 거예요.

그래서 연금의 현재 가치는

\[ V \;=\; m \cdot \frac{r(1 - r^n)}{1 - r}. \]

예를 들어 매년 100만 원씩 30년 동안 받기로 했고 이자율이 5%면 \( r = 1/1.05 \approx 0.952 \), 계산기를 한 번 두드리면 \( V \approx 1{,}537 \)만 원 정도가 나옵니다. 명목상 받는 총액은 3000만 원인데, "지금 한 번에" 받는다면 그 절반밖에 안 된다는 거예요. 시간이 끼면 돈이 가벼워집니다.

14.2 거듭제곱의 합 Sums of Powers

등비급수 다음으로 자주 만나는 합은 거듭제곱의 합입니다. 가장 어린 사촌은 \( 1 + 2 + \cdots + n \)이에요.

제곱의 합은 살짝 더 복잡한데, 결과는 여전히 깔끔합니다.

증명은 귀납법이 정석이고(5장), 좀 더 우아하게는 \( (k+1)^3 - k^3 \)의 텔레스코핑 합을 이용해 유도할 수도 있습니다. 핵심 아이디어만 말하면, \( (k+1)^3 - k^3 = 3k^2 + 3k + 1 \)이고 양변을 \( k = 1 \)부터 \( n \)까지 더하면 좌변은 망원경(telescope)으로 \( (n+1)^3 - 1 \)이 됩니다. 우변에서 \( \sum k \)는 이미 알고 있으니 \( \sum k^2 \)을 풀어낼 수 있어요.

일반화하면, 임의의 양의 정수 \( d \)에 대해

\[ \sum_{k=1}^{n} k^d \;=\; \frac{n^{d+1}}{d+1} \;+\; \text{(낮은 차수 항들)}. \]

즉, "0부터 \( n \)까지 \( k^d \)를 적분한 것"인 \( n^{d+1}/(d+1) \)이 주된 항입니다. 이건 우연이 아니라 합이 적분의 이산판이라는 깊은 사실의 단서인데, 다음 절에서 이걸 진짜로 써먹습니다.

14.3 합의 근사 Approximating Sums

닫힌 꼴이 없는 합은 어떻게 다룰까요? 답은 단순합니다 — 적분으로 갈아타는 거예요. 함수 \( f \)가 양수이고 단조증가(monotonic increasing)면, \( k \)에서 \( k+1 \) 사이의 적분 \( \int_k^{k+1} f(x)\,dx \)는 그 구간에서 \( f \)의 어떤 값과 그 다음 값 사이에 갇혀요. 이걸 박스로 그려 보면 다음과 같은 부등식이 즉시 나옵니다.

그림 없이 글로 설명하면 이렇습니다. \( f \)가 증가함수일 때, 폭이 1이고 높이가 \( f(k) \)인 직사각형은 \( [k-1, k] \) 위의 적분을 덮고, \( [k, k+1] \) 위의 적분에는 못 미칩니다. 그래서 직사각형 합 \( \sum f(k) \)는 두 적분 사이에 끼이게 돼요. 단조감소면 그 반대.

위/아래 경계의 차이는 보통 \( f(n+1) - f(1) \) 정도로, 합 자체에 비해 훨씬 작습니다. 그래서 적분 근사는 "가장 큰 항만큼의 오차"로 합을 잡아낼 수 있는 굉장히 효율적인 도구예요.

14.4 모서리 위로 매달기 Hanging Out Over the Edge

이제 매력적인 문제 하나로 잠깐 곁길로 빠져 봅시다. 동일한 책 여러 권을 책상 모서리에 차곡차곡 쌓아서, 가장 위 책이 책상 모서리에서 가능한 한 멀리 매달리도록 하고 싶어요. 책 한 권의 길이는 1이라고 합시다. 책이 \( n \)권 있을 때, 책상 모서리에서 가장 위 책의 끝까지 거리는 최대 얼마까지 갈 수 있을까요?

물리 직관을 짚고 가면, 어떤 책 더미든 무너지지 않으려면 위쪽 더미의 무게중심이 그 아래 받침의 가장자리(또는 그 안쪽)에 있어야 합니다. 이 조건을 단계적으로 적용하면, 위에서부터 \( k \)번째 책은 그 아래 책 끝에서 \( \frac{1}{2k} \)만큼 앞으로 내밀 수 있어요(맨 위 책은 \( 1/2 \), 두 번째는 \( 1/4 \), …).

이제 결정타. 조화수는 발산합니다.

이게 무슨 뜻이냐면, 책을 충분히 많이 쌓으면 돌출량 \( H_n/2 \)을 원하는 만큼 크게 만들 수 있다는 거예요. 한 도서관쯤 있다면 (이론적으로는) 마지막 책이 책상 모서리에서 한 발자국, 두 발자국, 한 블록, 한 도시 너머에까지 매달릴 수 있다는 뜻입니다. 물리적으로는 다듬지 않은 모서리, 흔들림, 마찰 같은 게 다 무시됐지만, 이상화된 이산수학 모델의 입장에서는 정말로 끝없이 멀리 갑니다.

14.5 곱 Products

합을 다루는 도구를 곱으로도 옮길 수 있을까요? 답은 "로그를 씌우면" 깔끔하게 됩니다. 로그는 곱을 합으로 바꿔주는 마법이거든요.

\[ \ln \prod_{k=1}^{n} a_k \;=\; \sum_{k=1}^{n} \ln a_k. \]

그러니까 곱의 점근 행동을 알고 싶으면, 로그를 취해서 합을 분석한 뒤 다시 지수로 돌아가면 됩니다. 가장 유명한 예가 팩토리얼이에요.

스털링 근사를 살짝 손으로 보고 싶으면 로그를 씌워 봅시다.

\[ \ln n! = \sum_{k=1}^{n} \ln k. \]

\( \ln \)은 단조증가이므로 적분 비교에서

\[ \int_{1}^{n} \ln x\,dx \;\le\; \sum_{k=1}^{n} \ln k \;\le\; \int_{1}^{n+1} \ln x\,dx. \]

\( \int \ln x\,dx = x \ln x - x \)이므로 양 끝은 \( n \ln n - n + O(\ln n) \). 따라서

\[ \ln n! \;=\; n \ln n - n + O(\ln n), \qquad n! \;=\; e^{\,n \ln n - n + O(\ln n)} = \left(\frac{n}{e}\right)^n \cdot e^{O(\ln n)}. \]

지수의 \( O(\ln n) \) 부분이 다항식이 되어 \( \sqrt{2\pi n} \) 정도의 보정 인자를 만들어 내는데, 그 정확한 \( \sqrt{2\pi} \)는 좀 더 정밀한 분석(왈리스 곱 같은 것)에서 떨어집니다. 핵심은 적분 근사 한 번이 이렇게 거대한 결과의 뼈대를 잡아준다는 점이에요.

14.6 어려운 합 Double Trouble

합 두 개가 겹치면 가끔 머리가 아파집니다. 그래도 하나의 일관된 원리가 거의 모든 경우에 통하는데, 바로 합의 순서를 바꿔도 된다는 사실이에요. 모든 항이 음이 아니거나, 합이 절대 수렴하면 안전합니다.

\[ \sum_{i \in I} \sum_{j \in J} a_{ij} \;=\; \sum_{j \in J} \sum_{i \in I} a_{ij}. \]

특히 합의 영역이 삼각형 모양이면 순서를 바꿔서 훨씬 쉬워지는 경우가 많아요. 예를 들어 \( i \le j \)인 \( (i,j) \) 쌍에 대해 합한다고 합시다.

이중 합 다루는 마음가짐은 단순합니다 — "지수와 그 범위를 그림으로 그려 보고, 지금 안쪽이 어려우면 바깥으로 보낼 수 있는지 보자". 그게 잘 통하면 무지막지해 보이던 합이 갑자기 정리됩니다.

14.7 점근 표기법 Asymptotic Notation

드디어 알고리즘 수업의 단골손님, 빅 오 표기법(Big-O notation)입니다. 컴퓨터과학 학생이 평생 가장 자주 쓰는 수학 표기 중 하나이고, 그래서 정의가 흐릿하면 평생 헷갈립니다. 한 번 깔끔하게 정리하고 갑시다.

다섯 가지 기호 — \( O, \Omega, \Theta, o, \omega \) — 가 있고, 이들은 모두 두 함수 \( f, g : \mathbb{N} \to \mathbb{R}_{>0} \)의 큰 \( n \)에서의 상대적 크기를 표현합니다.

직관은 이렇습니다. \( O \)는 "위로 \( g \)에 의해 (상수배까지) 눌린다", \( \Omega \)는 "아래로 \( g \)만큼은 자란다", \( \Theta \)는 "위아래로 똑같이 자란다 = 같은 차수". 소문자 \( o \)와 \( \omega \)는 부등호가 엄격한 버전이에요. \( o(g) \)는 "정말 \( g \)보다 무시할 만큼 작다", \( \omega(g) \)는 "정말 \( g \)보다 압도적으로 크다".

흔히 헷갈리는 포인트 몇 개를 정리해 둡시다.

이 표기법이 알고리즘 분석에서 왜 그렇게 사랑받느냐 하면, 우리가 보통 신경 쓰는 게 "코드 한 줄당 정확한 상수"가 아니라 "입력이 두 배가 되면 시간이 어떻게 변하느냐"이기 때문입니다. 상수 계수와 낮은 차수 항을 다 무시해도 그 본질은 변하지 않아요. 그래서:

• 이진 탐색: \( \Theta(\log n) \)
• 선형 탐색: \( \Theta(n) \)
• 병합 정렬: \( \Theta(n \log n) \)
• 버블 정렬: \( \Theta(n^2) \) 최악
• 외판원의 brute force: \( \Theta(n!) \) — 사실상 손도 못 댐

마지막으로 한 가지 비교를 강조해 둡시다. 큰 \( n \)에서 자주 등장하는 함수들의 성장 속도 순서는 다음과 같습니다 (왼쪽이 더 느리게 자람).

\[ 1 \;\prec\; \log\log n \;\prec\; \log n \;\prec\; \sqrt{n} \;\prec\; n \;\prec\; n \log n \;\prec\; n^2 \;\prec\; n^c \;(c>2) \;\prec\; 2^n \;\prec\; n! \;\prec\; n^n. \]

여기서 \( \prec \)는 "리틀 오"를 뜻해요 — 좌변이 우변에 비해 압도적으로 작다는 뜻입니다. 알고리즘을 설계하다 어떤 단계가 \( O(n^3) \)이고 다른 단계가 \( O(n \log n) \)이면, 큰 \( n \)에서 후자는 사실상 무시된다는 식의 직관을 위 사슬이 깔끔하게 정리해 줍니다.

15.1 다른 것을 세어 무언가 세기 Counting One Thing by Counting Another

어떤 집합의 원소를 직접 세기 어려울 때, 우리는 자주 "세기 쉬운 다른 집합과 짝을 지어준다"는 전략을 씁니다. 두 집합 사이에 일대일 대응(전단사)을 만들면, 한쪽의 크기를 알자마자 다른 쪽의 크기가 따라옵니다. 이게 카운팅의 가장 근본적인 원리예요.

말로 하면 당연해 보이지만, 이 단순한 사실이 카운팅의 거의 모든 트릭을 떠받칩니다. 직접 세기 곤란한 \(A\)를 들고 있으면, 더 친숙한 \(B\)와 짝지어 \(|A|\)를 \(|B|\)로 갈아끼웁니다.

"직접 세지 마라, 짝지어라" — 이 챕터의 보이지 않는 슬로건입니다. 다음 절부터 짝지을 만한 표준 집합들 (수열, 순열, 조합 등)을 차례로 만들어둡니다.

15.2 수열 세기 Counting Sequences

카운팅의 첫 번째 도구상자는 수열입니다. 자리마다 어떤 집합에서 원소를 하나씩 골라 늘어놓는 것이죠. 자리들이 서로 독립이라면 단순한 곱셈이 답을 줍니다.

특히 모든 자리가 같은 집합 \(P\)(\(|P| = n\))에서 골라지고 자리 수가 \(k\)이면 수열의 개수는 \(n^k\)입니다.

이 단순한 \(n^k\) 수식 하나로 자료구조의 상태 공간, 해시 함수의 출력 공간, 트리의 노드 수 같은 것들이 한꺼번에 다뤄집니다. 곱 규칙이 카운팅의 \(+\)이라면, 다음 절의 일반화된 곱 규칙은 \(\times\)입니다.

15.3 일반화된 곱 규칙 The Generalized Product Rule

현실의 선택은 종종 "앞에서 무엇을 골랐느냐"에 따라 다음에 가능한 선택지가 달라집니다. 이때도 곱 규칙은 유효한데, 다만 각 자리의 경우의 수가 일정하기만 하면 됩니다.

각 단계의 가짓수가 이전 선택에 의존하더라도, 의존 결과의 크기가 일정하기만 하면 곱셈이 통한다 — 이게 핵심입니다.

\(k\)개를 뽑아 늘어놓는 \(k\)-순열의 수는 \(n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}\)이고, 자주 \(P(n,k)\)로 씁니다. 곧 보겠지만 이 식은 다음 절들과 빠르게 얽혀 들어갑니다.

15.4 나누기 규칙 The Division Rule

때로는 "필요 이상으로 많이 센 다음" 중복분으로 나누는 게 가장 빠른 길입니다. 모든 원소가 똑같이 \(k\)번씩 세어졌다는 사실만 잡으면, 답은 전체 / \(k\)예요.

나누기 규칙은 본질적으로 "대칭이 있는 곳에서는 너무 많이 세어졌으니 대칭 횟수로 나눠라"라는 직관입니다. 알고리즘 분석에서 등가 클래스를 셀 때, 그래프의 라벨 없는 형태를 셀 때 끊임없이 재등장합니다.

15.5 부분집합 세기 Counting Subsets

앞에서 자연스럽게 등장한 \(\binom{n}{k}\)는 이산수학 전체에서 가장 자주 등장하는 수일지도 모릅니다. \(n\)개에서 \(k\)개를 순서 없이 고르는 방법의 수, 일명 이항계수예요.

파스칼 항등식은 파스칼 삼각형을 한 줄씩 채우는 점화식이고, 동적계획법으로 \(\binom{n}{k}\)를 \(O(nk)\)에 정수 산술로 계산하는 알고리즘의 뿌리이기도 합니다.

15.6 반복 있는 수열 Sequences with Repetitions

이번에는 같은 글자가 여러 번 나오는 단어를 늘어놓는 문제입니다. 예를 들어 "MISSISSIPPI"의 글자들을 모두 한 번씩 사용해 만들 수 있는 서로 다른 단어는 몇 개일까요?

또 하나 자주 나오는 문제는 구분되지 않는 \(n\)개의 공을 구분되는 \(k\)개의 상자에 나누어 담는 방법의 수입니다. 이건 그 유명한 "별과 막대"로 셉니다.

15.7 카운팅 연습: 포커 핸드 Counting Practice: Poker Hands

카운팅 도구가 정말로 익었는지 확인하는 가장 즐거운 방법은 포커입니다. 표준 52장 덱(13개 랭크 × 4개 슈트)에서 5장의 손패를 받습니다. 가능한 손패의 총 수는 \(\binom{52}{5} = 2{,}598{,}960\). 이걸 분모 삼아 각 족보의 확률을 계산해봅니다.

포커가 좋은 이유는 같은 손패를 두 번 세는 함정이 곳곳에 숨어 있기 때문입니다. 예를 들어 "쓰리카드 랭크는 13가지, 페어 랭크는 13가지"로 잡으면 같은 랭크를 동시에 골라버리는 모순이 생기죠. 의존적인 선택은 일반화된 곱 규칙에 충실해야 한다는 좋은 교훈입니다.

15.8 비둘기집 원리 The Pigeonhole Principle

가장 단순해 보이지만 가장 자주 쓰는 카운팅 무기 — 비둘기집. 비둘기 \(n+1\)마리를 비둘기집 \(n\)개에 넣으면, 어떤 비둘기집에는 둘 이상이 들어 있다. 너무 당연하지 않나요? 그런데 이 한 줄이 종종 마법을 부립니다.

비둘기집은 카운팅 정리라기보다 존재 증명의 도구입니다. "있다"고 주장만 하고 누군지는 모르는 비구성적 증명의 전형이에요.

15.9 포함-배제 Inclusion-Exclusion

합집합의 크기를 셀 때 단순히 더하면 겹치는 부분이 두 번 세어집니다. 이걸 정확히 보정해주는 공식이 포함-배제예요. 두 집합이면 모두 알고 있는 \(|A \cup B| = |A| + |B| - |A \cap B|\)인데, 이걸 일반화한 모습이 이렇습니다.

증명의 직관: 합집합의 한 원소가 정확히 \(m\)개의 \(A_i\)에 속한다면, 우변에서 그 원소는 \(\binom{m}{1} - \binom{m}{2} + \cdots + (-1)^{m+1} \binom{m}{m}\)번 세어지고, 이 합은 \(1 - (1-1)^m = 1\). 따라서 정확히 한 번 세어집니다.

포함-배제는 식 자체는 무서워 보이지만 적용 과정은 거의 기계적입니다. 어떤 "나쁜 조건들"이 합집합으로 묶이는 문제를 만나면 거의 자동으로 떠올리세요.

15.10 조합적 증명 Combinatorial Proofs

이항계수 항등식 같은 식을 보면 보통 양변을 식으로 펼쳐 같은 다항식임을 보이려고 하죠. 그런데 더 우아한 길이 있습니다 — 같은 집합을 두 가지 방법으로 세서 양변이 같음을 보이는 것입니다. 이걸 조합적 증명이라고 합니다.

식 변형으로 푸는 증명이 "그렇다"라는 사실만 알려준다면, 조합적 증명은 "왜 그런지"를 보여줍니다. 같은 객체를 두 방법으로 세는 습관이 들면 이항계수에 관한 거의 모든 항등식이 자명해 보이기 시작해요. 카운팅이 단순한 수 세기 기법을 넘어 증명 기술이 되는 순간입니다.

16.1 무한급수 Infinite Series

수학자가 수열을 다루는 방법은 여러 가지가 있지만, 그중에서도 가장 강력한 트릭 하나는 “수열을 함수로 변환하기”입니다. 수열 \( (a_0, a_1, a_2, \dots) \)가 있으면, 우리는 다음과 같이 멱급수 한 줄로 묶어버립니다.

여기서 \( x \)는 어떤 구체적인 숫자가 아니라 그냥 자리표시자(placeholder)입니다. 수열의 정보를 잃지 않고 보관하기 위한 옷걸이라고 생각하면 좋아요. \( x = 0.3 \) 같은 걸 대입할 일은 일단 없습니다. 그래서 “수렴 반경이 어떻게 되나” 같은 해석학적 걱정은 16.5에서 따로 정리할 거예요.

가장 처음 만나야 할 항등식 한 줄이 있습니다. 모든 항이 1인 수열 \( (1, 1, 1, 1, \dots) \)의 생성함수는 무엇일까요?

이 식은 고등학교 등비급수 공식에서 \( |x| < 1 \) 조건으로 외우던 그 식이지만, 형식 멱급수 세계에서는 양변이 “같은 수열을 인코딩한다”는 뜻으로 그대로 받아들이면 됩니다. 곱해서 확인해 볼까요. \( (1-x)(1 + x + x^2 + \cdots) \)를 분배법칙으로 풀면 \( 1 + x + x^2 + \cdots - x - x^2 - x^3 - \cdots \)가 되어 가운데 항들이 깔끔히 상쇄되고 1만 남습니다.

16.2 생성함수로 세기 Counting with Generating Functions

생성함수가 단순히 “수열을 식으로 바꾸기” 놀이에서 그쳤다면 이렇게 큰 단원을 차지할 이유가 없죠. 진짜 마법은 두 수열의 생성함수를 곱하면, 그 곱이 어떤 카운팅을 자동으로 수행해 준다는 데 있습니다.

이 컨벌루션이 왜 카운팅을 해주냐면, “전체 무게 \( n \)을 만들 때, \( A \) 쪽에서 무게 \( k \), \( B \) 쪽에서 무게 \( n-k \)를 가져와 짝지은 경우의 수”를 각 \( k \)에 대해 더한 값이기 때문입니다. 두 결정의 합으로 만들어지는 모든 카운팅 문제가 자동으로 컨벌루션이 되는 거예요.

일반화하면 이렇습니다. 어떤 “부품” 종류 \( i \)에서 무게 \( w \)인 부품을 사용한다면 그 부품의 생성함수는 \( x^w \)이고, 같은 종류를 0개 이상 쓸 수 있다면 \( 1 + x^w + x^{2w} + \cdots = \frac{1}{1-x^w} \)입니다. 부품 종류가 여럿이면 각각의 생성함수를 곱해서 전체 카운팅 생성함수를 만들 수 있어요. 이걸 흔히 “선택의 곱은 생성함수의 곱”이라고 외우면 직관에 잘 박힙니다.

16.3 부분분수 Partial Fractions

생성함수를 곱셈으로 잘 만들었다면, 이제 거기서 “수열의 \( n \)번째 항”을 다시 꺼내야 활용도가 올라갑니다. 만약 식이 다항식의 비율 — 즉 유리식 \( \dfrac{P(x)}{Q(x)} \) — 형태라면, 부분분수 분해가 거의 만능 도구가 돼요.

왜 좋냐고요? 각 항 \( \dfrac{A_i}{1 - r_i x} \)는 16.1에서 본 등비급수 \( A_i \sum_n r_i^n x^n \)이기 때문입니다. 그래서 합쳐 놓은 \( x^n \) 계수도 “여러 등비수열의 합”으로 깔끔하게 떨어져요. 카운팅 결과를 풀어쓰는 닫힌 형태(closed form)가 곧장 튀어나옵니다.

16.4 선형점화식 풀기 Solving Linear Recurrences

드디어 이번 챕터의 하이라이트입니다. 선형점화식을 폐형으로 풀고 싶을 때 생성함수가 어떻게 작동하는지를 피보나치로 직접 따라가 봅시다.

피보나치 수열은 \( F_0 = 0,\ F_1 = 1 \), 그리고 \( n \ge 2 \)에 대해 \( F_n = F_{n-1} + F_{n-2} \)로 정의돼요. 이 수열의 생성함수를 \( F(x) = \sum_{n \ge 0} F_n x^n \)이라 두고, 점화식을 그대로 “함수의 식”으로 옮겨봅시다.

핵심 아이디어는 점화식 양변에 \( x^n \)을 곱하고 \( n \ge 2 \)에 대해 모두 더하는 것입니다. \[ \sum_{n \ge 2} F_n x^n = \sum_{n \ge 2} F_{n-1} x^n + \sum_{n \ge 2} F_{n-2} x^n. \] 좌변은 \( F(x) - F_0 - F_1 x = F(x) - x \). 우변 첫 항은 \( x \sum_{n \ge 2} F_{n-1} x^{n-1} = x(F(x) - F_0) = x F(x) \). 두 번째 항은 \( x^2 \sum_{n \ge 2} F_{n-2} x^{n-2} = x^2 F(x) \). 정리하면 \[ F(x) - x = x F(x) + x^2 F(x), \] \[ F(x)(1 - x - x^2) = x, \qquad F(x) = \frac{x}{1 - x - x^2}. \] 수열에 대한 점화식이 분모 한 줄짜리 닫힌 식으로 쪼그라들었어요.

점화식이 무리수와 거듭제곱으로 깔끔히 표현되는 게 신기하지 않나요. \( |\psi| < 1 \)이라 \( n \)이 커질수록 \( \psi^n \)은 0에 가까워지고, 결국 \( F_n \approx \phi^n / \sqrt{5} \)라는 황금비 성장률이 자연스럽게 따라옵니다. 일반적으로 “선형동차 점화식 → GF 분모는 다항식 → 부분분수 → 등비합”이라는 한 줄 파이프라인을 기억해 두면, 어지간한 점화식은 모두 같은 방식으로 닫힌 식이 나옵니다.

16.5 형식 멱급수 Formal Power Series

여태 계속 “수렴은 신경 안 써도 된다”라는 말을 흘려 왔는데, 이제 그 약속에 책임을 져야 할 때입니다. 핵심은 우리가 다루는 대상이 “함수”가 아니라 “수열에 가방을 씌운 형식적 표현”이라는 점이에요.

이렇게 정의하면 곱셈의 \( x^n \) 계수는 항상 유한 합이라 잘 정의됩니다. 즉 “무한히 더했는데 발산하면 어쩌지” 같은 걱정은 처음부터 발생할 자리가 없어요. \( \sum_{k=0}^n a_k b_{n-k} \)는 유한합이니까요.

그럼 \( \dfrac{1}{1-x} = \sum x^n \) 같은 등식의 의미는 뭘까요. 이건 “\( (1-x) \cdot \sum x^n = 1 \)”이라는 형식 곱 관계로 정의합니다. 좌변을 컨벌루션 정의대로 곱하면 정말 1만 남는다는 걸 손으로 확인할 수 있어요. 그러니까 \( 1/(1-x) \)는 “\( 1-x \)의 형식 곱 역원”이라는 뜻이지, “함수 \( x \mapsto 1/(1-x) \)와 일치한다”는 해석학적 주장이 아닙니다.

이 결과 덕분에 \( 1 - x - x^2 \) 같은 다항식도 형식 멱급수의 세계에서 안전하게 “나눌 수” 있고, 16.4에서처럼 \( \dfrac{x}{1-x-x^2} \)을 부담 없이 적을 수 있어요. 분모의 상수항이 0이 아니기 때문입니다.

마지막으로 형식적 미분도 짚고 넘어갑시다. 형식 도함수는 \( \dfrac{d}{dx}\sum a_n x^n = \sum n a_n x^{n-1} \)로 항별로 정의해요. 수렴이 어떻든 신경쓰지 않고요. 이 형식 도함수는 일반 함수 미분이 만족하는 곱 규칙, 합 규칙을 그대로 만족하기 때문에, 16.1의 \( \frac{1}{(1-x)^2} = \sum (n+1) x^n \) 같은 항등식을 “미분으로 유도”했을 때도 결과가 진짜로 옳다고 보장됩니다.

17.1 거래합시다 Let's Make a Deal

1970년대 미국의 게임쇼 Let's Make a Deal에서 진행자 몬티 홀이 던진 문제는 수학자들조차 한참을 다툰 사건이었습니다. 룰은 이렇습니다. 무대 위에 문이 세 개 있고, 그중 한 문 뒤에는 자동차가, 나머지 두 문 뒤에는 염소가 들어 있습니다. 참가자가 먼저 문 하나를 고릅니다. 그러면 진행자는 남은 두 문 중에서 염소가 있는 문 하나를 열어 보여줍니다. 진행자는 어느 문에 자동차가 있는지 알고 있고, 반드시 염소가 있는 문을 고른다는 점이 중요합니다. 그리고 참가자에게 묻습니다. 고른 문을 바꾸시겠습니까, 그대로 두시겠습니까?

여기서 많은 사람의 직관은 이렇게 말합니다. 이제 문이 두 개 남았으니 자동차가 있을 확률은 절반씩이지. 바꾸든 안 바꾸든 똑같다. 하지만 이 직관은 틀렸습니다. 바꾸면 자동차를 얻을 확률이 \( \tfrac{2}{3} \)이고, 그대로 두면 \( \tfrac{1}{3} \)에 머뭅니다. 두 배 차이가 납니다.

왜 이렇게 어긋날까요? 사람들은 흔히 지금 보이는 두 문만 바라보며 대칭성을 가정해 버립니다. 그러나 진행자가 문을 여는 행위는 단순히 정보를 지운 게 아니라, 자동차가 있는 문은 절대 열지 않는다는 규칙을 통해 정보를 적극적으로 전달한 행동입니다. 이 비대칭성을 잡아내는 방법이 있어야 합니다. 다음 절에서 살펴볼 4단계 방법이 바로 그 도구입니다.

17.2 4단계 방법 The Four Step Method

확률 문제를 안전하게 푸는 정형화된 절차가 있습니다. 단계를 통째로 외우는 게 아니라, 매번 같은 순서로 머리속을 정리하는 습관이라고 보시면 됩니다.

몬티홀에 적용해 봅시다. 자동차가 있는 문을 1, 2, 3 중 하나라 하고, 참가자가 처음 고른 문도 1, 2, 3 중 하나, 그리고 진행자가 여는 문도 1, 2, 3 중 하나입니다. 단순화를 위해 참가자는 항상 1번 문을 먼저 고른다고 합시다(대칭성 때문에 일반성을 잃지 않습니다).

1단계 — 표본공간. 두 단계 무작위 시행이 일어납니다. 첫째, 자동차가 1, 2, 3번 문 중 어디에 놓이는가. 둘째, 진행자가 어느 문을 여는가. 트리로 펼치면 결과는 다음과 같이 나옵니다.

  자동차 위치     진행자가 여는 문     결과
   1 (1/3) ───── 2 (1/2) ──────── (1, 2)
              └─ 3 (1/2) ──────── (1, 3)
   2 (1/3) ───── 3 (1) ────────── (2, 3)
   3 (1/3) ───── 2 (1) ────────── (3, 2)

참가자가 1번을 고른 상태에서, 자동차가 1번에 있을 때 진행자는 2번이나 3번 중 아무 데나 열 수 있으므로 각각 \( \tfrac{1}{2} \) 확률을 부여합니다. 자동차가 2번이라면 진행자는 반드시 3번을 열어야 하고(1번은 참가자가 골랐고 2번은 자동차이므로), 자동차가 3번이라면 반드시 2번을 엽니다.

2단계 — 결과 확률. 가지의 곱으로 각 결과의 확률을 매깁니다.

\( \Pr[(1,2)] = \tfrac{1}{3} \cdot \tfrac{1}{2} = \tfrac{1}{6} \), \( \Pr[(1,3)] = \tfrac{1}{6} \), \( \Pr[(2,3)] = \tfrac{1}{3} \), \( \Pr[(3,2)] = \tfrac{1}{3} \). 합은 \( 1 \)입니다.

3단계 — 사건. 우리가 알고 싶은 건 바꾸기 전략을 쓸 때 자동차를 얻는 사건입니다. 바꾸기 전략에선, 진행자가 연 문 말고 남은 다른 문으로 바꿉니다. 이 사건 \( W \)에 속하는 결과는 자동차가 1번이 아닐 때 모두입니다. 즉 \( W = \{(2,3), (3,2)\} \).

4단계 — 합산. \( \Pr[W] = \tfrac{1}{3} + \tfrac{1}{3} = \tfrac{2}{3} \). 끝입니다. 바꾸기 전략의 승률은 \( \tfrac{2}{3} \), 안 바꾸기 전략의 승률은 \( \tfrac{1}{3} \).

17.3 이상한 주사위 Strange Dice

주사위 세 개 \( A, B, C \)를 만들었다고 합시다. 보통 주사위가 아니라 면마다 다른 숫자가 적힌 특별한 주사위입니다. 두 사람이 각자 주사위를 굴려 더 큰 수가 나오는 쪽이 이깁니다. 이때 \( A \)가 \( B \)를 이길 확률이 절반을 넘는다를 \( A \succ B \)라고 적기로 합시다.

상식적으로는 이 관계가 추이적일 거라고 기대합니다. 즉 \( A \succ B \)이고 \( B \succ C \)이면 \( A \succ C \)일 거라고요. 가위바위보처럼 순환하는 일은 보통의 부등호에는 없으니까요. 그런데 잘 만든 주사위 세 개로는 \( A \succ B \succ C \succ A \)라는 가위바위보 같은 고리를 만들 수 있습니다. 이런 주사위를 비추이적 주사위라고 부릅니다.

왜 직관이 무너질까요? 우리는 주사위를 평균이 큰 쪽이 강한 주사위로 자동 환산하는데, 승률은 평균이 아니라 분포의 모양 전체에 의존합니다. \( A \)는 \( 9 \) 같은 큰 수에 무게가 실리지만 \( 4 \) 이하도 자주 나오고, \( B \)는 양극단 \( 1 \)과 \( 8 \)로 갈리며, \( C \)는 중간값을 모아둔 주사위입니다. 두 분포가 만났을 때 누가 자주 이기는가 하는 문제는 단일 숫자로 환원되지 않습니다.

17.4 생일 원리 The Birthday Principle

강의실에 학생 23명이 모여 있다고 합시다. 같은 생일을 가진 두 사람이 있을 확률이 얼마나 될까요? 직관은 365일 중 23명이라니, 너무 적다. 한 5%쯤?이라고 속삭이지만, 정답은 50%를 살짝 넘습니다. 학생이 23명만 모이면 이미 동률에 도달한다는 뜻입니다.

4단계 방법으로 풀어 봅시다. 표본공간은 23명 각자가 365일 중 하루를 균등하게 가질 모든 경우, 즉 \( S = [365]^{23} \)이고 결과는 길이 23인 튜플입니다. 각 결과에 동일 확률 \( 1 / 365^{23} \)을 부여합니다(단순화: 윤년·계절성 무시).

관심 사건 \( M \)은 두 명 이상이 같은 생일인 사건입니다. 이걸 직접 세기보다 여집합 \( \overline{M} \)인 모두가 다른 생일을 세는 게 훨씬 쉽습니다. 23명을 한 명씩 줄세워 생일을 정한다고 보면, 첫 사람은 365일 중 아무 날이나 가능, 두 번째는 364일, 셋째는 363일, ..., 23번째는 \( 365 - 22 = 343 \)일.

\[ \Pr[\overline{M}] = \frac{365 \cdot 364 \cdot 363 \cdots 343}{365^{23}} \approx 0.4927. \]

따라서 \( \Pr[M] = 1 - \Pr[\overline{M}] \approx 0.5073 \). 절반을 넘습니다.

일반화도 쉽습니다. 가능한 생일 종류가 \( N \)이고 사람이 \( n \)명일 때 충돌 확률이 \( \tfrac{1}{2} \)에 도달하는 \( n \)은 대략 \( n \approx 1.177 \sqrt{N} \)입니다. \( N = 365 \)면 \( n \approx 22.5 \), 우리가 본 23과 일치합니다. 핵심은 가능한 쌍의 수가 사람 수의 제곱으로 늘어난다는 점입니다.

17.5 집합론과 확률 Set Theory and Probability

지금까지 직관적으로 사용한 표본공간과 사건을 이제 집합론의 언어로 다시 깔끔하게 정리해 봅시다. 이게 확률공간(probability space)의 표준 정의입니다.

이렇게 보면 사건은 곧 부분집합이고, 사건들의 연산은 그대로 집합 연산입니다. \( A \) 또는 \( B \)가 일어남은 \( A \cup B \), 둘 다 일어남은 \( A \cap B \), \( A \)는 일어나지 않음은 여집합 \( \overline{A} = S \setminus A \). 집합 항등식이 곧 확률의 항등식이 되는 강력한 사전이 생기는 셈입니다.

합집합 경계는 거칠어 보여도 컴퓨터과학에서 가장 자주 등장하는 부등식 중 하나입니다. 가령 무작위 알고리즘이 \( m \)가지 나쁜 사건 중 어느 하나라도 발생하면 실패한다고 합시다. 각 나쁜 사건의 확률을 \( \tfrac{1}{m^2} \) 이하로 누를 수 있다면 합집합 경계로 전체 실패 확률은 \( \tfrac{1}{m} \)을 넘지 않습니다. 정확한 \( \Pr[A_i \cap A_j] \)을 몰라도 위쪽 경계만 잡고 안전하게 결론을 내릴 수 있는 도구입니다.

이렇게 사건을 집합으로, 확률을 측도로 보는 시점이 자리잡으면, 다음 챕터들에서 다룰 조건부 확률·독립성·기댓값·집중 부등식이 모두 같은 언어 위에서 자연스럽게 펼쳐집니다. 확률은 더 이상 감이 아니라, 우리가 5장과 8장에서 길러 온 집합과 합산의 도구를 그대로 다시 쓰는 분야가 되는 것입니다.

18.1 몬티홀의 혼란 Monty Hall Confusion

문 셋 중 하나 뒤에는 자동차가, 나머지 둘 뒤에는 염소가 있습니다. 참가자가 한 문을 고르면, 정답을 아는 사회자 몬티가 나머지 두 문 중 염소가 있는 문 하나를 열어 보여줍니다. 그리고 묻습니다. "바꾸시겠어요?" 직관은 "둘 중 하나니까 50:50, 바꾸나 안 바꾸나 똑같다"고 말합니다. 그런데 이게 틀렸어요. 바꾸면 \( 2/3 \), 안 바꾸면 \( 1/3 \) 입니다.

왜 직관이 무너질까요? 몬티가 문을 여는 행동이 정보를 뿌리기 때문입니다. 그는 무작위로 문을 열지 않고, "염소가 있고, 참가자가 고르지 않은" 문을 골라서 엽니다. 이 조건이 확률 분포를 비대칭으로 휘게 만들어요. 14장에서 이미 이 문제를 한 번 풀었지만, 그땐 표본공간을 직접 펼쳐서 셌습니다. 이번엔 더 강력한 도구로 봅니다.

몬티홀에서 "바꿨을 때 자동차를 얻을 확률"은 결국 "참가자가 처음에 염소를 골랐을 확률"과 같습니다. 처음 추측이 틀릴 확률 \( 2/3 \) 가 그대로 정답률로 돌아오는 거예요. 이 챕터를 마칠 즈음에는 이 한 줄이 자연스럽게 들리길 바랍니다.

18.2 정의와 표기 Definition and Notation

조건부 확률은 표기법부터 익숙해지면 좋아요. \( P(A \mid B) \) 는 "B가 일어났다는 가정 하에서 A의 확률"이고, 읽을 땐 "P of A given B"라고 합니다. 정의는 다음과 같습니다.

식의 모양을 직관적으로 풀어볼게요. 분모 \( P(B) \) 가 새로운 표본공간(B 안에서 다시 비율을 재겠다는 의미)이고, 분자 \( P(A \cap B) \) 가 그 안에서 A도 함께 일어나는 부분의 크기입니다. B를 새 1로 두고 거기서 A가 차지하는 비율을 다시 계산하는 셈이에요.

반대로 \( B' \) = "첫 번째가 1"로 바꾸면 \( P(B') = 1/6 \), \( P(A \cap B') = 1/36 \) 이라 \( P(A \mid B') = 1/6 \). 어, 또 같네요? 합이 7은 첫 번째 눈이 무엇이든 두 번째가 정확히 한 값으로 정해지므로 \( 1/6 \) 이 유지되는 거예요. 이런 부분이 확률의 재미있는 점입니다.

18.3 조건부 확률에서의 4단계 방법 The Four-Step Method for Conditional Probability

복잡한 확률 문제는 다음 4단계를 따라가면 거의 풀립니다. (1) 표본공간을 트리로 펼치기, (2) 각 가지에 결과 적기, (3) 가지마다 조건부확률 적기, (4) 묻는 사건의 확률을 더하기. 트리 다이어그램은 이 절차의 시각적 도구예요.

여기서 핵심은 가지에 적힌 숫자들이 모두 조건부확률이라는 사실이에요. "자동차가 1번이라는 조건 하에서 몬티가 2번을 열 확률은 \( 1/2 \)" 같은 식. 이 가지들을 곱해야 그 잎이 발생할 확률이 됩니다. 왜 곱셈이 맞는지는 다음 절에서 정당화합니다.

18.4 트리 다이어그램이 작동하는 이유 Why Tree Diagrams Work

트리에서 가지를 곱해 잎의 확률을 얻는 절차는, 사실 정의 18.2.1을 단순히 변형한 것입니다. 양변에 \( P(B) \) 를 곱하면

트리의 한 경로는 정확히 \( A_1 \cap A_2 \cap \dots \cap A_n \) 의 형태입니다. 첫 가지는 \( P(A_1) \), 그 다음 가지는 "\( A_1 \) 이 일어났다는 조건 하에서 \( A_2 \)" 즉 \( P(A_2 \mid A_1) \), 그 다음은 \( P(A_3 \mid A_1 \cap A_2) \), 이런 식이에요. 이 가지들을 다 곱하면 정확히 위 공식이 나옵니다.

트리는 그저 직관적인 그림이 아니라, 곱셈 규칙의 시각적 표현이에요. 어떤 복잡한 문제든 결과를 단계로 쪼갤 수 있다면 트리로 옮길 수 있고, 옮긴 순간 답은 산수 문제로 바뀝니다.

18.5 전확률 법칙 The Law of Total Probability

표본공간을 서로소인 사건들 \( B_1, B_2, \dots, B_n \) 으로 빈틈없이 쪼갤 수 있다면(이를 분할이라 합니다), 어떤 사건 \( A \) 의 확률은 각 조각을 통과하는 경로들의 합으로 적을 수 있어요.

이 식과 정의 18.2.1을 결합하면 그 유명한 베이즈 정리가 떨어집니다.

18.6 심슨의 역설 Simpson's Paradox

직관에 가장 통쾌한 한 방을 날리는 카드입니다. 두 그룹 각각에서 X가 Y보다 좋은데, 합치면 Y가 X보다 좋다. "어떻게 그럴 수가?" 싶지만, 실제 통계에서 자주 발생합니다.

의료 통계에서도 흔합니다. 신약이 모든 연령대에서 위약보다 잘 듣는데 전체로 보면 위약이 이기는 경우가 있어요. 연령대별 환자 수가 달라서요. 핵심 교훈: 조건부 확률을 통합할 땐 분할의 가중치를 함께 봐야 한다. \( P(A \mid B_1) > P(A' \mid B_1) \) 이고 \( P(A \mid B_2) > P(A' \mid B_2) \) 라 해도 가중치 \( P(B_i) \) 가 양쪽에서 다르면 \( P(A) \) 와 \( P(A') \) 의 부등호는 뒤집힐 수 있습니다.

18.7 독립 Independence

"정보를 받아도 확률이 안 바뀌는" 사건들을 독립이라고 합니다. 18.2의 주사위 예제에서 \( P(A \mid B) = P(A) \) 가 그런 경우였죠. 정의는 깔끔합니다.

"확률이 0인 사건은 어떻게 되나?" 같은 경계 사례를 깔끔히 처리하려고 곱 형태를 정의로 채택해요. 직관적으로 독립은 "한쪽이 일어났다는 사실이 다른 쪽의 분포에 아무 영향을 못 준다"는 의미입니다.

주의할 점: 서로소(disjoint)와 독립(independent)은 완전히 다른 개념입니다. 서로소면 \( P(A \cap B) = 0 \) 인데, \( A, B \) 가 둘 다 양의 확률이면 곱은 양수라 정의 18.7.1을 만족할 수 없어요. 서로소인 두 양수확률 사건은 절대 독립이 아닙니다.

18.8 상호 독립 Mutual Independence

여러 사건의 독립은 한 단계 더 까다롭습니다. 단순히 "두 개씩 짝지어 모두 독립"인 것(쌍별 독립, pairwise)과 "모든 부분집합이 독립"인 것(상호 독립, mutual)은 다릅니다.

쉽게 말해 쌍별 독립은 "어느 한 사건에 대한 정보로는 다른 한 사건을 못 맞추지만, 두 사건의 정보를 합치면 세 번째를 알 수도 있다"는 상황을 허용합니다. 진짜 독립을 원하면 부분집합 모두를 점검해야 해요.

18.9 확률 vs 신뢰도 Probability versus Confidence

마지막으로 철학적인 곁가지 하나. "동전을 던졌을 때 앞이 나올 확률 \( 1/2 \)"라는 말은 무슨 뜻일까요? 답이 둘로 갈립니다.

빈도주의(frequentist) 관점: 확률은 "장기적으로 같은 실험을 무한히 반복했을 때의 빈도"입니다. 앞면이 나올 확률이 \( 1/2 \) 라는 건 던지기를 무한히 하면 앞면 비율이 \( 1/2 \) 로 수렴한다는 뜻이에요. 이 관점에서 "내일 비올 확률이 30%"는 다소 어색합니다. 내일은 한 번뿐이라 빈도가 정의되지 않으니까요.

베이즈주의(Bayesian) 관점: 확률은 "관찰자의 신뢰도(degree of belief)"입니다. 30%란 "내가 가진 정보로 봤을 때 비가 올 거라는 믿음의 강도가 그 정도"라는 의미예요. 새 정보가 들어오면 베이즈 정리로 신뢰도를 업데이트합니다(사전 확률 → 사후 확률).

베이즈 정리를 다시 봅시다. \( P(B \mid A) = P(A \mid B) P(B) / P(A) \). 베이즈 관점에서 \( P(B) \) 는 사전 신뢰도(prior), \( P(B \mid A) \) 는 \( A \) 라는 증거를 본 뒤의 사후 신뢰도(posterior), \( P(A \mid B) \) 는 가설 \( B \) 가 데이터 \( A \) 를 얼마나 잘 설명하는지를 나타내는 가능도(likelihood)입니다. 이 세 단어는 통계학·머신러닝의 기본 어휘예요.

이 챕터에서 우리는 "정보가 들어오면 확률이 바뀐다"는 한 줄을 정의 18.2.1로 엄밀화하고, 그것이 트리·전확률·베이즈·심슨역설·독립 같은 풍성한 결과로 뻗어가는 모습을 봤습니다. 다음 챕터에서는 확률을 값으로 다루는 도구, 확률변수로 넘어갑니다. 이제 사건 단위가 아니라 숫자 단위로 확률을 보는 거예요.

19.1 확률변수 예 Random Variable Examples

표본공간 \(S\)가 정해졌다고 합시다. 우리는 결과 \(\omega \in S\) 하나하나에 어떤 실수를 대응시키고 싶어요. 예를 들어 동전 세 번을 던지는 실험이라면 결과는 HHT, THH 같은 문자열인데, 우리가 정말 알고 싶은 건 "앞면이 몇 번 나왔는가"라는 숫자입니다. 그러니 결과를 숫자로 보내주는 함수가 필요합니다.

이름은 "변수"지만, 실체는 함수입니다. 이게 처음 헷갈리는 부분이에요. 보통 변수라 하면 \(x = 3\) 같은 정해진 값이 떠오르지만, 확률변수 \(X\)는 "결과에 따라 다른 값을 내놓는 규칙"입니다. 결과 \(\omega\)가 정해지면 \(X(\omega)\)도 정해져요. 결과가 무작위니까 \(X\)의 값도 무작위가 됩니다.

한 가지 더 짚어둘 게 있어요. 같은 표본공간 위에 여러 확률변수를 동시에 정의할 수 있습니다. 주사위 두 개의 예에서 \(T\)는 합, \(D(\omega) = |i - j|\)는 차이의 절댓값, \(M(\omega) = \max(i,j)\)는 최댓값 — 이런 식으로 얼마든지요. 모두 같은 \(\omega\)에서 동시에 평가될 수 있고, 그래서 \(T\)와 \(M\)이 함께 어떻게 움직이는지(공분산 같은 것)를 따질 수 있게 됩니다.

19.2 독립 Independence

사건의 독립은 이미 봤어요: \(\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]\). 확률변수의 독립은 이것의 자연스러운 확장입니다. 두 확률변수가 독립이라는 건, 한쪽 값을 알아도 다른 쪽 값에 대한 우리 예측이 바뀌지 않는다는 뜻이에요.

독립은 좋은 성질이에요. 독립이면 결합 확률을 분해할 수 있고, 분산이 합으로 분리되고(20장에서 확인), 큰 수의 법칙·중심극한정리 같은 것이 깔끔하게 작동합니다. 그런데 한 가지 큰 사실: 기댓값의 선형성은 독립을 요구하지 않아요. 19.5절에서 다시 말씀드릴게요.

19.3 분포 함수 Distribution Functions

확률변수 \(X\)에 대해 우리가 알고 싶은 모든 정보는 결국 "\(X\)가 어떤 값을 얼마의 확률로 갖는가"로 요약됩니다. 이 정보를 담는 함수가 분포(distribution)예요. 이산확률변수에서는 두 가지 방식이 표준입니다.

PMF는 항상 \(\sum_x p_X(x) = 1\)을 만족하고 \(0 \le p_X(x) \le 1\)이어야 합니다. CDF는 비감소 함수이며 \(\lim_{x \to -\infty} F_X(x) = 0\), \(\lim_{x \to \infty} F_X(x) = 1\) 입니다. 자주 만나는 분포들을 정리해 둘게요.

19.4 큰 기대 Great Expectations

분포 전체를 볼 수 있다면 좋겠지만, 보통 우리는 그 분포를 한두 개의 숫자로 요약하고 싶어요. 그중 가장 중요한 게 기댓값(expected value), 즉 평균입니다. "이 확률변수의 값은 평균적으로 얼마쯤 될까?"에 답하는 양이에요.

기댓값은 결과별 가중평균이라는 점에서 무게중심으로 비유하면 좋아요. PMF를 막대그래프로 그렸을 때, 그 막대들의 균형점이 \(\mathrm{E}[X]\)입니다. 그래서 분포가 한쪽으로 치우치면 기댓값도 그쪽으로 끌려가요.

전체 기댓값 법칙은 "어떤 분기마다 평균이 얼마인지를 알면, 분기 확률로 가중해서 전체 평균을 얻는다"는, 매우 자연스러운 사실입니다. 어려운 기댓값을 작은 케이스로 쪼개 푸는 표준 도구예요.

19.5 기댓값의 선형성 Linearity of Expectation

이제 이 챕터에서 가장 강력한 정리, 그리고 거의 마법처럼 작동하는 도구를 소개합니다.

증명은 한 줄짜리예요. 그런데 응용은 정말 풍성합니다. 핵심 패턴은 이래요: 복잡해 보이는 확률변수 \(X\)를 단순한 인디케이터들의 합 \(X = I_1 + I_2 + \cdots + I_n\)으로 쓸 수 있으면, 선형성으로 \(\mathrm{E}[X] = \sum_i \mathrm{E}[I_i] = \sum_i \Pr[A_i]\)가 됩니다. 분포 전체를 알 필요 없이 각 사건의 확률만 알면 평균이 나오는 거예요.

19.6 정말 큰 기대 Really Great Expectations

기댓값이 늘 단순한 가중평균처럼 행동하는 건 아니에요. 합이 무한급수가 되거나, 음·양의 값이 섞이거나, 조건부로 다시 쓸 때 미묘한 일들이 벌어집니다. 이 절에서는 그런 두 가지 사례를 다뤄볼게요.

그럼에도 불구하고 기댓값과 그 선형성은 조합론, 알고리즘, 그리고 일상의 의사결정에 끊임없이 등장하는 도구입니다. 인디케이터 트릭은 한 번 익숙해지면 거의 모든 "평균 ~ 의 개수" 문제에 통하는 만능 열쇠예요. 다음 챕터에서는 평균만으로는 부족할 때 — 즉, 평균에서 얼마나 벗어나는지를 측정하는 분산과 편차 부등식들 — 을 다루겠습니다.

20.1 마르코프 부등식 Markov's Theorem

여러분이 어느 빵집의 일일 매출 데이터를 받았다고 합시다. 일일 매출의 평균이 100만 원이라는 사실 하나만 알 때, "어느 날의 매출이 1000만 원을 넘을 확률"에 대해 무슨 말을 할 수 있을까요? 매출의 분포 모양을 모르므로 정확한 값은 못 구합니다. 그래도 "그런 일은 자주 못 일어난다"는 직관은 분명히 있어요. 평균이 100만 원인데 매일 1000만 원씩 찍히면 평균이 그렇게 작을 리가 없잖아요. 마르코프 부등식은 바로 이 직관을 식 한 줄로 굳힌 것입니다.

20.2 체비셰프 부등식 Chebyshev's Theorem

마르코프는 평균만 알 때 쓰는 도구였습니다. 만약 평균뿐 아니라 "값이 평균에서 얼마나 흩어져 있는지"까지 안다면 어떨까요? 흩어짐을 잰 양이 분산입니다. 분산이 작으면 변수는 평균 근처에 빽빽하게 몰려 있을 거고, 분산이 크면 사방으로 퍼져 있겠죠. 체비셰프 부등식은 이 직관을 살짝 더 정량적으로 다듬은 결과입니다.

20.3 분산의 성질 Properties of Variance

분산을 "정의대로" 매번 \( \mathrm{E}[(X-\mu)^2] \)로 계산하는 건 불편합니다. 두 가지 도구를 갖춰 두면 한결 빨라져요. 하나는 분산을 다른 형태로 풀어 쓰는 항등식, 또 하나는 합의 분산을 합으로 나누는 법칙입니다.

20.4 무작위 표본 추정 Estimation by Random Sampling

실제 응용에서 우리는 모집단 전체를 관찰하지 못합니다. 대신 일부를 무작위로 골라 평균을 재고, 그 표본 평균이 모평균에 얼마나 가까운지 추정해야 해요. 여론조사, A/B 테스트, 몬테카를로 시뮬레이션 모두 똑같은 구조입니다. 이 절에서는 체비셰프를 이용해 "표본을 몇 개 뽑아야 충분한가"를 답하는 가장 단순한 방법을 살펴봅니다.

모집단에서 같은 분포로 독립적으로 뽑은 표본을 \( X_1, X_2, \ldots, X_n \)이라 합시다. 모평균은 \( \mu \), 모분산은 \( \sigma^2 \). 표본 평균은 \[ \bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i. \] 이 \( \bar{X}_n \) 자체가 확률변수예요. 우리는 이 새로운 변수의 평균과 분산을 이미 가진 도구로 계산할 수 있습니다.

중요한 포인트는 표본 평균의 표준편차가 \( \sigma/\sqrt{n} \)으로 줄어든다는 것입니다. 표본을 100배로 늘려도 정확도는 10배밖에 좋아지지 않아요. 이 "1/제곱근" 비율이 통계학 비용 구조의 본질입니다.

20.5 확률변수의 합과 큰 수의 법칙 Sums of Random Variables

지난 절들에서 우리는 두 가지 사실을 모았습니다. 첫째, 독립합의 분산은 분산의 합이다. 둘째, 표본 평균의 분산은 \( \sigma^2/n \)이다. 이 두 도구만 가지고도 확률론에서 가장 유명한 정리 중 하나인 "큰 수의 법칙"의 약한 형태를 단단하게 증명할 수 있어요. 이름이 거창해서 어려워 보이지만, 본질은 한 줄입니다. "표본을 충분히 모으면 표본 평균은 모평균에 거의 확실하게 가깝다."

증명 한 줄이 너무 짧아 보일지도 모르지만, 그 한 줄을 가능하게 한 인프라는 결코 짧지 않았어요. 기댓값의 선형성, 독립합의 분산, 분산의 계산식, 마르코프, 체비셰프, 표본 평균의 분산 공식 — 이 모든 부품이 있어야 마지막 한 줄이 의미를 가집니다. 책의 한 챕터가 어떻게 모여 큰 정리를 받쳐 주는지 보여주는 좋은 예시예요.

21.1 도박꾼의 파산 Gambler's Ruin

장면을 하나 그려봅시다. 카지노에 들어선 도박꾼이 처음에 \( n \)달러를 가지고 있어요. 매 라운드마다 동전을 던져 앞면이면 1달러를 따고, 뒷면이면 1달러를 잃습니다. 도박꾼은 가진 돈이 \( T \)달러가 되면 의기양양하게 자리를 뜨겠다고 다짐했지만, 반대로 0달러가 되면 어쩔 수 없이 자리를 떠야 해요. 자, 그가 목표 \( T \)달러에 도달할 확률은 얼마일까요? 그리고 게임이 끝날 때까지 평균 몇 라운드를 버틸 수 있을까요?

이 문제를 도박꾼의 파산이라고 부르는데요, 18세기부터 사람들이 골머리를 앓아 온 고전 문제입니다. 표면적으로는 도박 이야기지만, 사실은 1차원 격자 위 임의 보행의 가장 깔끔한 형태예요. 정수 직선 위 \( n \)에서 출발해 매 단계마다 \( +1 \) 또는 \( -1 \)을 더하며 움직이고, 0이나 \( T \)에 닿으면 멈추는 거죠.

직관적으로 \( p \)가 \( 1/2 \)에 가까우면 양쪽으로 비슷하게 흔들리니까 도박꾼이 살아날 가능성도 한가운데서 \( n/T \)쯤 될 것 같죠. 반대로 \( p < 1/2 \)인 약간 불공정한 게임이라면 카지노가 점점 도박꾼의 돈을 빨아들일 거고, \( p > 1/2 \)이면 도박꾼이 유리할 거예요. 이 직관을 정확한 식으로 만들어 봅시다.

점화식으로 파산 확률 풀기

핵심 아이디어는 한 걸음 조건부 분석(one-step conditioning)이에요. 도박꾼이 현재 \( n \)달러를 가지고 있을 때 목표를 달성할 확률을 \( w_n \)이라고 합시다. 첫 번째 동전을 던진 직후를 보면, 이전과 같은 모양의 게임이 약간 다른 자본금에서 시작됩니다. 그러니

\[ w_n = p \cdot w_{n+1} + q \cdot w_{n-1}, \qquad 1 \le n \le T-1 \]

이 됩니다. 경계조건은 \( w_0 = 0 \) (이미 파산), \( w_T = 1 \) (이미 우승)이고요. 이건 우리가 이전 챕터에서 봤던 선형 점화식이에요. 일반 해를 찾아봅시다.

기대 시간: 게임은 얼마나 길까?

파산 확률을 알았으니 이제 게임의 길이도 따져봅시다. 시작 자본이 \( n \)일 때 게임이 끝날 때까지 걸리는 기대 라운드 수를 \( e_n \)이라고 둘게요. 같은 한 걸음 분석으로

\[ e_n = 1 + p \, e_{n+1} + q \, e_{n-1}, \qquad 1 \le n \le T-1, \]

\( e_0 = e_T = 0 \). 첫 번째 동전 한 번을 항상 더해주는 게 핵심이에요. 이 점화식의 동차부분은 위와 같고, 비동차항이 상수 \( -1 \)이라 특수해를 따로 잡아야 해요.

특히 공정한 게임에서 \( T = 100 \), \( n = 50 \)이면 평균 \( 50 \cdot 50 = 2500 \)라운드. \( T = 1000 \), \( n = 500 \)이면 평균 25만 라운드! 한가운데서 시작한 임의 보행이 한쪽 끝에 닿기까지 평균적으로 \( T^2 \) 정도 시간이 걸린다는 건, 임의 보행이 느리다는 의미예요. 거리에 비해 제곱만큼 시간이 든다는 \( \sqrt{t} \)–법칙은 확산(diffusion)의 본질이고, 브라운 운동이나 열 방정식과 같은 뿌리에서 자라난 결과입니다.

도박꾼의 파산은 단지 도박 이야기가 아니에요. 같은 점화식이 화학에서 분자가 막 사이를 통과할 확률, 신경과학에서 뉴런의 발화 임계값 도달 확률, 알고리즘에서 SAT 해법의 임의 재시작 분석에 등장합니다. "확률적인 한 걸음을 반복했을 때 어디서 멈추나"라는 질문은 정말 어디에나 있어요.

21.2 그래프 위 임의 보행 Random Walks on Graphs

직선 위에서 좌우로만 움직이는 보행은 너무 평면적이에요. 실제로 우리가 흥미로운 구조 — 소셜 네트워크, 도시 도로망, 웹 페이지의 하이퍼링크 — 는 그래프 모양이거든요. 그래서 임의 보행을 그래프로 일반화해 봅시다.

이 과정은 사실 마르코프 연쇄(Markov chain)의 한 종류예요. 다음 위치 \( v_{t+1} \)이 과거 전체가 아니라 오직 현재 \( v_t \)에만 의존하니까요. 전이 확률 행렬 \( P \)는 \( P_{uv} = 1/\deg(u) \)이면 \( v \in N(u) \), 아니면 0입니다.

평형 분포: 어디에 가장 오래 머무는가

충분히 오랫동안 임의 보행을 돌리면, 시작 위치는 잊혀지고 어떤 안정된 분포 \( \pi \)로 수렴해요. 무방향 연결 그래프에서 비주기적이면(예컨대 자기 자신으로 가는 변이 하나라도 있거나 홀수 사이클이 있으면) 이 평형 분포는 차수에 비례합니다.

이 결과가 의미하는 바는 단순해요. 이웃이 많은 정점일수록 보행자가 그곳에서 더 많은 시간을 보낸다. 차수가 평형 확률을 결정하고요. 그래프에서 "중요한 정점"을 이웃 수로 정의해도 된다는 첫 신호입니다. 하지만 웹 같은 방향 그래프에서는 이 깔끔한 차수 비례 공식이 그대로 통하지 않아요. 그래서 등장한 게 PageRank입니다.

PageRank: 임의 보행으로 검색을 풀다

1998년 스탠퍼드 박사과정생 두 명, 래리 페이지와 세르게이 브린이 풀고 싶었던 문제는 이거였어요. "웹 페이지가 수십억 개 있다. 검색어가 들어왔을 때 어떤 페이지를 가장 위에 띄울 것인가?" 단순히 "검색어가 등장한 횟수"로 정렬하면 키워드 스팸이 판칠 거고요. 그들의 통찰은 이거였죠. 웹은 거대한 방향 그래프다. 페이지가 페이지를 링크한다는 건 일종의 추천이다. 추천을 많이 받는 페이지가 중요하다. 그런데 추천하는 페이지 자체가 중요할 때 그 추천이 더 무겁다.

이 재귀적 정의를 어떻게 풀까요? 답은 우아하게도 임의 보행이에요. 어떤 가상의 서퍼가 임의의 페이지에서 출발해, 매 단계마다 현재 페이지의 외부 링크 중 하나를 균등하게 골라 클릭한다고 합시다. 이 서퍼가 충분히 오래 떠돌면 어떤 페이지에 머물 확률 분포가 평형을 이루는데, 그 평형 확률이 곧 그 페이지의 중요도입니다. 즉 임의 보행이 오래 머무는 페이지가 중요한 페이지예요.

식을 보면 핵심이 보여요. 페이지 \( v \)의 점수는 \( v \)로 링크를 거는 페이지들이 자기 점수를 자기의 외부 링크 수만큼 나눠서 \( v \)에 보태주는 합입니다. 큰 사이트가 적은 외부 링크로 \( v \)를 가리키면 점수가 크게 옮겨오고, 외부 링크가 산만하게 많은 페이지가 \( v \)를 가리키면 조금만 옮겨와요. 추천하는 사람이 신뢰할 만하고, 또 신중할수록 추천이 무겁다는 직관이 그대로 식이 된 것이죠.

어떻게 계산하느냐고요? 방법은 놀랍게도 단순합니다. 모든 \( \pi(v) \)를 \( 1/|V| \)로 초기화한 뒤, 위의 식을 우변에서 좌변으로 반복 대입합니다 — 이걸 거듭제곱 반복(power iteration)이라고 불러요. 수십 번 반복이면 수렴합니다. 1998년 당시 웹 페이지가 수억 개였는데도 이 방법이 통했다는 게 PageRank의 공학적 묘미예요.

PageRank의 진정한 천재성은 검색 결과를 전역적으로 정렬할 점수를 검색어와 무관하게 미리 계산해 둘 수 있다는 거예요. 사용자가 검색어를 입력하면 해당 검색어에 부합하는 페이지들 중 PageRank가 높은 순서로 보여주면 그만이거든요. "임의 보행의 평형 분포"라는 한 줄짜리 수학적 객체가 검색 엔진을 살리고 구글이라는 회사를 만들어낸 셈이에요.

22.1 하노이의 탑 The Towers of Hanoi

점화식 이야기를 시작할 때 거의 모든 교재가 꺼내드는 단골손님이 있습니다. 바로 하노이의 탑입니다. 세 개의 막대 \( A, B, C \)가 있고, 막대 \( A \)에 크기가 서로 다른 원반 \( n \)개가 큰 것이 아래, 작은 것이 위로 쌓여 있어요. 우리는 이 원반들을 모두 막대 \( C \)로 옮겨야 합니다. 단, 규칙이 있습니다.

• 한 번에 원반은 하나만 움직일 수 있다.
• 큰 원반을 작은 원반 위에 올릴 수 없다.

이 문제의 매력은, 답을 머리로 풀려고 하면 금방 막히는데 재귀로 풀면 거짓말처럼 풀린다는 점입니다. 한번 같이 따라가 봐요.

핵심 아이디어는 이렇습니다. \( n \)개를 \( A \to C \)로 옮기고 싶으면, 먼저 위쪽 \( n-1 \)개를 \( A \to B \)로 옮긴 다음, 가장 큰 \( n \)번 원반을 \( A \to C \)로 옮기고, 마지막으로 \( B \)에 쌓아둔 \( n-1 \)개를 \( B \to C \)로 옮기면 됩니다. 큰 원반은 깔개 역할만 하므로 작은 원반들의 이동을 방해하지 않아요.

초기                  중간                  최종
 |       |       |     |       |       |     |       |       |
 _       |       |     |       |       |     |       |       _
__       |       |     |       _       |     |       |       __
___      |       |     |       __      |     |       |       ___
A        B       C     A       B       C     A       B       C
    

이 전략을 비용으로 바꿔 적으면 점화식이 됩니다. \( n \)개를 옮기는 데 필요한 최소 이동 횟수를 \( T(n) \)이라 하면, 위 절차에서 우리는 \( n-1 \)개 옮기기를 두 번, 그리고 가장 큰 원반 한 번을 옮깁니다.

점화식이 있으면 작은 값부터 직접 계산해 볼 수 있어요. \( T(0)=0,\; T(1)=1,\; T(2)=3,\; T(3)=7,\; T(4)=15,\; T(5)=31 \). 패턴이 보이나요? 1씩 더하면 모두 2의 거듭제곱입니다. 그럼 한번 추측해 봅시다. \( T(n) = 2^n - 1 \).

여담으로, 전설에 따르면 64개 원반을 어떤 사원의 승려들이 옮기고 있다고 합니다. 1초에 한 번씩 옮긴다 해도 \( 2^{64}-1 \approx 1.8 \times 10^{19} \)초, 약 5849억년이 걸립니다. 우주의 나이보다 훨씬 길죠. 알고리즘 시간복잡도가 왜 중요한지 이보다 직관적인 예가 있을까요.

def hanoi(n, src, via, dst):
    if n == 0: return
    hanoi(n-1, src, dst, via)
    print(f"{src} -> {dst}")
    hanoi(n-1, via, src, dst)

22.2 합병 정렬 Merge Sort

이제 좀 더 실용적인 친구를 봅시다. 합병 정렬(merge sort)은 \( n \)개의 원소를 정렬할 때, 배열을 절반으로 나눠 각각 정렬한 뒤 두 정렬된 부분을 합쳐 하나로 만드는 알고리즘이에요. 이 "나눠서 풀고 합친다"는 패턴이 바로 분할정복(divide-and-conquer)입니다.

비용을 \( T(n) \)이라 하면, 길이 \( n \) 배열에서 합병 정렬은 다음 일을 합니다.

1. 길이 \( n/2 \)짜리를 두 번 정렬: 비용 \( 2T(n/2) \).
2. 두 정렬된 배열을 하나로 합치는 merge: 비용 \( \Theta(n) \) (양쪽 끝에서 작은 쪽을 한 번씩 뽑아내며 \( n \)개 다 채우면 끝).

이 점화식을 손으로 풀어 봅시다. 가장 단순한 방법은 펼쳐쓰기(unrolling)입니다. 한 단계씩 안쪽으로 들어가면서 식을 풀어 보면,

\[ T(n) = 2T(n/2) + n = 2\big(2T(n/4) + n/2\big) + n = 4T(n/4) + 2n. \]

한 번 더 펼치면 \( 8T(n/8) + 3n \). \( k \)번 펼치면 \( 2^k T(n/2^k) + k\,n \). 이제 \( n/2^k = 1 \)이 될 때까지, 즉 \( k = \log_2 n \)까지 가면,

\[ T(n) = 2^{\log_2 n}\, T(1) + (\log_2 n)\, n = n \cdot 0 + n \log_2 n = n \log_2 n. \]

같은 결과를 그림으로도 볼 수 있어요. 재귀 트리(recursion tree)를 그려 봅시다. 루트에서 비용 \( n \), 다음 층에 비용 \( n/2 \)인 노드 두 개(합 \( n \)), 그 다음에 \( n/4 \)인 노드 네 개(합 \( n \))… 층마다 합이 \( n \)인 게 핵심입니다. 트리의 높이는 \( \log_2 n \)이므로 전체 비용은 \( n \log_2 n \).

            n            ← n
          /   \
        n/2    n/2        ← n
       / \    / \
     n/4 n/4 n/4 n/4      ← n
      ...                 ← ...
      1 1 1 ... 1         ← n  (leaves: 총 n개)
    높이 log₂ n
    

22.3 선형 점화식 Linear Recurrences

하노이는 \( T(n) = 2T(n-1)+1 \), 합병 정렬은 \( T(n) = 2T(n/2) + n \). 둘 다 자기 자신을 다시 부르지만, 부르는 방식이 다릅니다. 이 절에서는 첫 번째 종류, 즉 입력 크기를 상수만큼 줄이는 점화식을 정리합니다. 일반적으로 모양은

\[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_d a_{n-d} + f(n) \]

이고, 계수 \( c_i \)가 상수일 때 이를 상수계수 선형 점화식이라고 합니다. \( f(n)=0 \)이면 동차(homogeneous), 아니면 비동차(inhomogeneous)입니다.

특성근을 \( r_1, \ldots, r_d \)라 하고 모두 다르다면, 일반해는 이들의 선형결합입니다.

\[ a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_d r_d^n. \]

계수 \( \alpha_i \)는 초기조건(\( a_0, a_1, \ldots \))을 대입해 연립방정식으로 정합니다. 만약 어떤 근 \( r \)이 중근이라면 \( r^n,\, n r^n,\, n^2 r^n,\ldots \) 식으로 \( n \)을 곱한 항들을 추가해 주면 됩니다.

비동차 항 \( f(n) \)이 있을 때는 두 단계로 나눕니다. 먼저 동차 부분의 일반해 \( a_n^{(h)} \)를 구하고, \( f(n) \)에 어울리는 특수해 \( a_n^{(p)} \)를 추측해서 대입해 본 뒤, 둘을 더한 \( a_n = a_n^{(h)} + a_n^{(p)} \)로 일반해를 만듭니다.

22.4 분할정복 점화식 Divide-and-Conquer Recurrences

합병 정렬 같은 알고리즘의 비용은 일반적으로 다음 모양을 합니다.

\[ T(n) = a\,T(n/b) + f(n), \]

여기서 \( a \ge 1 \)은 부분문제 개수, \( b > 1 \)은 크기 축소 비율, \( f(n) \)은 분할과 결합에 드는 비용이에요. 이런 점화식의 차수를 한 방에 알려주는 도구가 바로 마스터 정리(Master Theorem)입니다.

왜 이런 모양이 나오는지 직관은 재귀 트리에 있습니다. 트리의 높이는 \( \log_b n \), \( k \)번째 층에는 노드가 \( a^k \)개, 각 노드의 비용이 \( f(n/b^k) \)예요. 잎의 개수는 \( a^{\log_b n} = n^{\log_b a} \). 따라서 비용이 어디에 몰리는지가 차수를 결정합니다.

• 경우 1: 잎 쪽이 무겁다. 합병 비용이 작아 잎이 비용을 지배 → \( n^{\log_b a} \).
• 경우 2: 모든 층이 비슷하게 무겁다. 층마다 \( \Theta(n^{\log_b a}) \), 층이 \( \log n \)개 → \( n^{\log_b a} \log n \).
• 경우 3: 루트 쪽이 무겁다. 루트의 \( f(n) \)이 비용을 지배 → \( f(n) \).

22.5 점화식 감각 익히기 A Feel for Recurrences

점화식을 잘 다루는 사람은 정리 하나를 외우고 있는 사람이 아니라, 답의 모양을 빠르게 추측하고 검증하는 사람입니다. 이 절에서는 그 감각을 위한 세 가지 도구를 정리합니다.

(1) 펼쳐쓰기(unrolling). 점화식을 한두 단계 풀어쓰고 패턴을 찾는 방법이에요. 22.2절에서 \( T(n) = 2T(n/2)+n \)을 펼쳐 \( 2^k T(n/2^k) + kn \) 꼴을 얻은 게 전형적인 예입니다. 일반항을 추측한 뒤, 귀납법으로 검증하면 끝.

(2) 재귀 트리(recursion tree). 부분문제를 트리로 그리고, 층별 비용을 합산하는 방법. 분할정복 점화식의 직관은 거의 항상 트리에서 옵니다. 마스터 정리의 세 경우도 결국 "어느 층이 비용을 지배하는가?"의 트리적 표현이에요.

(3) 추측-검증(guess and verify). 답이 \( O(n \log n) \)일 거라고 추측한 뒤, 강한 귀납법으로 \( T(n) \le c\,n \log n \)을 직접 증명하는 방법. 이걸 치환법(substitution method)이라고도 부릅니다. 추측만 적당히 하면 거의 모든 점화식을 잡을 수 있어요.

마지막으로 점화식을 만났을 때 머릿속에 둘 만한 실전 팁입니다.

• 점화식을 보자마자 "크기를 어떻게 줄이는가"를 묻자. \( n-1 \)인지, \( n/b \)인지에 따라 도구가 달라진다.
• 크기가 상수만큼 줄면(예: \( T(n)=T(n-1)+\cdots \)) 선형 점화식 도구(특성방정식)를 시도.
• 크기가 비율로 줄면(예: \( T(n)=aT(n/b)+f(n) \)) 마스터 정리부터 본다.
• 마스터 정리가 안 되면 재귀 트리를 그려본다. 거의 항상 답이 보인다.
• 그래도 안 풀리면 답의 형태를 추측하고 치환법으로 검증한다.
• 작은 \( n \)에 대해 직접 계산해 보고 OEIS(온라인 정수수열 사전)에 검색해 보는 것도 의외로 빠른 길이다.