비둘기집 원리(Pigeonhole Principle)의 직관과 알고리듬 문제에서의 활용 - soo:bak
작성일 :
비둘기집 원리란?
비둘기집 원리(Pigeonhole Principle)는 일정한 수의 공간에 더 많은 항목이 들어가면,
반드시 어느 공간에는 중복이 발생한다는 매우 기본적인 수학적 원리입니다.
가장 단순한 형태는 다음과 같이 설명할 수 있습니다:
n + 1개의 물건을n개의 상자에 넣을 경우, 적어도 하나의 상자에는 두 개 이상의 물건이 들어가야 한다.
직관적으로 명확해 보이는 이 원리는, 상태 수가 제한된 문제에서 중복이 불가피하다는 사실을 증명하거나
모순을 유도할 때 자연스럽게 사용됩니다.
일반화된 정의와 수식
보다 일반화된 형태로는 다음과 같이 표현할 수 있습니다:
k개의 상자에N개의 항목을 넣으면, 어떤 상자에는 최소한 \(\left\lceil \frac{N}{k} \right\rceil\) 개 이상의 항목이 들어가야 합니다.
예시로, 10개의 사탕을 3개의 상자에 넣는다면, 적어도 한 상자에는 \(\lceil \frac{10}{3} \rceil = 4\)개 이상의 사탕이 포함됩니다.
간단한 예시로 살펴보기
생일 예시
- 생일이 가능한 날짜가 윤년을 포함해 최대 366일이라고 가정할 때,
367명이 있다면, 생일이 같은 두 사람이 반드시 존재합니다.
악수 예시
6명이 서로 악수를 한다면, 어떤 사람은 최대5번, 최소0번 악수를 할 수 있습니다.- 하지만 어떤 사람이
0번 악수를 했다면, 동시에5번 악수를 한 사람은 존재할 수 없습니다. - 가능한 값이
5가지뿐이므로, 반드시 같은 악수 횟수를 가진 사람이 둘 이상 존재하게 됩니다.
알고리듬 문제에서의 활용
비둘기집 원리는 반복 상태의 발생을 보장하거나, 가능한 경우의 수를 제한하는 조건이 등장할 때 자연스럽게 적용됩니다.
1. 중복 원소의 존재 보장
- 배열에 들어갈 수 있는 값이
1부터N - 1까지로 제한되어 있고, 배열의 길이가N이상이라면, 반드시 중복되는 값이 존재합니다.
2. 상태 수가 제한된 경우의 순환 발생
- 어떤 수를 반복적으로 연산하여 다음 수를 만들어가는 문제에서,
- 가능한 상태 수가 유한하면, 언젠가는 반드시 이전에 나왔던 값이 다시 나타납니다.
- 생성 가능한 수가
0부터9999까지로 제한되므로,10,000개를 초과하여 수를 생성하면 반드시 중복이 발생합니다.
3. 가능한 상태 수를 기준으로 논리적 모순 유도
- 특정 조건이 성립하지 않는다고 가정했을 때, 가능한 경우의 수를 비둘기집 원리로 비교해 보면 그 가정이 성립할 수 없다는 결론에 도달할 수 있습니다.
핵심 정리
- 가능한 상태 수가 유한할 때, 무한히 연산을 반복하면 언젠가는 반드시 중복되는 상태가 다시 나타납니다.
- 이는 사이클 탐지, 중복 판별, 존재성 증명 등 여러 상황에서 유용하게 쓰일 수 있습니다.
- 단순한 조건처럼 보이지만, 문제에 대한 방향성을 단번에 정해줄 수 있는 사고 도구로 자주 활용됩니다.
마무리
비둘기집 원리는 문제를 해결하기 위한 구체적인 연산보다는, 전체적인 구조를 판단하거나 조건을 해석하는 데에 쓰입니다.
특히 상태 수가 제한되어 있고, 연산이 반복되는 구조가 보일 때는 항상 이 원리를 떠올려보는 것이 도움이 됩니다.
관련 문제: [백준 10570] Favorite Number (C#, C++) - soo:bak
관련 문제: [백준 6500] 랜덤 숫자 만들기 (C#, C++) - soo:bak