비둘기집 원리

비둘기집 원리란?

여러개의 데이터를 그룹 짓는 상황에서 경우의 수를 따질 때, 사용할 수 있는 알고리즘이다.

예시

1. 옷장에 흰색 양말 10개와 검은색 양말 10개가 있다고 할 때, 같은 색상의 양말 한 켤레를 만들기 위해서는 최소 몇개의 양말을 꺼내야 하는가?

색상에 상관없이 한 켤레의 양말을 만들면 되기 때문에, 3개 이상만 꺼내면 같은 색상의 한 켤레를 만들 수 있다.

 

비둘기집 원리를 적용하면, 두개의 방이 있다고 가정하며 양말을 한개 꺼내 흰색, 검은색 중 하나의 방에 넣는 시행을 반복한다.

최선의 경우에는 2번의 시행으로 둘 중 하나의 방에 양말 두개가 들어가 한 켤레를 만들 수 있지만, 서로 다른 색의 양말이 나왔을 경우에는 한 방에 하나씩의 양말만 들어있을 뿐이다.

그러므로 세번째 시행에서는 둘중 하나의 방에 무조건 한켤레의 양말이 만들어 지게 되는 것이다.

 

2. 대한민국에 총 10만개의 서로 다른 이름이 있다고 가정할 때, 대한민국 5천만 국민 중 중복된 이름을 가진 국민이 있음을 증명하기

1번 예시의 경우는 흰색, 검은색으로 두가지 그룹만 있기 때문에 '비둘기집 원리'를 적용하지 않더라도 쉽게 해결할 수 있다.

2번 예시의 경우는 총 5천만의 데이터와 10만개의 그룹으로 구성되어 있기 때문에 더 까다롭다고 할 수 있다.

 

하지만, 비둘기집 원리를 동일하게 적용하면 10만개의 방에 이름 하나씩을 집어넣는다고 할 때, 데이터의 수가 방의 수보다 많기 때문에 무조건 한개 이상의 방에는 동일한 이름이 두개 이상 들어있을 것이라고 직관적으로 생각해볼 수 있다.