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

[알고리즘 코딩 이벤트 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,1}

2) 새 원소 1을 새로운 부분집합으로 만들든가

 {0},{1}

원소가 세개인 집합 {0,1,2}를 나누는 방법 역시, 원소가 두개인 집합을 나누는 방법에서 다시 새 원소 2를 어떻게 추가하냐에 따라 결정된다.

위 1)에서 2를 기존 집합에 추가하거나

 {0,1,2}

새 집합으로 만들거나

 {0,1},{2}

위 2)에서 2를 기존 집합 중 하나에 추가하거나

 {0,2},{1}
 {0},{1,2}

새 집합으로 만들거나

 {0},{1},{2}

고로 원소의 갯수가 n이면, n-1개짜리 집합을 나누는 경우를 구하고, 각각의 경우에 대하여 기존 집합 중 하나에 추가하는 경우들과, 새로운 집합으로 추가하는 경우를 구하면 된다.

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 ] ] );
}

[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

저 페이지에 가니까 다른 사람들이 올린 것 중에 C++로 짠 게 있어서 그걸로 N=16일 때를 돌렸더니 그건 55분 걸렸네... 알고리즘이 좀 다르긴 했지만.