티스토리 뷰

공부

포함-배제의 원리

전명우 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)  (7) 2014.07.25
포함-배제의 원리  (0) 2014.07.20
Nim game  (5) 2013.07.29
댓글
댓글쓰기 폼