| [정보통신기술용어해설] |
Pigeon Hole Principle 비둘기집 원리 | (2017-10-18) |
Dirichlet Box Principle | |
1. 비둘기집 원리
ㅇ n,k (n > k) 일 때, n 마리의 비둘기를 k 개의 비둘기집에 넣을때,
- 적어도 2 마리 이상 들어간 집이 있게 됨
ㅇ 또는, n(A) > n(B) 이면,
- 유한 집합 A에서 B로 가는 단사 함수가 될 수 없음
. 단사 함수 : B의 각 원소에 대응하는 A의 원소가 기껏해야 하나 만 갖을 때 (1:1 함수)
ㅇ 비둘기집 원리는, 배열의 존재성 문제를 증명할 때 필요함