1 번째 수정본 소스 보기 : Diary/문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이

내용출력
로그인[l]
수정할 수 없습니다: Diary/문제로_풀어보는_알고리즘_149쪽_문제_3.c_풀이 는 읽기 전용 페이지입니다.
#TEMPLATE [[Diary/DynamicTemplate]]
<div class="diary">
== [[/문제로_풀어보는_알고리즘_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}을 나누는 방법은 한가지 뿐이다.
<blockquote>
{0}
</blockquote>

원소가 두개인 집합 {0,1}을 나누는 방법은, 다음과 같이 두가지이다.
<blockquote>
원소가 하나인 집합을 나누는 방법에서,

1) 기존의 집합 {0}에 새 원소 1을 추가하든가
 {0,<color(red,1)>}
2) 새 원소 1을 새로운 부분집합으로 만들든가
 {0},<color(red,{1})>
</blockquote>

원소가 세개인 집합 {0,1,2}를 나누는 방법 역시, 원소가 두개인 집합을 나누는 방법에서 다시 새 원소 2를 어떻게 추가하냐에 따라 결정된다.
<blockquote>
위 1)에서 2를 기존 집합에 추가하거나
 {0,1,<color(red,2)>}
새 집합으로 만들거나
 {0,1},<color(red,{2})>
위 2)에서 2를 기존 집합 중 하나에 추가하거나
 {0,<color(red,2)>},{1}
 {0},{1,<color(red,2)>}
새 집합으로 만들거나
 {0},{1},<color(red,{2})>
</blockquote>

고로 원소의 갯수가 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기가가 넘어가는 걸 보고 황급히 껐음ㅋ
<mysign([[Raymundo]],2012-9-1 5:53 pm)>


===== Comments & Trackbacks =====
<longcomments(100)>
----
[[주인장분류]]
</div>
Diary/문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이 페이지로 돌아가기 | 다른 수정본 보기