알고리즘: 재귀함수(6) 예제 - 멱집합 ( powerset )

멱집합이란?

 

S의 모든 부분집합을 원소로 하는 집합을 S의 멱집합이라 하며, P(A) 혹은 2의 S승으로 나타낸다.

만약 S의 원소 개수가 n개라면, 멱집합의 갯수는 2의 n승이다.

 

---

 

 

멱집합 예제

어떤 집합의 모든 부분집합의 집합을 멱집합이라고 함

 

ex ) 원소의 갯수가 n개인 집합의 모든 가능한 부분 갯수의 집합 갯수 :   2의 n승

즉, 2의 n승의 서로 다른 경우의 수가 존재함

 

그렇다면 크기가 n인 모든 부분 집합의 경우의 수는 어떻게 출력할 수 있을까?

 

 

 

예시 데이터

{ a, b, c, d, e, f }의 모든 부분 집합을 나열하려면
a를 제외한 { b, c, d, e, f }의 모든 부분집합들을 나열하고 { b, c, d, e, f }의 모든 부분집합에 { a }를 추가한 집합들을 나열함

고등학교 수학으로 돌아가보겠습니다.

 

먼저 원리를 요약하자면 어떤 부분집합의 모든 부분집합을 구하려면 해당 집합에서 원소 하나를 제거한 다른 집합의 부분집합을 구하는 일을 한다면, 원래 집합의 부분집합을 구할 수 있습니다.

 

 

include와 exclude가 바뀌었습니다. 이를 참고하시어 반대로 보시면 되십니다.

 

상태 공간 트리

• 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리
• 트리의 모든 노드를 방문하면 원하는 해를 찾을 수 있음
• 루트에서 출발해 체계적으로 모든 노드를 방문하는 절차를 기술함

 

1단계.  { a } 기준

 

a, b, c, d, e, f 의 부분집합들은 크게 보면 [ a를 포함하지 않는 것들 ]과 [ a를 포함하는 것들 ]로 나뉩니다. 

 

먼저 (1) a를 포함하지 않는다는 것은 b부터 f까지 다섯 개의 부분집합들과 같으며,

(2) a를 포함하는 것은 b, c, d, e, f의 부분집합들을 모두 구해 a를 다 추가해주면 그것이 a를 포함하는 부분집합들이 됩니다.

 

편의상 (1)과 (2)로 표현하겠습니다.

 

(1)은 b, c, d, e, f의 부분집합들로 '총 2의 5승' 개가 있으며, (2)는 모든 부분집합들에 a를 포함하면 되기에 마찬가지로 '2의 5승'개가 있습니다.  이 둘이 합쳐져 총 경우의 수는 '2의 6승' 개라고 보면 됩니다.

 

 

2단계.  { b } 기준

 

조금 더 설명을 해보겠습니다.

{ a }를 제외한 나머지 부분집합은 다시 두 가지로 나뉩니다. (3) { b }를 포함하지 않는 집합과 (4) { b } 를 포함하는 집합입니다.

 

{ b, c, d, e, f } 의 모든 부분집합에 { a }를 추가한 집합들을 나열하려면,

 

• { c, d, e, f }의 모든 부분집합들에 { a }를 추가한 집합들을 나열하고,
  
  
• { c, d, e, f }의 모든 부분집합에 { a, b }를 추가한 집합들을 나열합니다.

우리가 해야 할 일은 { a }는 기본으로 추가해 출력을 해야하기에 위에서 설명하였듯이 { c, d, e, f }의 모든 부분집합들에 { a }를 추가한 집합들을 나열합니다. 이는 앞서 이야기한 (3)번인 { b } 를 포함하지 않는 경우입니다.

 

두 번째로 { c, d, e, f }의 모든 부분집합에 { a, b }를 추가한 집합들을 나열합니다. 이로 (4) 번인 { b }를 포함하는 집합을 만들 수 있습니다.

 

 

3단계.  { c } 기준

 

다시 위의 방법을 반복합니다. { b }를 제외한 뒤 남은 집합은 또 다시 두 가지 갈래로 나뉩니다.

 

{ c }를 포함하는 경우와 { c }를 포함하지 않는 경우로 말입니다. 이때 마찬가지로 집합 { d, e, f }의 모든 부분집합들에 { a }를 추가한 집합들을 나열하고, { d, e, f }의 모든 부분집합에 { a, c }를 추가한 집합들을 나열합니다.

 

---

 

문제 풀기

 

집합 S의 멱집합을 출력하세요.