비둘기집의 원리와 압축
비둘기집의 원리란 다음과 같은 것이다. 비둘기가 n마리 있고, 비둘기집이 m개 있는데, n>m이면, 반드시 비둘기가 2마리 이상 들어가는 집이 하나 이상 있다. 예를 들어 비둘기 5마리가 비둘기 집 3개에 들어가려면 어떤 집에는 비둘기가 2마리 이상이 들어간다는 것이다. 비둘기집의 원리는 너무 당연한 사실이지만, 이산수학에서 꽤 중요한 위치를 차지하고 있는 놈이다. 위키백과에서 관련된 내용을 살펴볼수 있다: 위키백과-비둘기집의 원리 컴퓨터 압축기술에 비둘기집의 원리를 적용해보자. 데이터 압축이란 어떤 데이터를 인코딩의 과정을 거쳐 원래 크기보다 작은 데이터로 변형하고, 다시 디코딩 과정을 거쳐 원래 데이터를 복원해 내는 일 모두를 일컫는다. 데이터가 압축될때 원래 데이터의 크기보다 크기가 줄어드는데, 여..
프로그래밍
2008. 12. 25. 23:28
