비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 어느 한 상자에는 2개 이상의 물건이 들어있다는 원리를 말한다. 디리클레의 서랍 원리라고도 한다. 뭐 하다가 이런 것을 증명했는지 참 궁금해진다. 증명 증명은 귀류법으로 간단히 가능한데, n개의 상자에 n+1마리의 비둘기를 넣을건데 비둘기가 한 마리 이하로 들어가 있다고 가정하자. 그러면 n개의 상자에는 최대 n 마리의 비둘기가 들어갈 수 있으므로 모순이다. 그러니 이 원리는 참이다. 예시 이 원리가 통하는 상황을 생각해보면 저번에 다룬 해시테이블이 있다. 이 원리 때문에 연결리스트나 아예 배열의 크기를 확장할 필요가 생겼다. 또 생각해 보자면 아무 자리 자연수 11개 이상이 있다면 무조건 1의 자리 숫자가 한 개는 겹칠 것이다. 뭐 또 유명한 예..