Diary/오일러프로젝트300번문제 : GyparkWiki

/오일러프로젝트300번문제

(해결되었습니다: /오일러프로젝트300번문제2)

도대체 제 풀이에 어디가 문제인지 몰라서 도움을 청하려고 작성합니다.

문제는 [여기]

문제를 요약하면,

단백질 패턴은 H또는 P원소로 구성됨 (예: HHPPHHHPHHPH)
단백질은 H와 H가 서로 이웃하는 부분이 최대가 되도록 접히려는 성질이 있다.
- 아래 그림은 HHPPHHHPHHPH 패턴의 경우. 좌측처럼 접히면 H-H의 갯수가 6개, 우측은 9개. 이 단백질의 경우는 9개가 최적

H와 P는 동일한 확률로 나온다고 가정
문제: 최적의 상태로 접힌 길이 15인 단백질 패턴의 H-H 접촉지점의 갯수의 평균은?
- 예제: 길이 8인 경우는 850 / 2^8 = 3.3203125

예를 들어 길이4인 경우를 생각하면, (편의상 H를 1, P를 0으로 해서 이진수처럼 나타냄)

패턴    최적으로 접혔을 때 접촉지점의 갯수
0000    0
0001    0
0010    0    (1이 하나 이하라면 어떻게 접히든 1-1 쌍이 나올리 없음)
0011    1    (11의 경우는 어떻게 접히든 1-1 쌍이 하나)
0100    0
0101    0
0110    1
0111    2
1000    0
1001    1    (정사각형 형태로 접힐 때 두 1이 만남)  11
1010    0                                           00
1011    2
1100    1
1101    2
1110    2
1111    4    (정사각형 형태로 접힐 때 최적)
---------
합     16
평균 = 16 / 2^4 = 1

이런 문제에 익숙하다면 훨씬 빠르게 푸는 알고리즘을 생각할 수 있겠지만, 저는 일단 딱히 떠오르는 게 없어서 그냥

길이 15개인 패턴이 접힐 수 있는 모든 형태를 미리 만들어두고
2의 15승(=3만여)개의 패턴에 대해 각 형태에 대입하면서 H와H가 만나는 지점의 갯수를 세는

방법을 썼습니다.

처음에 작성했더니 길이가 8인 경우(문제에서 예제로 알려준)에 정답을 맞추더군요. 그래서 길이 15에 대해 풀라고 실행했더니... 오래 걸릴 거라 예상은 했지만 밖에 나가 밥을 먹고 돌아왔는데도 끝나지 않더군요. (아무래도 길이가 1 늘어날 때마다 가능한 조합이 기하급수적으로 늘어나니...)

그래서 여기저기 손보면서 불필요하고 무의미한 계산을 최대한 없앴습니다. 현재는 제 컴퓨터(애슬론 듀얼코어 5600+, 2.9GHz, Strawberry perl 5.10.0)에서 10분 걸리네요. 여전히 과하게 긴 감이 있습니다만...

문제는 시간도 시간이지만... 그렇게 10분에 걸쳐 풀었는데 답을 사이트에서 입력하면 틀렸다고 나옵니다. ㅠ,.ㅠ

처음에는 원인을 몰라서 끙끙댔습니다. 그러다가 혹시 나눗셈 계산하면서 결과가 반올림된게 아닌가 싶더군요. 그래서 나눗셈 하기 전 분자와 분모를 따로 출력했습니다:

분모 (총합) = 264957
분자 (2의 15승) = 32768
분모/분자 = 8.085845947265625
프로그램에서 출력할 때는 끝자리가 반올림되어서 8.08584594726563 으로 출력

이제는 맞았겠지 했는데... 저 값을 넣어도 여전히 안 됩니다 -_-?

저는 아무리 들여다봐도 "8자리일 때는 맞추는데 15자리일 때는 틀릴" 만한 구석을 못 찾겠습니다.

아래는 제 소스코드입니다. 코드패드 쪽에도 올려놨습니다. [여기]. 남의 코드 보는 게 아무래도 불편할터라 최대한 주석에 설명을 상세히 달아두었습니다만...

검증을 위해 길이 3부터 14까지의 실행결과도 적어두겠습니다.

