티스토리 뷰
포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다.
Topcoder나 Codeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다.
포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다.
1) 집합이 두 개인 경우
|A|를 유한 집합 A의 크기라고 하면, 두 유한 집합 A, B의 합집합의 크기 |A∪B|는 아래와 같다.
2) 집합이 세 개인 경우
세 개의 유한 집합 A, B, C가 있다고 하자. 이의 벤다이어그램은 위 그림과 같다. 세 집합의 합집합의 크기 |A∪B∪C|는 아래와 같이 계산할 수 있다.
3) 일반항
일반적으로 n개의 유한 집합 A1,A2,…,An이 있다고 하자. 그 합집합의 크기는 아래와 같다.
4) 여러 응용
'공부' 카테고리의 다른 글
Suffix Array와 LCP (14) | 2014.08.14 |
---|---|
Manacher's Algorithm (0) | 2014.08.13 |
중국인의 나머지 정리와 확장 유클리드 알고리즘 (0) | 2014.07.25 |
고속 푸리에 변환 (Fast Fourier Theorem, FFT) (9) | 2014.07.25 |
Nim game (18) | 2013.07.29 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- idea
- ioi
- Tree
- BOI
- Boyer-Moore Majority Vote Algorithm
- dynamic programming
- IOI2012
- vote
- Algorithm
- USACO
- Divide & Conquer
- Splay Tree
- Dynamic Pramming
- Boyer
- majority
- BOI 2009
- IOI2014
- TRIE
- IOI2013
- Dijkstra
- Knuth Optimization
- z-trening
- IOI2011
- optimization
- BOI 2001
- moore
- Parametric Search
- HackerRank
- Greedy Method
- Segment tree
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
글 보관함