글 목록
- 추가 설명 — 되짚기는 길 하나가 아니라 영역을 준다
편집 거리의 표는 최솟값만 담는다. 표를 거꾸로 읽어 연산을 복원하면 최선의 길이 여럿일 수 있고, 그래서 결과는 길 하나가 아니라 표 위의 영역이 된다.
- 편집 거리 — 비슷하다는 말을 수로 바꾸기
자리끼리만 맞추는 Hamming 거리는 글자 하나가 빠지면 뒤가 전부 밀려 무너진다. 빈 칸을 허용해 정의한 편집 거리를 표 하나로 채우고, O(NM)보다 빠를 수 없다는 말의 정확한 뜻까지 짚는다.
- 플로이드·워셜의 메모리 줄이기 — N³칸에서 N²칸으로
플로이드·워셜은 D[k][i][j]로 N³칸을 쓴다. k를 계산할 때 k-1층만 참조한다는 점에서 2층으로 줄이고, D^{k-1}[i][k]와 D^k[i][k]가 같다는 것을 보여 1층으로 줄인다. 덮어써도 답이 변하지 않는 이유를 증명한다.
- 모든 쌍 최단 거리 — 다익스트라 N번과 플로이드·워셜
한 시작점이 아니라 모든 노드 쌍의 최단 거리를 구한다. 다익스트라를 N번 돌리는 기준선을 세우고, 경유할 수 있는 노드를 {1..k}로 제한해 k를 늘려 가는 플로이드·워셜을 유도한다. 점화식 D^k[i][j]=min(D^{k-1}[i][j], D^{k-1}[i][k]+D^{k-1}[k][j])가 왜 성립하는지 양방향으로 증명한다.
- 추가 설명 — 왜 이어 붙이는 것이 최선인가
최대 부분배열의 갱신식은 '앞부분의 최선은 kⱼ' 라는 한 줄을 당연하게 쓴다. 그 한 줄을 후보끼리의 1:1 대응으로 증명하고, 누적합에서 지금까지의 최소를 빼는 다른 풀이가 사실 같은 값을 계산한다는 것까지 보인다.
- 최대 부분배열 — 자리마다 최선 하나만 들고 간다
합이 가장 큰 연속 구간을 찾는 문제를 세 번 푼다. 모든 구간을 세면 O(N³), 누적합을 미리 만들면 O(N²), 각 자리에서 끝나는 최선의 합 하나만 들고 가면 O(N)이다. 빈 배열을 답으로 허용하느냐가 점화식을 어떻게 바꾸는지까지 본다.
- 추가 설명 — 어떤 순서로 곱했는지 되짚기
동적 계획법 ③의 표는 최소 비용만 담는다. 어떤 괄호 순서로 곱해야 그 비용이 나오는지는 표에 없다. 채우는 동안 이긴 분할점 k를 함께 적어 두면 (1,n)에서 재귀로 (M₁(M₂M₃)) 같은 괄호화를 복원한다. d=[3,2,4,2] 예시로 되짚고, 파스 트리와 동점의 미묘함까지 짚는다.
- 동적 계획법 ③ — 구간을 어디서 자를 것인가
행렬 M₁×…×Mₙ을 곱할 때 결과는 같아도 곱셈 횟수는 괄호를 어디에 치느냐로 달라진다. (3×2)(2×4)(4×2)는 48번 대 28번. '이 구간의 마지막 곱을 어디서 하는가'라는 결정에서 M[i,j]=minₖ(M[i,k]+M[k+1,j]+d_{i-1}d_k d_j)를 세우고, 짧은 구간부터 채워 O(n³)에 푼다. dp-2의 결정 사고를 원소에서 구간으로 확장한다.
- 추가 설명 — 어느 날을 골랐는지 되짚기
동적 계획법 ②의 표는 최댓값만 담는다. 채운 표를 마지막 칸부터 거꾸로 읽으면 어느 날을 골랐는지도 복원된다. a=[3,5,6,10] 예시로 직접 되짚고, 되짚기를 코드로 옮긴 뒤 동점 처리의 미묘함까지 짚는다.
- 동적 계획법 ② — 점화식은 어떻게 세우는가
날마다 일급이 다르고 연속된 날엔 일할 수 없을 때 총 일급을 최대화한다. '최적해가 마지막 날을 포함하는가?'라는 결정 하나에서 S(n)=max(S(n-1), S(n-2)+aₙ)을 유도하고, 상향식으로 O(n)에 푼다. DP①이 점화식을 계산했다면 ②는 점화식을 세운다.
- 카라츠바 알고리즘 — n자리 곱셈은 n²보다 빠를 수 있다
n자리 두 수를 곱하는 데 정의대로면 Θ(n²)이 든다. 반으로 잘라 재귀해도 곱셈이 4번이라 여전히 n²이다. 카라츠바는 (x₁+x₂)(y₁+y₂) 하나로 곱을 3번으로 줄여 Θ(n^1.585)를 얻는다. Strassen의 8→7과 같은 구조를, 한 단계 더 단순한 무대에서 본다.
- 동적 계획법 ① — 피보나치로 배우는 재귀·메모이제이션·DP
피보나치를 세 방법으로 푼다. 정의 그대로의 재귀는 같은 부분 문제를 지수 번 다시 풀어 O(2^n)에 가깝다. 계산한 값을 적어 두는 메모이제이션은 O(N)으로 줄인다. 채우는 순서까지 알면 재귀 없이 상향식으로 채우는 동적 계획법이 된다.
- 추가 설명 — Strassen의 7은 어디서 왔고, 왜 최소인가
Strassen의 7개 곱은 어디서 왔을까. '곱셈 한 번'을 이중선형 곱으로 다시 보면 최소 곱셈 수는 그 사상의 랭크가 된다. 복소수 곱을 3번으로 줄이는 가우스의 요령을 발판 삼아 2×2 행렬 곱의 랭크가 정확히 7(6은 불가능)임을 보인다.
- 행렬 곱셈 — 나누기만으로는 못 이긴다, Strassen이 곱을 줄이는 법
N×N 행렬 곱은 정의대로면 O(N³)이다. 2×2 블록으로 나눠 재귀해도 곱셈이 8번이라 여전히 N³이다. Strassen은 곱셈을 7번으로 줄여 O(N^2.807)을 얻는다. 왜 지수가 바뀌는지, 7개의 곱이 답을 재구성하는지 검증한다.
- 추가 설명 — 평행한 변이 만드는 동률과 대척점 쌍 열거
볼록 껍질 ⑤의 Rotating Calipers 뼈대는 평행한 변이 있어도 지름 값이 옳다. 이 글은 대척점 쌍 열거가 왜 별개 문제인지, 평행한 변이 만드는 동률과 교차 쌍을 어떻게 채우는지를 다룬다. 완전성(빠짐없음)은 얻되 유일성(중복 없음)은 얻지 못하며, 그 차이가 어디서 오는지까지 밝힌다.
- 볼록 껍질 ⑤ — 가장 먼 두 점과 Rotating Calipers
볼록 껍질을 도구로 써서 평면의 가장 먼 두 점(지름)을 찾는다. 가장 먼 쌍은 껍질 꼭짓점이며, 평행선을 돌리며 대척점 쌍만 훑는 Rotating Calipers로 모든 쌍 O(N²) 대신 O(N)에 얻는다.
- 볼록 껍질 ④ — 분할 정복과 공통 접선
점들을 절반으로 갈라 각각의 껍질을 재귀로 구한 뒤 공통 접선(common tangent)으로 잇는 분할 정복을 다룬다. 접선을 O(N)에 찾는 선형 워킹을 증명까지 따라가고, 이진 탐색을 겹쳐 O(log²N)으로 줄이는 아이디어와 그 아이디어가 아직 채우지 못한 부분을 밝힌다.
- 추가 설명 — 균형 트리에서 접선을 O(log N)에 찾기
볼록 껍질 ③이 미뤄둔 부분. x좌표로 정렬된 볼록 사슬을 균형 트리에 담아, 외부 점에서 그은 접선의 접점을 O(log N)에 찾는 법. 후보 꼭짓점의 두 이웃 변에 CCW를 돌려 방향을 판정하고, 그것이 왜 이진 탐색이 되는지 따라간다.
- 볼록 껍질 ③ — Plane Sweeping과 동적 갱신
점을 하나씩 더해 가며 볼록 껍질을 유지하는 두 문제를 다룬다. 점을 x좌표 순으로 추가하는 Plane Sweeping(O(N²)에서 균형 트리로 O(N log N))과, 완성된 껍질에 점이 계속 추가되는 동적 볼록 껍질이다.
- 볼록 껍질 ② — Graham Scan과 정렬 하한
Package Wrapping은 걸음마다 점 전체를 훑어 최악 O(N²)이다. Graham Scan은 각도 정렬 한 번 뒤 스택으로 좌회전만 남겨 O(N log N)에 볼록 껍질을 구한다. 정렬을 볼록 껍질로 환원해 Ω(N log N) 하한까지 확인한다.
- 볼록 껍질 ① — 정의, CCW, 그리고 Package Wrapping
평면의 점들을 모두 감싸는 가장 작은 볼록 다각형, 볼록 껍질(convex hull)을 구한다. O(N³) 브루트포스에서 출발해 세 점의 회전 방향을 정수 연산으로 판정하는 CCW를 유도하고, 포장지로 감싸듯 껍질을 찾는 Package Wrapping(O(NH))까지 다룬다.
- 추가 설명 — 균형 이진 탐색 트리는 어떻게 y로 정렬하고 구간을 찾는가
가장 가까운 점 쌍 ③에서 활성 집합을 떠받친 균형 BST(std::set)의 내부를 본다. 왜 정렬 배열·연결 리스트가 아닌 균형 BST인지, y를 키로 두면 왜 트리가 곧 y정렬인지, [y-D, y+D] 구간을 O(log n + 개수)에 찾는 원리를 짚는다.
- 가장 가까운 점 쌍 ③ — Plane Sweeping과 균형 이진 탐색 트리
2편과 같은 O(n log n)에 다른 시선으로 닿는다. 점을 x좌표 순으로 훑으며 폭 D 안의 점만 균형 BST(std::set)에 담는 Plane Sweeping으로, y좌표 [y-D, y+D] 구간만 조회한다. 후보가 상수 개임을 보여 전체 O(n log n)을 유도한다.
- 가장 가까운 점 쌍 ② — 정렬을 유지해 O(n log n)으로
1편 O(n log²n)의 여분 log n은 combine마다 y정렬을 다시 하는 데서 나온다. 재귀가 y로 정렬된 결과를 반환하게 만들어 combine을 O(n) merge로 바꾸고, 분할은 x·순서는 y로 유지해 전체를 O(n log n)으로 끌어내린다.
- 추가 설명 — 왜 다음 7개만 비교하면 되는가
가장 가까운 점 쌍의 combine에서, 한 점이 옆에 있는 점을 몇 개만 비교해도 되는 이유를 쉽게 풀어 본다. 핵심은 '가까운 점은 좁은 공간에 빽빽이 들어갈 수 없다'는 것. 후보가 들어올 칸을 잘게 쪼개 세면, 비교 대상이 n과 무관한 상수(최대 7개)로 묶인다.
- 가장 가까운 점 쌍 ① — 분할 정복과 O(n log²n)
2차원 평면에서 가장 가까운 두 점을 찾는 문제. 모든 쌍을 보면 O(n²)이지만, 분할 정복으로 더 빠르게 풀 수 있다. x좌표로 좌우를 나눠 각 영역의 최소 거리 D를 구한 뒤, 경계의 폭 D 밴드만 합치는 과정을 보고 O(n log²n)임을 유도한다.
- 추가 설명 — 왜 하필 5개로 나누는가
median of medians가 그룹을 5개로 나누는 이유. 그룹 크기 g를 일반화해 두 부분문제 비율의 합이 1보다 작아야 선형임을 보인다. g=3과 g=4는 합이 정확히 1이라 깨지고, g=5는 0.9로 성립한다. g=7 이상은 수축이 좋아지는 대신 그룹 정렬 비용이 늘어 맞선다.
- 추가 설명 — quickselect는 왜 평균 O(n)인가
선택 문제 본문이 '대부분 O(n)'으로 넘어간 quickselect의 평균 시간을 기댓값 점화식으로 엄밀히 따진다. quick sort와 달리 한쪽으로만 재귀하기 때문에 E(n)에 max 항이 생기고, 이를 상계로 풀면 E(n) ≤ 4n = O(n)이다.
- 선택 문제 — k번째 원소를 정렬 없이 O(n)에 찾기
k번째로 작은 원소를 찾는 선택 문제. 정렬은 O(n log n)이지만 선택은 더 쉽다. quick sort의 분할을 재활용한 quickselect를 보고, 최악 O(n²)을 없애려 5개씩 묶는 median of medians로 최악에도 O(n)임을 증명한다.
- quick sort — 최악 O(n²)인데 평균은 왜 O(n log n)인가
quick sort는 pivot으로 배열을 가르는 분할 정복이다. 두 포인터 분할 과정을 보고 최선 O(n log n)과 최악 O(n²)이 갈리는 지점을 짚는다. 핵심은 평균 분석이다. 기댓값 점화식 E(n)을 세워 평균이 Θ(n log n)임을 유도한다.
- 분할 정복 — 나누어 풀고, 정렬의 한계를 증명하다
분할 정복은 문제를 나눠 풀고 합치는 전략이다. merge sort의 점화식을 대입법으로 풀어 O(n log n)을 유도하고, 메모리 약점과 대안 heap sort를 본다. 비교 기반 정렬이 Ω(n log n)보다 빠를 수 없음을 결정 트리로 증명한다.
- 테이프 스토리지 — 접근 시간을 최소로 만드는 greedy 배치
크기와 사용 빈도가 다른 데이터들을 하나의 테이프에 어떤 순서로 배치해야 평균 접근 시간이 최소가 될까? 빈도 대비 길이의 비율 F/L이 큰 데이터부터 앞에 놓는 greedy 전략을 세우고, 이웃한 두 데이터를 맞바꾸는 교환 논증으로 그 최적성을 증명한다.
- 구간 스케줄링 — 겹치지 않게 가장 많은 일 고르기
시작 시간과 종료 시간이 정해진 여러 일이 있고, 한 번에 하나만 할 수 있다. 이익이 모두 같을 때, 겹치지 않게 고를 수 있는 일의 개수를 최대로 만드는 문제를 다룬다. 종료 시간이 빠른 일부터 고르는 greedy 전략을 세우고, 교환 논증으로 그 최적성을 증명한다.
- 데드라인 스케줄링 — 이익을 최대로 만드는 그리디 배치
마감 기한과 이익이 있는 일들 중에서, 이익의 합을 최대로 만드는 일정을 짜는 문제를 다룬다. 이익이 큰 일부터 마감 기한에 가까운 자리에 넣는 그리디 전략을 세우고, 교환 논증으로 그 최적성을 증명한 뒤, 균형 트리로 O(N log N)까지 줄이는 방법을 살펴본다.
- 다익스트라 알고리즘 2 — 최단 경로 복원, 시간 복잡도, 그리고 Prim과의 비교
다익스트라 알고리즘에서 부모 배열로 최단 경로를 복원하고, 우선순위 큐로 O(m log n)을 달성한 뒤 Prim 알고리즘과 차이를 비교한다.
- 다익스트라 알고리즘 1 — 각 정점까지의 최단 거리만 구하기
다익스트라 알고리즘으로 한 시작점에서 모든 정점까지 최단 거리를 구한다. 확정 집합을 키우며 가장 가까운 정점을 추가하는 그리디 전략을 보고, 왜 최소 d_min이 정답인지·왜 추가한 정점의 간선만 갱신하면 되는지를 증명한다.
- Prim·Kruskal은 모든 MST를 찾을 수 있는가
같은 그래프에 여러 MST가 나올 수 있다. 동률 간선이 같은 자리를 두고 맞설 때 갈림이 생기는 조건을 짚고, 목표 MST를 정해 그것을 출력하게 하는 선택 규칙을 Prim과 Kruskal 각각에 대해 구성해 두 알고리즘이 모든 MST에 도달함을 보인다. 가중치가 모두 다르면 MST가 유일함도 증명한다.
- Kruskal 알고리즘 — 그리디로 MST를 만든다
Kruskal 알고리즘으로 최소 신장 트리(MST)를 구성한다. 가장 작은 간선부터 그리디하게 고르는 전략이 왜 최적인지 컷 기반 교환 논법으로 증명하고, Union-Find로 사이클 검사를 거의 상수 시간에 처리해 O(m log m)으로 마무리한다.
- 프림 알고리즘 (Prim) — MST를 찾는 그리디 전략
프림 알고리즘은 하나의 정점에서 시작해 현재 트리 안과 밖을 가르는 간선 중 가장 가벼운 것을 반복적으로 추가하여 MST를 만든다. 알고리즘의 동작을 단계별로 살펴보고, 매 단계 선택이 항상 어떤 MST의 부분집합에 포함된다는 사실을 귀납법과 사이클 논증으로 증명한다.
- 최소 신장 트리 (MST) — 정의와 성질
최소 신장 트리(MST)는 가중 연결 그래프에서 모든 정점을 잇는 간선 가중치 합이 최소인 부분 그래프다. MST가 왜 트리여야 하는지, 정확히 n−1개 간선을 갖는 이유를 증명하고, MST가 유일하지 않을 수 있는 경우를 정리한다.
- 그리디 알고리즘 — 매 순간 가장 좋아 보이는 선택
그리디 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하고 그 선택을 번복하지 않는다. selection sort와 최단 경로 문제를 통해 그리디의 작동 원리를 살펴보고, 눈앞의 최적이 전체 최적이 아닐 수 있는 한계를 확인한다.
- 정렬 알고리즘 — Selection / Merge / Quick
selection·merge·quick sort의 동작 원리를 코드 수준에서 보고, 각 정렬의 올바름을 루프 불변식과 귀납법으로 증명한다. 시간 복잡도 O(n²)·O(n log n)·평균 O(n log n)의 차이가 어디서 오는지 정리한다.
- 자료구조 — 데이터를 담는 그릇의 설계
Array, Stack, Queue, Linked List, BST, AVL Tree, Heap, 2-3 Tree, Graph까지 — 각 자료구조의 구조와 핵심 연산을 시각적으로 정리한다.
- 재귀 — 문제를 자기 자신으로 푼다
재귀(Recursion)의 구조와 올바른 설계 원칙을 이해하고, 수학적 귀납법으로 재귀 알고리즘의 올바름을 증명한다. 팩토리얼·피보나치·하노이의 탑을 통해 재귀적 사고를 익히고, 재귀 트리와 마스터 정리로 복잡도를 분석한다.
- 알고리즘 오리엔테이션 — 알고리즘이란 무엇인가
알고리즘의 정의와 올바름(Correctness)을 살펴보고, 최댓값 찾기와 이진 탐색 예시로 알고리즘을 증명한다. 정지 문제(Halting Problem)로 알고리즘의 근본 한계를 확인하고, RAM 모델과 점근적 표기법(Big-O, Θ, Ω)으로 효율을 분석한다.
- Future Cryptography — 양자역학이 바꾸는 암호의 미래
마흐·젠더 간섭계, 양자 폭탄 검출기, EPR 역설, 벨의 정리, 양자 컴퓨터(Shor 알고리즘), 그리고 BB84 양자 키 교환까지 — 양자역학이 암호학의 미래를 어떻게 바꾸는지 다룬다.
- Before Physics — 논리, 불완전성, 그리고 과학의 기반
양자역학과 상대성 이론에 들어가기 전, 논리와 물리학의 차이, 괴델의 불완전성 정리, 오컴의 면도날, 과학적 원리까지 — 물리학을 세우는 철학적·논리적 기반을 다룬다.
- Zero Knowledge Proof — 전달 없이 입증하기
영지식 증명의 직관과 그래프 동형 예시, 비밀 공유, 은닉 서명까지 살펴보며 증명자가 지식을 드러내지 않고 설득하는 방식을 설명한다.
- Cryptographic Hashing — 암호학적 해시 함수
SHA의 내부 구조(Merkle-Damgård), 일방향성·충돌 저항성의 수학, Birthday Paradox가 해시 길이에 미치는 영향, MD5·SHA-1이 왜 더 이상 안전하지 않은지, 그리고 HMAC과 패스워드 해시까지 — 암호학적 해시 함수의 전체를 다룬다.
- Digital Signature — 전자 서명의 수학적 구조
RSA·ElGamal 전자 서명의 생성과 검증, 교과서 RSA가 위조되는 두 가지 방식, 인증기관(CA)의 역할, 암호학적 해시와 Birthday Paradox, 그리고 AES+RSA+SHA의 역할 분담까지 디지털 서명의 전체 그림을 다룬다.
- Diffie-Hellman — 공개 채널 위의 비밀 키 교환
ElGamal의 수학적 기반이 된 Diffie-Hellman 키 교환 — 프로토콜 구조, 정확성 증명, CDH/DDH 가정, 중간자 공격과 인증 문제, 그리고 ElGamal·TLS로의 확장까지 다룬다.
- ElGamal — 이산 대수 기반 공개키 암호
RSA와 달리 이산 대수 문제(DLP)의 어려움에 기반한 ElGamal 암호화. 키 생성, 암복호화, 정확성 증명, 확률적 암호화의 보안 이점까지 다룬다.
- Find Prime — 소수 판별과 확률적 소수 탐색
소수 밀도 추정, Fermat 테스트, Witness와 Carmichael 수의 한계, Witness 밀도 증명 — 임의의 큰 수가 소수인지 확률적으로 판별하는 방법을 단계적으로 구성한다.
- RSA — 공개키 암호의 수학적 구조
RSA의 키 생성, 암복호화, 복호화 정확성 증명(오일러·페르마·CRT), 소인수분해 보안 근거, Square-and-Multiply 고속 지수연산까지 — 공개키 암호의 수학 전체를 다룬다.
- Chinese Remainder Theorem — 중국인의 나머지 정리
서로소인 여러 모듈러스에 대한 연립 합동식이 항상 유일한 해를 가짐을 구성적으로 증명하고, 단계별 계산 예시와 RSA-CRT 속도 최적화까지 다룬다.
- Fermat's Little Theorem — 페르마의 소정리
소수 p와 서로소인 a에 대해 a^(p-1) ≡ 1 (mod p)가 성립함을 두 가지 방법으로 증명하고, 모듈러 역원 계산과 RSA 복호화, 페르마 소수 판별법까지 응용을 다룬다.
- Modular Arithmetic — 모듈러 산술과 잉여계
모듈러 산술의 동치 관계, 완전·축약 잉여계, 오일러 정리와 페르마의 소정리, 중국인의 나머지 정리(CRT)까지 — RSA를 비롯한 공개키 암호의 수학적 엔진을 완성한다.
- Greatest Common Divisor — 최대공약수와 유클리드 호제법
암호학의 핵심 도구인 최대공약수(GCD)를 대수적으로 정의하고, 유클리드 호제법과 확장 유클리드 알고리즘(베주 항등식)을 엄밀하게 증명한다. 서로소의 성질과 GCD 정의의 동치 증명까지 다룬다.
- Division Theorem — 정수 나눗셈의 기초
암호학의 수학적 기반이 되는 Division Theorem(나눗셈 정리)을 엄밀하게 증명한다. 나누어 떨어짐의 정의와 성질, 소수의 정의를 살펴보고, 몫과 나머지의 존재성·유일성을 보인다.
- NP-Complete — NP에서 가장 어려운 문제들
NP 내에서 가장 어려운 문제들의 집합인 NP-Complete를 정의하고, Reduction(귀착) 개념과 Cook의 정리를 통해 SAT가 최초의 NP-Complete 문제임을 증명하는 과정을 살펴본다.
- NP의 다른 정의 — 검증자와 증명서
NTM 기반의 NP 정의와 검증자(Verifier) 기반의 NP 정의가 동치임을 보인다. '힌트가 있을 때 빠르게 검증할 수 있는 문제'라는 직관이 어떻게 수학적으로 엄밀해지는지 탐구한다.
- Alice and Bob — 계산 복잡도 클래스 P, NP, PSPACE
암호화의 안전성을 계산 복잡도로 정의한다. P, NP, EXP, PSPACE 클래스를 소개하고, P ⊆ NP ⊆ PSPACE ⊆ EXP 계층 관계와 PSPACE = NPSPACE를 설명한다.
- Classes — 계산 가능성 클래스 D, E, co-E
결정 가능한 문제의 집합 D, 열거 가능한 문제의 집합 E, 그리고 co-E를 정의하고, D = E ∩ co-E를 증명한다. 정지 문제를 통해 E ≠ D임을 확인한다.
- Turing Machine — 계산의 극한
현대 컴퓨터의 이론적 모델인 튜링 머신의 구조를 살펴보고, 2-Tape DTM, Universal Turing Machine, 그리고 DTM과 NTM의 계산 능력이 동일함을 정리한다.
- DPDA와 NPDA — 스택을 가진 오토마타
DFA에 스택을 추가한 DPDA가 해결할 수 있는 문제와 없는 문제를 살펴보고, NPDA와의 계산 능력 차이를 분석한다. 스택 2개로 튜링 머신을 시뮬레이션하는 원리까지 다룬다.
- NFA — 비결정론적 유한 오토마타
DFA를 확장한 계산 모델인 NFA의 구조와 accept 조건을 살펴보고, Powerset Construction을 통해 NFA와 DFA의 계산 능력이 동일함을 설명한다.
- DFA — 결정론적 유한 오토마타
튜링 머신을 단순화한 계산 모델인 DFA의 구조와 동작 원리를 살펴보고, Pumping Lemma를 통해 DFA로 풀 수 없는 문제가 존재함을 증명한다.
- Problem & Solution — Complexity Theory의 수학적 정의
Complexity Theory에서 '문제'와 '풀이'는 어떻게 정의될까? Decision Problem, Language, 튜링 머신을 통해 풀리지 않는 문제가 왜 대부분인지를 살펴본다.
- 집합의 크기(Cardinality) — 무한의 크기를 비교하다
무한집합에도 크기가 있을까? 자연수, 정수, 유리수, 실수의 크기를 비교하고, 칸토어의 대각선 논법을 통해 무한에도 '더 큰 무한'이 있음을 증명한다.
- Toss Coin over Telephone
전화로 공정하게 동전 던지기를 할 수 있을까? Manuel Blum이 제안한 암호학적 동전 던지기 프로토콜과 그 수학적 배경을 다룬다.
- Interesting Number Paradox
수학적 증명에서 '정의(definition)'의 엄밀함이 왜 중요한지를 보여주는 패러독스. 암호학 Complexity Theory 도입부.