제 프로그램의 실행결과.
길이 8의 경우를 제외하고 정확하다는 보장 없음
길이 15의 경우는 틀렸다고 나옴
 길이   총합 패턴갯수  평균
    3      4      8    0.5
    4     16     16    1.0
    5     46     32    1.4375
    6    133     64    2.078125
    7    335    128    2.6171875
    8    850    256    3.3203125
    9   1999    512    3.904296875
   10   4737   1024    4.6259765625
   11  10766   2048    5.2568359375
   12  24595   4096    6.004638671875
   13  54521   8192    6.6553955078125
   14 121601  16384    7.42193603515625
   15 264957  32768    8.085845947265625

#!perl
# Problem 300
# 답은 264957 / 32768 = 8.085845947265625 ? 근데 오답이라 나옴;;;
# 컴퓨터에서는 나눗셈의 결과가 8.08584594726563 로 마지막 자리가 잘리니 주의
# 
use strict;
use warnings;

my $LENGTH =  $ARGV[0] || 8;

sub ver8 { #{{{

    # 단백질의 길이 - 명령행 인자로 받거나, 기본값 8
    my $length = $LENGTH;

    # 현재 좌표의 상하좌우에 추가로 원소를 배치할 경우 좌표 계산을 위한 오프셋
    my %next = (
        up    => [ -1, 0 ],
        down  => [  1, 0 ],
        left  => [  0,-1 ],
        right => [  0, 1 ],
    );


    # 가능한 형태들의 리스트
    # $fold[0] 은 길이 0인 단백질이 취할 수 있는 형태들의 배열 (당연히 없다)
    # $fold[1], $fold[2] 는 각각 길이 1, 2인 단백질이 취할 수 있는 형태들 (1가지씩)
    # 길이 1인 경우는 당연히 1가지이고, 길이 2인 경우는 총 4가지가 있겠지만:
    #        1
    #        0     10     01     0
    #                            1
    # 어차피 다 같은 형태니까 처음 두 원소는 아래로 붙어있는 마지막 형태만 취급
    my @fold = (
        # 원소 0개
        [ ],
        # 원소 1개
        [
            {
                coord => [ [ 0, 0 ] ],
                neighbor => [ ],
                elems => { "0,0" => "0" },
            }
        ],
        # 원소 2개
        [
            {
                coord => [ [ 0, 0 ], [ 1, 0 ] ],            # 각 원소의 [ y, x ] 좌표
                neighbor => [ ],                            # 순서상 인접한 원소들 외에 추가로 이웃이 되는 원소의 인덱스 쌍의 배열
                elems => { "0,0" => "0", "1,0" => "1" },    # coord의 역으로, "y좌표,x좌표"를 키로 하고 해당 좌표에 있는 원소의
                                                            # 인덱스를 값으로 하는 해쉬. 특정 좌표에 이미 원소가 있는지 확인할 때 사용
            }
        ],

        # 예를 들어 원소 4개인 단백질의 경우
        #      0    0    0     0     03
        #      1    1    123   12    12
        #      2    23          3
        #      3
        # 이렇게 다섯개의 구조가 있다.
        # (두번째~다섯번째 형태는 좌우 대칭인 형태가 하나씩 있으나 이건 결국 동일한 형태이니 생성하지 않음)
        # 따라서 $fold[4]는 익명 해쉬 5개가 원소로 있는 익명 배열이고,
        # 다섯번째 구조를 나타내는 익명 해쉬의 예를 들면
        # {
        #    coord => [ [0,0], [1,0], [1,1], [0,1] ]   # 0~3번 원소의 y,x 좌표값들
        #    neighbor => [ [0,3] ]                     # 0번과 3번 원소가 추가로 이웃이 되었음
        #    elems => { "0,0"=>"0", "1,0"=>"1", "1,1"=>"2", "0,1"=>"2" }  # coord 의 역. 좌표=>원소인덱스
        # }
        # 이런 형태가 된다.
    );



    # 이제 길이 15개인 단백질이 취할 수 있는 모든 형태를 생성한다.
    # 길이2의 형태에서 마지막 원소인 1번 원소 상하좌우에 2번 원소를 붙여 길이3이 취할 수 있는 형태를 생성하고,
    # 다시 길이3의 각 형태에 대하여 마지막 2번 원소에 3번 원소를 상하좌우에 붙여 길이4의 형태들을 생성하는 식의 반복

    for my $l ( 3 .. $length ) {

        my @temp_fold = ();     # 길이 $l 짜리의 형태들의 배열

        foreach my $combi ( @{$fold[$l-1]} ) {      # 길이 $l-1 짜리 각 형태에 대하여
            my $lc = $combi->{coord}[-1];           # 마지막 원소의 좌표
            my $nc;                                 # 새로 추가될 $l번째 원소의 좌표
            my $ni = scalar @{ $combi->{coord} };   # $l번째 원소의 인덱스

            foreach my $dir ( qw/up right down left/ ) {

                # 이전 형태가 세로로만 이어진 막대 형태라면 이 때는 left 는 right 와 대칭이 되므로 패스
                if ( $lc->[0] == $ni - 1 and $dir eq "left" ) {
                    next;
                }

                # 추가될 원소의 좌표 계산
                $nc = [
                    $lc->[0] + $next{$dir}[0] ,
                    $lc->[1] + $next{$dir}[1]
                ];

                # 이 좌표가 이미 사용되었는지 검사
                if ( exists $combi->{elems}{ $nc->[0].",".$nc->[1] } ) {
#                     print "[ $nc->[0], $nc->[1] ] is used\n";
                }
                else {
                    # 새 원소가 추가된 형태 생성
                    my $new_combi = {
                        coord => [ @{$combi->{coord}} , $nc ],  # 좌표 배열은 기존 형태의 좌표 배열에 새 좌표 추가
                        neighbor => [ @{$combi->{neighbor}} ],  # 기존 형태의 이웃원소 목록, 아래에서 새 이웃 추가
                        elems => { %{$combi->{elems}} },        # 기존 형태의 좌표=>원소인덱스 해쉬
                    };
                    $new_combi->{elems}{ $nc->[0].",".$nc->[1] } = $ni; # 새 원소의 좌표=>인덱스 추가

                    # 새 원소와 인접하는 네이버들 찾음
                    foreach my $d ( qw/up right down left/ ) {
                        my $ec = [
                            $nc->[0] + $next{$d}[0],
                            $nc->[1] + $next{$d}[1],
                        ];
                        next if ( $ec->[0] == $lc->[0] and $ec->[1] == $lc->[1] );  # 직전 원소는 당연히 이웃이니 패스
                        if ( exists $new_combi->{elems}{ $ec->[0].",".$ec->[1] } ) {
                            push @{$new_combi->{neighbor}}, [ $new_combi->{elems}{$ec->[0].",".$ec->[1]} , $ni ];
                        }
                    }

                    push @temp_fold, $new_combi;
                }
            }
        }

        # DEBUG
#         { #{{{
#             # DEBUG용 출력.
#             print "----- new fold list (length: $l) ----\n";
#             foreach my $combi ( @temp_fold ) {
# 
#                 foreach my $y ( -1*$l .. $l ) {
#                     foreach my $x ( -1*$l .. $l ) {
#                         if ( exists $combi->{elems}{"$y,$x"} ) {
#                             print $combi->{elems}{"$y,$x"};
#                         }
#                         else {
#                             print " ";
#                         }
#                     }
#                     print "\n";
#                 }
# 
#                 print "neighbor => ";
#                 foreach my $coord ( @{$combi->{neighbor}} ) {
#                     printf "[%2d,%2d] ", $coord->[0], $coord->[1];
#                 }
#                 print "\n";
#                 print "\n";
#             }
#         } #}}}

        # 길이 $l에 대하여 모든 형태가 만들어졌음.
        # 이 형태들을 네이버 갯수가 많은 순으로 정렬을 하여 저장.
        # 정렬을 하는 이유는 나중에 불필요한 비교를 하지 않기 위함.
        $fold[$l] = [ sort { scalar(@{$b->{neighbor}}) <=> scalar(@{$a->{neighbor}}) } @temp_fold ];
    }

    # 이 시점에서 길이0부터 15까지의 모든 형태가 만들어졌다.
    # 그런데 위에 주석으로 적은 원소4개 단백질의 다섯 가지 형태를 보면,
    # 처음 네 가지는 추가로 이웃이 되는 원소가 한 쌍도 없다는 점에서 결국 동일한 형태라고 간주할 수 있다.
    # 이렇게 동일한 형태들은 한 가지만 남기고 제거한다.
    for (my $l = 3; $l <= $#fold; $l++) {
        my $temp = [];
        my %seen = ();

        foreach my $combi ( @{$fold[$l]} ) {    # 길이 $l의 각 형태들에 대하여
            my $str = join ":",
                        map { @$_ }
                          sort { ( $a->[0] <=> $b->[0] ) or ( $a->[1] <=> $b->[1] ) }
                            @{$combi->{neighbor}};

            unless ( $seen{$str} ) {            # 현재까지 나타나지 않았던 이웃조합의 형태 하나씩만 저장
                $seen{$str} = 1;
                push @$temp, $combi;
            }
        }

        $fold[$l] = $temp;
    }


    # 이제 형태 생성은 끝났음.
    #
    # 지금부터는 길이 15의 모든 단백질 2**15 개에 대하여,
    # 위에서 생성한 형태에 대입하여 H-H 가 만나는 CP의 갯수를 세고,
    # 각 단백질마다 최대의 CP값을 찾고,
    # 그 최대 CP값들의 합을 구한다.


    my $total_max_cp = 0;    # 최대 CP 값의 합

    # H또는 P로 구성된 단백질이니까 이진수처럼 생각할 수 있다.
    # H는 1, P는 0에 대응한다.
    # 따라서 2**15 - 1 까지의 수에 대해서 루프를 돈다.
    foreach my $num ( 3 .. (2**$length - 1) ) {
        my $str = sprintf ("%0${length}b", $num);       # 이진수 형태로 변환
        my @strs = split //, $str;                      # 특정 자리가 1인지 0인지 비교할때 substr을 써도 되지만, 알아보기 쉽게 배열로도 변환

        # 일단 스트링의 홀수번째 자리와 짝수번째 자리에 각각 하나 이상의 1이 있어야만 이웃이 생길 여지가 있다.
        # 그렇지 않다면 패스
        unless ( $str =~ /1(?:00)*1/ ) {
            next;
        }

        my $cp = 0;     # 일단 연속으로 배치된 1에 의해 생기는 CP의 갯수

        # $str에서 "11"의 갯수만큼 CP가 생긴다.
        # 예를 들어 00111001100 이면 CP는 최소 3개
        while ( $str =~ /1(?=1)/g ) {
            $cp++;
        }

        # 연속된 1의 그룹이 딱 하나만 있는 경우는 이걸로 끝이다.
        # 예: 000111100, 011000000 등
        if ( $str =~ /^0*111?0*$/ ) {
            $total_max_cp += $cp;
            next;
        }

        # 여기서는 형태에 직접 대입하기 전에, 미리 CP값을 눈으로 알 수 있는 것들을 추려냄
        # (그런데 CP값이 항상 그렇게 보장되는지 확신은 없다;)
        #
        # 1 하나씩 떨어져 있는 형태는 최대 CP값은 1
        # 예: 0100001000
        if ( $str =~ /^0*1(?:00)+10*$/ ) {
            $total_max_cp++;
            next;
        }
        # 11그룹 두개는 최대 CP값이 4이다.
        # 예: 01100001100
        if ( $str =~ /^0*11(?:00)+110*$/ ) {
            $total_max_cp += 4;
            next;
        }
        # 111그룹 두개는 최대 CP값이 7
        # 예: 00011100111
        if ( $str =~ /^0*111(?:00)+1110*$/ ) {
            $total_max_cp += 7;
            next;
        }
        # 1111그룹 두개는 최대 CP값이 10
        if ( $str =~ /^0*1111(?:00)+11110*$/ ) {
            $total_max_cp += 10;
            next;
        }
        # 여기까지가 추려내는 부분



        # 남은 경우는 별 수 없이 일일이 형태들에 대입하면서 추가적으로 나타나는 CP값을 구해야 한다.

        # 그런데 스트링의 뒷부분이 0으로 채워진 곳은 굳이 검사할 필요가 없다.
        # 예를 들어 001101110000000 패턴의 경우 마지막 PPPPPPP 는 어떻게 접히든 H-H의 갯수와 무관.
        # 따라서    00110111        패턴이라 생각하고 길이 8짜리 형태들과 비교하면 된다.

        my $t_length;       # 실제 검사할 길이 (마지막 "1"까지의 길이)
        if ( $str =~ /1(0*)$/ ) {
            $t_length = $length - length($1);
        }

        my $max_add_cp = 0; # 추가적인 CP 갯수의 최대값

        foreach my $combi ( @{$fold[$t_length]} ) {     # t_length 길이의 형태들에 대하여 루프.

            my $add_cp = 0;     # 이번 형태에서 추가로 생기는 CP의 갯수

            # 처음에 형태를 만들때 "추가적인 이웃쌍의 갯수"의 내림차순으로 정렬하였다.
            # 예를 들어 어떤 단백질 패턴 P 가 있을때
            # 이 루프 안에서 현재까지 발견한 가장 큰 추가CP 값이 4인데,
            # 이번에 검사할 $combi의 이웃쌍의 갯수가 4라면,
            # 그 이웃쌍이 전부 1에 대응된다해도 어차피 추가CP값이 4이다.
            # 따라서 검사할 필요가 없고,
            # 루프를 더 이상 반복할 필요도 없다. (이웃쌍의 갯수가 점점 줄어들테니)
            if ( $max_add_cp >= @{$combi->{neighbor}} ) {
                last;
            }


            # combi 형태와 단백질 패턴을 대응해서 CP의 값을 구한다.
            # 예를들어 combi->{neighbor} 배열이 [ [ 1, 7 ], [ 2, 5 ] ] 라면
            # @strs의 1번과 7번 인덱스의 원소가 각각 1이라면 H-H이므로 add_cp 값이 1 증가
            # 2번과 5번 인덱스도 마찬가지
            foreach my $n ( @{$combi->{neighbor}} ) {
                if ( $strs[$n->[0]] and $strs[$n->[1]] ) {
                    $add_cp++;
                }
            }

            if ( $max_add_cp < $add_cp ) {
                $max_add_cp = $add_cp;
            }
        }

        # 앞에서 구한 cp (연속된 1에 의해서 생기는)
        # 방금 구한 max_add_cp (서로 떨어져 있는 1이 만나서 생기는)
        # 둘을 합친 것이 이 패턴 P의 최대 CP값이다.
        # 이 합친 값을 total_max_cp 에 더한다.
        $total_max_cp += $cp + $max_add_cp;
    }

    # 모든 패턴에 대해 검사가 끝났음. total_max_cp 값과, 평균값 출력
    print "total CP = $total_max_cp\n";
    print "# of patterns = ", 2**$length, "\n";
    print "average = ", $total_max_cp / (2**$length), "\n";
} #}}}

