16강 / 20강

비둘기집 원리 — 세어 보지 않고도 아는 것

너무 당연해서 강력한 원리

비둘기 10마리를 집 9개에 넣으면, 적어도 한 집에는 두 마리 이상이 들어갑니다. 너무 당연하죠? 그런데 이 당연한 말이 놀라운 결론들을 만들어 냅니다.

비둘기집 원리 — n개의 물건을 k개의 상자에 넣으면 (n > k), 적어도 한 상자에는 ⌈n/k⌉개 이상이 들어간다.

비결은 무엇을 비둘기로, 무엇을 집으로 볼 것인가를 정하는 데 있습니다. 그것만 정하면 나머지는 자동이에요.

🕊️

비둘기

넣는 것 (사람, 값, 경우)

🏠

집

분류 기준 (나머지, 칸, 종류)

💥

결론

겹치는 것이 반드시 있다

고등학생너무 당연해서 강력한 원리

이 원리는 말도 안 되게 당연합니다.

비둘기 n+1 마리를 집 n 개에 넣으면 — 어딘가는 둘 이상

그런데 왜 배우나

힘	설명
세지 않고 안다	구체적으로 어디인지 몰라도 존재를 안다
증명이 짧다	—
적용이 넓다	수학부터 컴퓨터까지

5강의 ∃ 를 증명하는 강력한 도구다

예 — 서울 사람 중에

머리카락 수가 같은 두 사람이 반드시 있습니다.

—	수
사람	약 1000만
가능한 머리카락 수	약 15만

사람이 훨씬 많으니 반드시 겹친다 — 세어 보지 않고도

누구와 누구인지는 모릅니다. 그런데 있다는 것은 확실하죠.

존재를 구성 없이 증명한다 — 비구성적 증명

10강과 이어집니다

해시 함수가 단사가 아닌 이유가 이것입니다.

—	—
입력 (비둘기)	무한
출력 (집)	유한

충돌은 피할 수 없다 — 수학적으로 그렇다

세어 보지 않고도 '반드시 있다'를 말할 수 있습니다.

Python 브라우저에서 실행

import math

def 비둘기집(비둘기, 집, 설명):
    보장 = math.ceil(비둘기 / 집)
    print(f"{설명}")
    print(f"   비둘기 {비둘기:,} · 집 {집:,} → 어느 집엔가 최소 {보장:,}개가 몰린다\n")

비둘기집(367, 366, "사람 367명이 모이면 생일이 같은 두 사람이 있다")
비둘기집(50_000_000, 1_000_000, "머리카락 수가 같은 한국인 두 사람이 있다")
비둘기집(13, 12, "13명 중 태어난 달이 같은 두 사람이 있다")

🎮 비둘기를 집에 넣어 보세요

비둘기 수와 집 수를 조절하며 언제 충돌이 확정되는지 확인해 보세요. 무작위로 넣어 보는 버튼을 누르면 실제로도 늘 겹친다는 걸 볼 수 있습니다.

고등학생일반화된 비둘기집

기본형을 조금 확장하면 훨씬 유용해집니다.

n 마리를 k 집에 넣으면 — 어딘가는 ⌈n/k⌉ 마리 이상

예로 보면

상황	결론
학생 100명, 생일 달 12개	어느 달은 9명 이상 (⌈100/12⌉)
양말 7짝, 색 3가지	어느 색은 3짝 이상

"적어도 몇 개" 를 보장한다 — 평균의 하한이다

왜 올림인가

모두 ⌈n/k⌉ 미만 이라면 최대 k×(⌈n/k⌉−1) < n — 전부 담을 수 없습니다.

귀류법이다 — 6강의 도구가 여기서 쓰인다

실전 예 — 어두운 서랍

검정·흰색·회색 양말이 섞여 있습니다. 같은 색 한 켤레를 확실히 얻으려면 몇 짝?

뽑은 수	보장
3	전부 다를 수 있다
4	반드시 같은 색 둘 ✔

"최악의 경우" 를 생각하는 것이 핵심이다

이 사고방식이 유용합니다

분야	쓰임
알고리즘	최악의 경우 분석
자원 계획	"최소 몇 개가 필요한가"
보안	충돌 가능성

"운이 나쁘면" 을 계산하는 습관 — 공학의 기본 태도다

해시 충돌은 피할 수 없습니다

10강에서 해시 함수는 단사가 아니라고 했죠. 이제 왜 그럴 수밖에 없는지 증명할 수 있습니다.

비둘기 = 가능한 입력 (비밀번호, 파일, 문자열… 무한히 많음)
집 = 해시 값 (SHA-256이라도 2²⁵⁶개, 유한함)

무한을 유한에 넣으므로 충돌은 반드시 존재합니다. 좋은 해시 함수의 목표는 "충돌이 없게" 만드는 것이 아니라 — 그건 불가능하니까 — 충돌을 찾기 어렵게 만드는 것입니다.

이름 9개, 칸 8개 — 비둘기집 원리가 충돌을 보장합니다.

Python 브라우저에서 실행

# 작은 해시로 충돌을 직접 만들어 봅니다
def 작은해시(말, 칸수=8):
    return sum(ord(c) for c in 말) % 칸수

이름들 = ["민준", "서연", "지호", "하윤", "예준", "도윤", "시우", "주원", "지안"]
칸 = {}
for 이름 in 이름들:
    h = 작은해시(이름)
    칸.setdefault(h, []).append(이름)

