티스토리 뷰

공부

포함-배제의 원리

전명우 2014. 7. 20. 15:01

포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다.


TopcoderCodeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다.


포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다.


1) 집합이 두 개인 경우

$|A|$를 유한 집합 $A$의 크기라고 하면, 두 유한 집합 $A$, $B$의 합집합의 크기 $|A \cup B|$는 아래와 같다.



2) 집합이 세 개인 경우

세 개의 유한 집합 $A$, $B$, $C$가 있다고 하자. 이의 벤다이어그램은 위 그림과 같다. 세 집합의 합집합의 크기 $|A \cup B \cup C|$는 아래와 같이 계산할 수 있다.



3) 일반항

일반적으로 $n$개의 유한 집합 $A_1, A_2, \dots, A_n$이 있다고 하자. 그 합집합의 크기는 아래와 같다.




4) 여러 응용





'공부' 카테고리의 다른 글

Suffix Array와 LCP  (14) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
중국인의 나머지 정리와 확장 유클리드 알고리즘  (0) 2014.07.25
고속 푸리에 변환 (Fast Fourier Theorem, FFT)  (8) 2014.07.25
Nim game  (5) 2013.07.29
댓글
댓글쓰기 폼