ver8();
exit;

-- Raymundo 2010-9-10 11:31 pm

Comments & Trackbacks

와 정말 도대체 어디가 문제인거지? 설마 그 사이트의 정답이 잘못 등록된 건 아닐테고... 90여명이 이미 풀었으니...

-- Raymundo 2010-9-11 9:59 pm

일단 문제만 보고, 생각만 정리 해봤네용...

1. 일단 이거 복잡도가 겁나큰 문제군요.
일단 숫자가 조금만 늘어도 사실상 P!=NP 문제가 되버리네요.
2. 특정 스트링패턴(DNA)이 가지는 모양은 한개 또는 다수입니다.(최대화)
근데 스트링패턴이 특정 모양에 겹쳤을때, '사실상' 중복되는 케이스는 없을까요?
(자세히 보진 않았지만 이게 좀.. 의심되네요)
3. 분산처리 해볼만한게 없을까요?(연산이 문제가 없다면 분산처리 해야겠네요)
저장 구조는 어떻게 가져가야 할까요? (전 비트맵 구조가 떠오르네요)
4. 어떻게 쓸데없는 녀석들을 초기에 커팅해 볼수 있을까요?

대략 ACM 3급수준 문제 되겠습니다. ~_~);

-- 죠짱 2010-9-14 1:01 am

