포함 배제의 원리 (Inclusion-Exclusion)

포함 배제의 원리

포함 배제의 원리는 조합, 확률, 그리고 계산에서 유용하게 쓰이는 유명한 기술입니다.

$n$ 개의 집합 $A_1, A_2, \dotsc , A_n$ 들이 주어진 전체 집합 $A$ 가 있습니다. 이제 이 집합들이 가지고 있는 합집합의 원소갯수를 $S_n$ 이라 하겠습니다. 좀더 수식으로 표현하자면, $S_n = \bigg|\bigcup_{i=1}^n A_i\bigg|$ 와 같습니다. 즉, $n$ 개의 집합 $A_1, A_2, \dotsc , A_n$ 에 주어진 모든 원소들을 합집합 하여 만든 집합을 $S$ 라 한다면 그 $S$ 집합 원소들의 총 개수인 $S_n = |S|$ 를 찾는것 입니다. (집합 $A$ 에 대한 집합의 원소개수를 영어로 cardinality (카디널리티) 라고 하고 $|S|$ 로 표현합니다. )

여기서 포함 배제의 원리가 필요합니다. 왜일까요? 모든 집합에 들어있는 원소들은 중복 될수도 또는 중복되지 않을 수도 있습니다. 만약 $n$ 개의 집합 모두를 합집합 해버린다면, 어떤 원소들은 2번 이상 중복해서 들어 있을 수도 있습니다. 다시 말하면, 어떤 두개의 집합들이 교집합한다면 그 결과물이 공집합이 아닐 수 있기 때문에, 위에서 언급한 총 합 $S_n$ 는 단순히 $|A_1| +|A_2| + \dotsc + |A_n|$ 한것보다 같거나 작게됩니다. 그렇기에 일단 $S$ 를 먼저 구할 필요가 있는데, 여기서 포함 배제 원리가 적용되는 것입니다.

$n$ 개의 집합이 들어있는 집합 $A = \{A_1, A_2, \dotsc , A_n\}$ 가 존재할때, $S_n$ 을 구하기위한 식은 다음과 같습니다.

