PS 이야기

포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다. Topcoder나 Codeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다. 포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다. 1) 집합이 두 개인 경우$|A|$를 유한 집합 $A$의 크기라고 하면, 두 유한 집합 $A$, $B$의 합집합의 크기 $|A \cup B|$는 아래와 같다. 2) 집합이 세 개인 경우세 개의 유한 집합 $A..