최적화 이슈는
요거 보니까, 미리 패턴을 만들고, 최적 해를 먼저 계산이 가능하겠구요.
그걸 베이스로 하는거죠.
긍까 Raymundo님이 한 반대 방법으로 가보는거죠. 그럼 계산 최적화가 어느정도 되겠네요.

그리고 2^8을 생각한다고 해서 2^8이 될수도 있겠지만 환형을 생각하면 경우의 수가 줄어듭니다. 그말인 즉슨, asdf가 a-f가 만날경우 sdfa 랑 같다는 거죠. (동형, 동질) 요 케이스가 중복 패턴이라는 이야기구요. 아무래도 있을것 같군요. 그리고 아무리 짝수라도 asdf 일때 a만 따로 노는 경우가 없을까요? 있을거 같은데요. 그경우는 동형/동질의 패턴이 없겠군요.

그냥 자기전에 몇개 생각만 해봤습니다. 자러 가야지요

-- 죠짱 2010-9-14 1:16 am

일단 "패턴"이라는 말이 "어떻게 접혔느냐"와 "H와 P가 어떻게 조합되었느냐"에 둘 다 사용가능하니... 전자는 "형태", 후자를 "패턴"이라 칭하겠습니다.

제 풀이의 경우 "사실상 같은" 폴드 형태는 최대한 걸렀습니다.

