== [[/문제로_풀어보는_알고리즘_149쪽_문제_3.c_풀이]] ==
http://www.insightbook.co.kr/wp-content/uploads/2012/07/8966260462_f21-234x300.jpg
[http://www.insightbook.co.kr/post/3855 알고리즘 코딩 이벤트 1주차 2번째 문제 | 도서출판 인사이트]
위 사이트에서 이벤트를 하길래 겸사겸사 풀어봤음.
{{{
자연수 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}가 먼저 출력되든 상관 없습니다. 빠짐없이 출력하기만 하면 됩니다.
}}}
풀어보자.
원소가 하나인 집합 {0}을 나누는 방법은 한가지 뿐이다.
{0}
원소가 두개인 집합 {0,1}을 나누는 방법은, 다음과 같이 두가지이다.
원소가 하나인 집합을 나누는 방법에서,
1) 기존의 집합 {0}에 새 원소 1을 추가하든가
{0,}
2) 새 원소 1을 새로운 부분집합으로 만들든가
{0},
원소가 세개인 집합 {0,1,2}를 나누는 방법 역시, 원소가 두개인 집합을 나누는 방법에서 다시 새 원소 2를 어떻게 추가하냐에 따라 결정된다.
위 1)에서 2를 기존 집합에 추가하거나
{0,1,}
새 집합으로 만들거나
{0,1},
위 2)에서 2를 기존 집합 중 하나에 추가하거나
{0,},{1}
{0},{1,}
새 집합으로 만들거나
{0},{1},
고로 원소의 갯수가 n이면, n-1개짜리 집합을 나누는 경우를 구하고, 각각의 경우에 대하여 기존 집합 중 하나에 추가하는 경우들과, 새로운 집합으로 추가하는 경우를 구하면 된다.
[[Perl]]로 짠 코드:
{{{#!vim perl
#!/usr/bin/env perl
use strict;
use warnings;
use 5.010;
# 매번 원소의 갯수를 입력하기 귀찮으니 명령행 인자로 받자
my $n = $ARGV[0] // 4;
my @set = ( 0 .. $n-1 );
subset( \@set, [] );
exit;
sub subset {
my ( $set, $subsets ) = @_;
# 더 이상 남은 원소가 없으면 그때까지 구성된 부분집합들을 출력하고 종료
if ( @$set == 0 ) {
foreach my $subset ( @$subsets ) {
print "{", join(",", @$subset), "}";
}
print "\n";
return;
}
# 아직 남은 원소가 있다면
# 그 중 첫번째 원소를 뽑아낸 후
my $elem = $set->[0];
my @cur_set = @$set[ 1 .. $#$set ];
# 뽑아낸 원소를 기존의 부분집합들 중 하나에 추가하고
# 남은 원소와 현재까지 구성된 부분집합을 인자로 하여 재귀호출
foreach my $n_sub ( 0 .. $#$subsets ) {
my $cur_subset = [ @$subsets ];
$cur_subset->[$n_sub] = [ @{$cur_subset->[$n_sub]}, $elem ];
subset( \@cur_set, $cur_subset );
}
# 뽑아낸 원소를 새로운 부분집합으로 만들고 재귀호출
subset( \@cur_set, [ @$subsets, [ $elem ] ] );
}
}}}
{{{#!vim
[gypark@www insightbook_3855]$ perl subset.pl 4
{0,1,2,3}
{0,1,2}{3}
{0,1,3}{2}
{0,1}{2,3}
{0,1}{2}{3}
{0,2,3}{1}
{0,2}{1,3}
{0,2}{1}{3}
{0,3}{1,2}
{0}{1,2,3}
{0}{1,2}{3}
{0,3}{1}{2}
{0}{1,3}{2}
{0}{1}{2,3}
{0}{1}{2}{3}
}}}
잘 돌아간다.
문제에서는 N을 16이하로 가정했던데... 원소16개짜리 배열을 위와 같이 나누는 경우의 수가 몇개나 될까?
|| 집합의 원소 갯수 || 나누는 경우의 수 || 수행 시간 ||
|> 2 |> 2 |> 0.103초 ||
|> 3 |> 5 |> 0.103초 ||
|> 4 |> 15 |> 0.104초 ||
|> 5 |> 52 |> 0.102초 ||
|> 6 |> 203 |> 0.103초 ||
|> 7 |> 877 |> 0.103초 ||
|> 8 |> 4,140 |> 0.155초 ||
|> 9 |> 21,147 |> 0.244초 ||
|> 10 |> 115,975 |> 0.622초 ||
|> 11 |> 678,570 |> 0.876초 ||
|> 12 |> 4,213,597 |> 1.462초 ||
|> 13 |> 27,644,437 |> 5.012초 ||
|> 14 |> 190,899,322 |> 30.297초 ||
|> 15 |> 1,382,958,545 |> 3분 31초 ||
|> 16 |> 10,480,142,147 |> 26분 37초 ||
* 나누는 경우의 수는 검증을 위해 직접 계산...했을 리는 없고 저 코드에 카운트를 세도록 하여서 출력시킨 거다. 맞겠지 뭐.
* 수행 시간은... 저 [[Perl]] 코드는 원소갯수 14개째부터 너무 느려져서... 똑같은 형태로 JAVA로 짰다. 각 부분집합과 부분집합들의 그룹은 ArrayList로 만들었음. Perl의 경우 N이 12일 때 12초 정도 걸리고 16일 때는 한시간이 걸려도 끝날 기미가 안 보여서 껐음
자그마치 104억 가지가 넘는다... 처음에는 별 생각 없이 출력을 파일에 기록하게 했는데, 한시간쯤 후에 파일 크기가 10기가가 넘어가는 걸 보고 황급히 껐음ㅋ
===== Comments & Trackbacks =====
----
[[주인장분류]]