$$S_n = \sum_{i = 1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \ldots + (-1)^{n - 1} \cdot |A_1 \cap \ldots \cap A_n|$$

$n=1$ 이라면 복잡한 식이 필요없이 그냥 $|A_1| = S_n$ 가 성립합니다. $n=2$ 라면, $A_1$ 과 $A_2$ 의 합집합 $A_1 \cup A_2$ 을 구한뒤 중복되는 두 집합의 교집합 $A_1 \cap A_2$ 구해서 빼면 $S_n$ 를 구할 수 있습니다.
$n = 3 $ 이라면 어떨까요? 다음과 같은 그림을 생각하면 편합니다.

1. 세개의 각 집합을 따로 더하고,
   ($(a + b+ c +d ) + (e+b+c+f) +(d+c+f+g) = a+ e+ g+ 2f+ 2b+2d+3c$)
2. 각각 두개의 집합씩 교집합 하여 중복되는 원소부분을 빼고,
   ($a+ e+ g+ 2f+ 2b+2d+3c - ((b + c) + (d+ c) + (c+ f) ) = a+ e+g+f+b+d$)
3. 마지막으로 모든 세개의 집합이 교집합하여 중복되는 원소를 다시 넣어줍니다.
   $a+e+g+f+b+d+ c = S_n$

$n$ 이 점점 늘어날수록 계산해야되는 식의 길이는 점점 더 길어질 것입니다. 사실, 자세히 생각해보면 전체 합집합 $S$ 를 계산할때 사용하는 $A$ 의 부분집합은 단 한번만 사용된다는 것입니다.
예를 들어볼까요? 우선 편의상 $\{A_{i},A_{j}\}$ 를 집합 $A_i$ 와 $A_j$ 의 교집합이라 하겠습니다. $n=3$ 일때 $A$ 는 $A = \{A_1, A_2, A_3\}$ 으로 표현되고, 위의 식 $S_n$ 을 구하기 위해서는 $\{\emptyset\}, \{A_1\},\{A_2\},\{A_3\},\{A_1, A_2\}, \{A_{2}, A_{3}\}, \{A_{1}, A_{3}\}, \{A_{1},A_2,A_3\}$ 의 집합이 필요합니다. 결과적으로 $A$ 의 집합 원소 갯수가 $n$ 개 일때, 총 $2^n$ 개의 조합이 필요합니다. 포함 배제 원리를 적용하기 위해서 필수적으로 알아야할 부분입니다. 왜냐하면 포함 배제 원리 자체는 어떤 문제에 적용하냐에 따라 달라질 수 있겠지만, 몇몇 적용되는 포함 배제 원리를 이용한 방법은 시간 복잡도를 크게 잡아먹기 때문에, 실용적이기 전에, 배보다 배꼽이 더 커버리는 경우가 발생할 수 있기 때문입니다. 그래서 어느정도의 계산이 필요되는지 알아둬야 합니다.

예제

$A$ 가 $4$ 개의 집합을 가지고 있다고 가정하겠습니다 :

$A_1 = 1,2,3$
$A_2 = 2,3,4$
$A_3 = 1,3,5$
$A_4 = 2,3$

이 예제의 최종 목표는 위의 모든 집합들의 합집합으로 나온 원소들의 개수를 구하는 것입니다. 편의를 위해 $A_{i, j}, A_{i, j, k}, A_{i, j, k, l}$ 의 값은 각각 $A_i $ 와 $A_j$ 의 교집합, 그리고 $A_i , A_j , A_k$ 의 교집합, 마지막으로 $A_i, A_j, A_k, A_l$ 의 교집합으로 하겠습니다.

$S_n$ 을 구했던 공식을 사용하면 다음과 같이 수식이 구해집니다.

$|A_1| + |A_2| + |A_3| + |A_4| - |A_{1,2}| - |A_{1,3}| - |A_{1, 4}| - |A_{2,3}| - |A_{2,4}| - |A_{3,4}| $
$ + |A_{1,2,3}| + |A_{1,2,4}| + |A_{1,3,4}| + |A_{2,3,4}| - |A_{1,2,3,4}|$

너무 길어서 끊어 썼습니다..; 이번 예제는 상당히 원소의 갯수도 작고 간단하기 때문에 눈으로 보고도 어떤 원소들이 교집합을 이루는지 알 수 있습니다. 그래서 바로 각 교집합들이 이루는 집합에 들어있는 원소의 전체 갯수들을 구할 수 있습니다.

$$ 3 + 3 + 3 + 2 - 2 - 2 - 2 - 1 - 2 - 1 + 1 + 2 + 1 + 1 - 1 = 5 $$

이제 이 예제를 풀 수 있는 코드를 짜보도록 하겠습니다.

Implementation

int intersectionCardinality(vector<int> indices)

위의 함수는 $A_i$ 의 집합들을 교집합 시켰을때 만들어지는 집합의 총 원소 갯수를 반환하는 함수 입니다. 여기서 $i$ 는 벡터 index 들을 나타냅니다.

전체 집합 $A$ 에 존재하는 집합들 $A_1 , A_2 , \dotsc , A_n$ 들을 이용해서 모든 부분집합들을 만들어내고, 만들어진 각각의 부분집합들을 이용해 intersectionCardinality(vector<int> indices) 함수를 통해 값을 구하고, 마지막으로 적절한 부호를 덧붙여 모두 더하면 우리가 원하는 값이 만들어 집니다.

int n; // 전체 집합 A 에 들어있는 집합의 갯수 

// 최종 결과값, A 의 모든 부분집합들이 이루는 원소의 갯수들의 합 
// (the cardinality of sum of all subsets of A)
int result = 0; 

for(int b = 0; b < (1 << n); ++b)
{
     vector<int> indices;
     for(int k = 0; k < n; ++k)
     {
          if(b & (1 << k))
          {
               indices.push_back(k);
          }
     }
     int cardinality = intersectionCardinality(indices);
     if(indices.size() % 2 == 1) 
         result += cardinality;
     else 
         result -= cardinality;
}
cout << result << endl; //결과값 출력

위에서 '전체 합집합을 계산할때 전체 집합 $A$ 의 부분집합들은 오직 한번씩만 사용되기 때문에, 총 $2^n$ 개의 부분집합이 필요하다' 라는 언급을 드린적이 있는데 기억하시나요? 이 개념을 사용하기 위해 가장 바깥쪽 for loop 에서 변수 b 는 총 1 << n 번 반복문을 수행합니다. (비트 연산자를 아신다면 1 << n = 2^n 라는것을 캐치하실 수 있을거라 믿습니다.)

그리고 반복문 내부에서 매 반복마다 $A$ 의 부분집합을 벡터 지시자 (vector indicator) 를 통해 만듭니다. $n = 3$ 을 기준으로 예시를 들어보도록 하겠습니다. $n=3$ 일때 $A$ 는 $A = \{A_1, A_2, A_3\}$ 으로 표현되고, 위에서 언급된 $S_n$ 을 구하기 위해서는

$$\{\emptyset\}, \{A_1\},\{A_2\},\{A_3\},\{A_1, A_2\}, \{A_{2}, A_{3}\}, \{A_{1}, A_{3}\}, \{A_{1},A_2,A_3\}$$

의 집합이 필요합니다. 이것을 벡터 지시자로 표현하면 각각 다음과 같습니다.

$$\{ 000 \},\{ 001 \}, \{ 010 \} , \{ 100 \}, \{ 011 \}, \{ 011 \}, \{ 101 \}, \{ 111 \}$$

위 코드중 아래에 적힌 부분은 b 변수를 10진수 형태가 아닌 바이너리, 즉, 2진수 형태로 만들어 줍니다.

if(b & (1 << k))
{
	indices.push_back(k);
}

예를 들어 n 은 3이고 b 가 7 이라고 가정했을시에, k = 0 일때 1 << k 는 001 이 되고, b 는 2진수로 표현시 111 이므로 001 & 111= 001 = True 가 되어 index 0 이 삽입되고, k = 1 일때는 1 << k = 010 그리고 b & ( 1 << k) = 111 & 010 = 010 = True 가 되어 index 1 이 삽입됩니다. k = 2 일때도 역시 100 값으로 True 가 되어 index 2 가 삽입되게 됩니다. 결과적으로 indices 벡터는 0, 1, 2 의 값이 들어와 , $\{A_{1},A_2,A_3\} $ 가 표현되어 집니다. 이런 방식으로 전체 집합 $A$ 의 부분집합을 모두 표현할 수 있습니다.

마지막으로 $S_n$ 을 구할때

$$S_n = \sum_{i = 1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \ldots + (-1)^{n - 1} \cdot |A_1 \cap \ldots \cap A_n|$$

교집합을 하려는 부분집합의 개수가 홀수개면 부분 집합에서 교집합을 통해 만들어진 원소의 갯수들에게 $+$ 부호를 붙이고 짝수라면 $-$ 부호를 붙입니다. 그리고 최종값에 더합니다.

---

위의 예제는 포함 배제의 원리를 가장 흔하게 적용할 수 있는 문제중 하나입니다.

또 다른 문제는 이런것이 있습니다.

숫자 $n$ 이 주어졌을때, $[1,n]$ 범위에서 무작위로 정수를 하나 뽑을 경우 그 숫자가 적어도 $2, 3, 11, 13$ 중에 하나라도 나눠질 수 있는 정수를 뽑을 확률을 구하기.

조금 어렵나요? 저도 그렇게 생각합니다. 그래도 꾸준히 바라보면 이해가 가는거 같네요. 아닌가? 아무튼 조금더 정진해서 위와 같은 문제의 해설도 작성해보도록 하겠습니다.