- 형태를 90도씩 회전시킨 경우는 애초에 제외.
- 형태의 상하 또는 좌우대칭 형태도 생성 과정에서 제외.
- 각 길이별 형태을 다 만든 후에, 형태는 서로 다르지만 인접하는 이웃쌍이 동일한 경우를 제거 ([소스]의 55번라인 주석에서 처음 네 가지는 다 동일하죠)
- 그 외에 몇 가지 떠오르는 걸 시도해봤는데 그럼 아예 풀이에 오류가 생기길래 보류.

그리고 최적화 이슈의 경우...

저는
loop1: for ( 0 부터 2^n-1 까지의 모든 패턴에 대하여 )
loop2: for ( 생성해낸 형태 각각에 대입하면서 )
H-H CP 값 계산
을 하고 있는데,

문제 자체가 "모든 패턴에 대해 통틀어서 CP가 최대인 경우 얼마일까?" 이런 거라면 쉽겠는데 "각 패턴의 최대 CP값을 구해서 그 평균을 내라"다보니까, loop1 에서 반복 횟수를 줄이기가 힘들더군요. 그럼 loop2 에서 더 줄일 방법이 있나 봐야 하는데...

말씀하신대로 최적해를 (최적 형태를 의미하신 거 맞죠?) 먼저 구하려 해보았습니다. 그런데 이것도 생각처럼 쉽지 않았던게.. 최적 형태란 것도 결국 어느 패턴이 와서 대입되느냐에 따라 달라지겠더라고요.

