문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이 Etc

문제

『문제로 풀어보는 알고리즘』149쪽 문제 3.c

자연수 n을 입력받아 집합 {0, 1, 2, …, n-1}을 하나 이상의 집합으로 나누는 방법을 모두 출력하는 프로그램을 작성하세요.

[실행 예]

input n: 3
{0, 1, 2}
{0} {1, 2}
{1} {0, 2}
{2} {0, 1}
{0} {1} {2}

 

* 참고 *

1. n의 범위는 크게 상관이 없지만, 대략 16 이하라고 가정하시면 되겠습니다. ^^

2. 집합으로 나눈 경우를 출력하는 방법은 상관없습니다.

- {1} {0, 2}를 {0, 2} {1}로 표현해도 되고, 1, 0 2로 표현해도 됩니다. (다른 형식도)
- 또, {0} {1, 2}가 먼저 출력되든, {0} {1} {2}가 먼저 출력되든 상관 없습니다. 빠짐없이 출력하기만 하면 됩니다.

풀이


원소 수가 A개인 어떤 집합의 부분집합 개수 P(A)는
\begin{eqnarray}
P(A) = 2^A
\end{eqnarray}으로 나타낼 수 있다. 공집합을 제외하면 1을 뺀 수가 될 것이다.
이 문제에서는 모든 나눌 수 있는 방법을 출력하는 것이기 때문에, 각 원소들에 대해 재귀적으로 접근하여 부분집합을 병합하는 방법이 있을 것이다. 먼저, 집합의 모든 부분집합의 원소의 개수가 하나인 부분집합의 개수는 입력수인 k개가 될 것이다. 우리는 k개의 그룹을 돌면서 재귀적으로 각 원소들을 하나씩 병합함으로써 새로운 부분집합을 출력할 수 있다. 여기서 제약조건으로 들어가는 부분은, 중복을 피하기 위해 병합하려는 부분집합 A의 마지막 원소보다 병합되는 부분집합 B의 첫번째 원소가 커야 한다는 것이다. 그렇지 않다면, A와 B의 합집합은 이전의 재귀에서 이미 만들어졌던 부분집합이 되어버린다.

예를 들어, (0) (1) (2) (3) 의 부분집합으로 시작하여 각 원소를 돌며 하나씩 합쳐 가며 부분집합을 병합해 나가면 (0) 부분집합의 다음 셋들은 아래와 같이 재귀적으로 구해진다:

(0, 1) (2) (3)
(0, 1, 2) (3)
(0, 1, 2, 3)

이는 순차적으로 구해질 수 있는 모든 부분집합의 병합을 나타내며, 다음 부분집합 그룹인 (2)는 그 다음 인덱스인 (3)부터 병합함으로써 (0, 1, 2) 가 나오는 일을 피한다. k=4에서의 부분집합들로 나눌 수 있는 방법들은 아래와 같다 :

(0)(1)(2)(3)
(0,1)(2)(3)
(0,1,2)(3)
(0,1,2,3)
(0,1,3)(2)
(0,1)(2,3)
(0,2)(1)(3)
(0,2,3)(1)
(0,2,)(1,3)
(0,3)(1)(2)
(0,3)(1,2)
(0)(1,2)(3)
(0)(1,2,3)
(0)(1,3)(2)
(0)(1)(2,3)
정리해 보면, 겹치지 않는 부분집합의 개수가 15개 임을 알 수 있다.

소스코드


printfGroup은 부분집합들을 출력, findAllSubset은 k개의 유닛 셋들을 받아 모든 병합셋을 찾는 함수이다.

void    printGroup(vector< vector< int > > &set)
{
for(int i = 0; i < set.size(); ++i)
{
if(set[i].size() < 1) continue;

printf("{ ");
for(int j = 0; j < (set[i]).size()-1; ++j)
printf("%d, ", (set[i])[j]);
printf("%d }", set[i][(set[i]).size()-1]);
}
printf("\n");
}

void findAllSubset(vector< vector< int > > set, const int group, const int idx)
{
if(group == 0) return;

printGroup(set);

// merging
for(int p = idx; p < set.size(); ++p)
{
if(set[p].size() < 1) continue;
for(int i = p+1; i < set.size(); ++i)
{
if(set[i].size() < 1) continue;

// if the first element set B is larger than the last element of set A, merge it
if(set[i][0] > set[p][set[p].size()-1])
{
// push - we do it because of the ordering
int size = set[i].size();
for(int j = 0; j < set[i].size(); ++j)
{
set[p].push_back( set[i][j] );
}

// pop
while(set[i].size() > 0) set[i].pop_back();


// recursion
findAllSubset(set, group-1, p);


// restore
for(int j = 0; j < size; ++j)
{
set[i].insert(set[i].begin(), set[p][set[p].size()-1]);
set[p].pop_back();
}
}
}
}
}

덧글

댓글 입력 영역