for h in sorted(칸):
    표시 = " ← 충돌!" if len(칸[h]) > 1 else ""
    print(f"칸 {h}: {', '.join(칸[h])}{표시}")
print()
print(f"이름 {len(이름들)}개를 칸 8개에 넣었으니 충돌은 피할 수 없습니다.")

고등학생생일 문제 — 23명이면 절반이 넘습니다

note 의 이 예가 직관을 배신하는 대표적인 문제입니다.

비둘기집으로는 366명이 필요한데 — 확률로는 23명

왜 이렇게 다른가

물음	필요한 인원
반드시 같은 생일이 있다	366명
확률 50% 로 있다	23명 ⭐

"확실" 과 "그럴듯" 사이가 어마어마하게 멀다

왜 23명이면 충분한가

짝의 개수를 세어 보세요.

인원	가능한 짝
23	C(23,2) = 253쌍

사람은 23명인데 비교는 253번 일어난다

"나와 같은 생일" 이 아니라 "아무 두 사람" 이라는 게 핵심입니다.

계산은 여집합으로

—	—
"전부 다를" 확률	365/365 × 364/365 × …
23명일 때	약 0.49
같은 게 있을 확률	0.51 ✔

13강의 여집합 세기 가 여기서 쓰인다

보안에서 중요합니다

해시 길이	충돌까지 (생일 공격)
n 비트	약 2^(n/2) ⚠
128비트	2⁶⁴ — 절반이 아니라 제곱근

"충돌을 찾기" 는 "특정 값을 찾기" 보다 훨씬 쉽다

그래서 해시 길이를 두 배로 잡습니다. 생일 문제가 실무 설계를 바꾼 것이죠.

'적어도 하나'는 여집합으로. 13강에서 배운 그대로입니다.

Python 브라우저에서 실행

# 생일 문제 — 여집합으로 계산합니다 (13강의 요령)
def 겹칠확률(n, 날수=365):
    다름 = 1.0
    for i in range(n):
        다름 *= (날수 - i) / 날수      # 모두 다를 확률
    return 1 - 다름                     # 적어도 하나는 겹칠 확률

for n in (5, 10, 20, 23, 30, 50, 70):
    print(f"{n:>3}명 → 생일이 겹칠 확률 {겹칠확률(n)*100:>5.1f}%"
          + ("  ← 절반을 넘는 지점" if n == 23 else ""))

집을 '나머지'로 잡는 것이 이 문제의 열쇠입니다.

Python 브라우저에서 실행

# 나머지를 집으로 삼기 — 어떤 n개 중에는 합이 n의 배수인 부분이 있다
수들 = [17, 23, 5, 41, 8]
n = len(수들)
누적, 나머지자리 = 0, {}
for i, x in enumerate(수들, 1):
    누적 += x
    r = 누적 % n
    print(f"앞 {i}개의 합 {누적:>3} → {n}으로 나눈 나머지 {r}")
    if r == 0:
        print(f"   → 앞 {i}개의 합이 {n}의 배수!"); break
    if r in 나머지자리:
        j = 나머지자리[r]
        print(f"   → {j+1}번째 이후 {i-j}개의 합 {수들[j:i]} 이 {n}의 배수!"); break
    나머지자리[r] = i
print(f"\n나머지는 {n}가지뿐인데 누적합은 {n}개 → 비둘기집 원리로 반드시 걸립니다.")

고등학생꼭 기억하세요

16강의 정리와 쓰는 요령입니다.

비둘기 > 집 이면 — 어딘가는 겹친다

쓰는 순서

단계	정할 것
1	무엇이 비둘기인가
2	무엇이 집인가
3	비둘기가 더 많은지 확인

2번이 어렵다 — 집을 잘 정하는 것이 요령이다

예 — 창의적인 집 만들기

"1~100 에서 51개를 뽑으면 한쪽이 다른 쪽의 배수인 짝이 있다"

집을 이렇게	—
홀수 k 마다 {k, 2k, 4k, …}	집이 50개
51개를 뽑으면	같은 집에 둘 → 배수 관계 ✔

집을 영리하게 만들면 놀라운 결론이 나온다

컴퓨터에서의 적용

사실	근거
완벽한 무손실 압축은 불가능	비둘기집 ⭐
해시 충돌은 필연	10강
n 비트로 2ⁿ 개 초과 표현 불가	—

"모든 파일을 줄이는 압축" 은 수학적으로 불가능하다

어떤 파일을 줄이면 다른 파일은 늘어납니다. 자리가 부족하니까요.

당연한 원리가 불가능성을 증명한다 — 그게 이 원리의 힘이다

🤔 확인 문제

서랍에 검정 양말 10짝, 흰 양말 10짝이 섞여 있습니다. 어두운 방에서 같은 색 한 켤레를 확실히 만들려면 최소 몇 짝을 꺼내야 할까요?

🤔 확인 문제

해시 충돌이 원리적으로 피할 수 없는 이유는?

🤔 확인 문제

생일이 같은 두 사람이 있을 확률이 50%를 넘는 최소 인원은? (윤년 무시)

해설 23명입니다 — 비교되는 쌍이 C(23,2)=253쌍이나 되기 때문이에요. 367명은 확률 50%가 아니라 100% 보장에 필요한 수(비둘기집)입니다. 둘을 구별하는 것이 이 강의의 핵심이에요.