예를 들어서
형태1:
0
1
2345
9876
형태2:
01
32
4
56789
위 두개의 경우 "최대로 생길 수 있는 CP의 갯수"는 형태1이 더 많습니다만, 패턴이 "111100000" 이라면 이 패턴은 형태2에서 CP값이 더 커지죠.

이걸, "그러면 환형처럼 생각해서 패턴을 쉬프트 시키면..."이라고 생각도 해봤는데, 쉽지도 않거니와 그 계산하느니 그냥 루프한번 더 도는 것과 비슷해보이기도 하고.

결정적으로, 저는 일단 계산 시간은 한시간이 걸려도 좋으니 정답부터 맞춰내보고 싶은데 답이 오류가 나고 있어서... =ㅅ=;;; 혹시 성공하시게 되면 답은 미리 말씀하지 마시고 제 실행 결과에서 길이가 몇일 때부터 틀렸는지 알려주시면 감사하겠습니다~ ^_^

-- Raymundo 2010-9-14 8:05 am

뭐래는 거얌..

-- Zehn02 2010-9-14 10:18 pm

: 으이구 악플러!
-- Raymundo 2010-9-14 10:33 pm

주인장분류

Diary/오일러프로젝트300번문제

/오일러프로젝트300번문제

Comments & Trackbacks

Diary

최근 글들

코멘트와 트랙백

옛 글들

RSS

주요 페이지