topic★★★★★난이도 · 약 20분
조합론
경우의 수를 세는 수학적 전략 — 순열·조합·비둘기집·생성함수.
#조합론#순열#조합#암호학
왜 배우는가
AES 256비트 암호 키는 2²⁵⁶ ≈ 10⁷⁷가지로 우주의 원자보다 많아 뚫리지 않는다. 바둑 첫 수 이후 경우의 수 10¹⁷⁰, 체스는 10¹²⁰. 조합론은 암호학·알고리즘 복잡도·게임 AI의 공통 토대다.
조합론은 '세는 학문'이다. '몇 가지 가능성이 있는가?' — 이 질문 하나에 순열·조합·비둘기집·생성함수·포함배제 등 풍부한 도구가 응답한다.
| 도구 | 공식 | 언제 쓰는가 |
|---|---|---|
| 순열 P(n,r) | n!/(n−r)! | 순서 중요 (반장·부반장 뽑기) |
| 조합 C(n,r) | n!/(r!(n−r)!) | 순서 무관 (대표 2명 뽑기) |
| 비둘기집 | 11마리가 10집 → 한 집에 2마리 이상 | 존재성 증명 |
| 포함-배제 | |A∪B|=|A|+|B|−|A∩B| | 중복 세기 |
| 생성함수 | f(x)=Σaₙxⁿ | 점화식 닫힌 형태 |
이항정리: (1+x)ⁿ = Σ C(n,k)xᵏ. 조합의 수가 이항계수로 등장 — 파스칼 삼각형의 각 행이 이 계수.
text
예제 — 비밀번호 강도
4자리 숫자 PIN: 10⁴ = 10,000가지
→ 초당 100번 시도 시 100초면 전수조사
8자리 영문+숫자+기호: 94⁸ ≈ 6·10¹⁵가지
→ 같은 속도로 200만 년
AES-256 키: 2²⁵⁶ ≈ 10⁷⁷가지
→ 우주 나이(4·10¹⁷초)로도 불가능비둘기집 원리의 위력: '1년 366일에 367명 중 반드시 같은 생일 2명 존재'는 조합의 존재성을 간결하게 증명하는 도구. 해싱 충돌, 비밀번호 공간 분석, 알고리즘 하한 증명의 기본 무기.
실생활 응용 — ① AES/RSA 키 공간 분석 ② 정렬 비교 하한 Ω(n log n) 증명 ③ 바둑·체스 AI의 가지치기 ④ 네트워크 라우팅 경로 수 ⑤ 복권·가챠 확률.
실기 드릴 5문항
edit실기 드릴 · 단답형
10명 중 대표 3명을 순서 없이 뽑는 경우의 수는?
check_circle실기 드릴 · OX
같은 상황에서 P(10,3) > C(10,3)이다.
edit실기 드릴 · 단답형
비둘기 11마리가 비둘기집 10개에 들어갈 때, 적어도 한 집에는 최소 몇 마리가 있어야 하는가?
edit실기 드릴 · 단답형
(1+x)⁵의 x² 계수는?
radio_button_checked실기 드릴 · 객관식
52장 카드에서 5장을 뽑는 경우의 수는 약 얼마인가?