liquidbird's blog

breeze

마음 속에 멈추지 못한 바람

Breeze

2010

2010
piano. 6:05

2010

harpsibossa

Sounds :
  harpsichord, electric piano : Pianoteq 3

Harpsibossa

Guitar+Piano sketch

느린 것부터 하나. 베이스와 최소한의 드럼 정도 추가 또는 이대로 기타+피아노만.

어떤 카인드 오브 리버 느낌의 제목

( 다음엔 코드 복잡하고 리드미컬한 depapepe style 빠른 곡도 하나 )

TED - David Deutsch : Parallel universes and you

평행우주에 대한 짧은 이야기 선문답

아래는 받아쓰기 (영어대본이 아직 없어서 안 들리는 부분은 확인불가. xxxx, () 등으로 적었음. )

Chris Anderson :
You (want)  x xxxxx x xxxxxxxx of the parallel universe and teleportation of the quantum theory.
How is it doing in the sort of battle for (mine) space among physicists, among leading physicists.
You are winning or loosing?

David Deutsch :
I think it's gradually creeping forwards.
Younger people don't like mystical interpretations of quantum mechanics (so they had done) so much harm during the last 70 odd years.
And they then have a choice that face with an existential choice, either shut up and calculate which the majority do, or believe the Everret's multiple universes interpretaion of quantum mechanics.
And those are maybe 90 percent or 89 percent and 10 percent. I don't think there're more than one percent of physicists who believe in anything other than those two things.

Chris Anderson :
Someone who beilieves in parallel universes, does it change how you experience this live?
Does it give you... How do you think of them? How do you think free will for example in relation to that, at all?

David Deutsch :
First of all, we have to have a true explanation of the world otherwise we're try to explain the world in terms of things that (untrue) like gods and goddesses.
The fact that there are parallel universes affects all sorts of things about that... but they all (feed) in to human considerations indirectly.
For instance, there are centuries all debate about what (role?) determinism has immorality.
You know, some people think that if we're determined by law of physics, we can't be reponsible for our actions.
And other people think since we are responsible for our actions, the law of physics can't be deterministic or even physics can't be fundamental (haven't) for bit.
But if you understand parallel universes and teleportation you see there's a rich in a substructure there that can accommodate what people want, both in terms of physics being in fundamental and in terms of there being such things as free will and new knowledge and so on.

Chris Anderson :
So you believe that you can choose which universe to inhabit in a sense?

David Deutsch :
No, not quite. We have it them all in different proportions.
It's more that knowing that they're there gives a framework for understanding what it means to choose something.

Chris Anderson :
Ok. (laughter) It's strange enough I actually find not inspiring. David Deutsch, thank you so much.


아래는 대강 간단히 한글로.

질 : 평행우주론이 어떻게 좀 받아들여지고 있나?

답 : 조금씩 나아지는 것 같다. 안 믿는 사람이 9, 믿는 사람이 1 정도이고 나머지는 거의 없지.

질 : 평행우주를 믿으면 삶에 영향이 있나? 자유의지라든지 뭐 그런 거.

답 : 먼저 우주를 정말 제대로 설명할 수 있어야 돼. 신 같은 걸로 설명하려고 하지 말고.
     결정론이랑 물리법칙은 상충한다고 생각하기 쉬운데, 평행우주는 둘 다를 만족시켜 주지.

질 : 그래서 넌 니가 어느 우주에 살지 결정할 수 있다는 거야?

답 : 아니 그런 게 아니야. 우린 모든 우주를 서로 다른 비율로 갖고 있어.
     다른 우주들이 거기 존재한다는 사실을 알게 되면, 뭔가를 선택한다는 게 무슨 의미인지를 이해할 수 있는 틀을 가지게 되는 거야.

질 : 어.. 뭔 소린진 모르겠는데 여튼 되게 고마워.

my flow, your flow

conflux

My_flow_your_flow

자유롭게 흘러가는 곳으로

meant to be together

만남.
가까와짐.
일체감.

서로의 마음 속에 들어갈 수 있는 사람은 일생에 몇 명이나 될까.
우린 누구를 만나도록 되어 있는 것일까.

Meant_to_be_together

on the hillside

바람 부는 푸르른 산중턱에 앉아
저 멀리 마을에 돌아가는 물레방아, 흐르는 강물 위 좁은 나무다리를 건너는 아이들,
해질녘 바알갛게 물든 집들과 거리

가고 싶다. 보고 싶다.

On_the_hillside

가스펠 하나

가스펠 중에도 좋은 곡들이 많습니다. 이게 벌써 언제적 곡인가.

Thenameinme

google code jam 문제 하나 풀어봅시다 - 풀이편

단어의 글자수는 3이고, 사전의 표제어는 다음과 같이 5개 있는 경우를 예로 들겠습니다.
사전에 몇 번 등장하는지 찾아야 할 대상 단어들 (이하 '문제단어'로 호칭) 은 2개라고 하겠습니다.

[사전의 표제어들]
abd
aed
efw
oli
fse

[사전에 몇 번 나오는지 알아내야 하는 단어들 = 문제단어들]
uiw
a(bel)(irdxq)

이제 uiw 과 a(bel)(irdxq) 가 각각 사전의 표제어에 몇 번씩 일치되는지를 알아내면 끝입니다.
답은 다음 형식으로 출력하면 됩니다. (XXX, YYY는 각각 사전에 등장한 횟수)
case #1 : XXX
case #2 : YYY

1. 망하는 풀이

사람이 사전을 찾을 때와 같은 식으로 푸는 방법입니다.

- 문제단어 각각에 대해
 - 사전의 표제어들 각각과 일치하는지 검사하여  일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력

먼저 case #1 (즉 단어 'uiw') 의 경우는 간단합니다.

문제단어 'uiw'가 사전의 첫번째 표제어 'abd'와 일치하는지 검사하면 일치하지 않으니까 그냥 넘어가고, 사전의 두번째 표제어 'aed'와 일치하는지 검사하여 또 일치하지 않으니 그냥 넘어가고, ..., 마지막 표제어 'fse'와도 일치하지 않으니 넘어가고, 더이상 사전에 표제어가 없으면 끝입니다.
한번도 일치하지 않았으니까 일치횟수는 0이군요.

여기까진 문제가 없습니다.

다음 case #2 ( 단어 a(bel)(irdxq) ) 의 경우는 이런 방식으로 하면 다음과 같이 하게 됩니다.

문제단어가 확정된 것이 아니라   a(bel)(irdxq)   와 같이 여러 단어가 될 가능성이 있으므로 이를 풀어 보면 다음과 같은 단어조합이 가능합니다.

abi
abr
abd
abx
abq
aei
aer
aed
aex
aeq
ali
alr
ald
alx
alq

1*3*5 = 15개의 조합이 나왔습니다. 문제단어 a(bel)(irdxq) 는 표현상으로는 1개의 단어처럼 보이지만 실제로는 15개의 단어가 될 가능성을 가지는 것입니다.

이제 다음 풀이 방법을 적용시켜 보자면

- 문제단어 각각에 대해
 - 사전의 표제어들 각각과 일치하는지 검사하여  일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력

문제단어 각각에 대해 사전 표제어 각각과 일치하는지 검사해야 하는데, 앞에서 문제단어가 1개가 아니라 15개가 되어 버렸습니다.

따라서

- 15개의 문제단어 각각에 대해
 - 사전의 5개의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력

과 같이 계산해야 하므로, case #1에서 1개의 문제단어에 대해 사전의 5개의 표제어와 일치검사시에는 1*5=5번의 계산만 수행하면 되었던 것에 비해서 이번에는 15*5=75번의 계산이 필요합니다.

75번의 계산을 수행하면 결과는 '2회 일치'라는 것을 알 수 있습니다.
이 정도 표제어 수와 이 정도 조합의 단어까지는, 사람의 눈으로 보면 바로 몇 개가 일치하는지 보이죠.

이 정도까진 그냥 하면 되지 않냐 할 수 있는데, 단어의 길이가 10이고 문제단어가 다음과 같은 경우를 생각해 봅시다.

(qweasdzxcv)(poiuytrewq)(afdgs)(eydhcn)o(ethi)(bnvn)(asdfghjklm)(yt)(ghfjdk)
10 * 10 * 5 * 6 * 1 * 4 * 4 * 10 * 2 * 6 = 5,760,000

문제단어 1개가 실제로는 오백 칠십 육만개의 단어조합을 나타냅니다.
조합을 만들 때 가능한 경우의 수는 곱하기로 늘어나기 때문에 걷잡을 수 없이 커집니다.
이런 문제단어가 1000개라면? 오십 칠억 육천만개의 단어조합이 되지요.
그리고 사전의 표제어가 1000개라면? 오십칠억육천만 * 1000 번의 계산이 필요합니다.

계산할 수는 있겠지만 시간이 얼마나 걸릴지 알 수 없습니다. 그래서 망하는 풀이입니다.

2. 진짜 풀이

우선 문제를 다시 정리해 보죠.

다시 사전의 표제어를 살펴보겠습니다.

abd
aed
efw
oli
fse

그리고 문제단어들입니다.

uiw
a(bel)(irdxq)

case#2 인 단어 'a(bel)(irdxq)' 의 경우 다음과 같은 문제단어조합이 나오고, 이 중에 표제어와 일치하는 것은 abd와 aed의 2 개입니다.

abi
abr
abd
abx
abq
aei
aer
aed
aex
aeq
ali
alr
ald
alx
alq

그럼 이번엔 이렇게 풀어보겠습니다.

- 사전의 각 표제어에 대해서
 - 문제단어와 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴

case #1은 뻔하니까 case #2 에 대해 풀어봅시다.

1) 1번째 사전 표제어 'abd' 가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
    - 첫번째 글자는 'a'로 같으니까 OK
    - 두번째 글자는 사전표제어 'b' 가 문제단어의 '두번째 글자로 가능한 글자들 (bel)' 에 포함되니까 OK
    - 세번째 글자는 사전표제어 'd' 가 문제단어의 '세번째 글자로 가능한 글자들 (irdxq)' 에 포함되니까 OK
    - 마지막 글자까지 모두 일치했으니까 일치횟수 1 증가
2) 2번째 사전 표제어 'aed' 가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
    - 풀이는 똑같으니 생략함. 마지막 글자까지 모두 일치하니까 일치횟수는 또 1 증가하여 2가 됨.
3) 3번째 사전 표제어 'efw'가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
    - 첫번째 글자가 'e'와 'a'로 서로 다르니까 FAIL
    - 두번째 글자부터는 볼 필요 없음
4) 4번째 사전 표제어 'oli'가 ....
    - 풀이 생략. FAIL
5) 5번째 사전 표제어 'fse'가 ...
    - 풀이 생략. FAIL

이와 같이 계산하여, case#2의 단어는 모든 사전 표제어에 대해 2번 일치함을 구했습니다.

이 경우에는 단어의 글자수가 늘어나고, 사전의 표제어 수가 많아지고, 문제단어 수가 많아져도 조합을 만들지 않기 때문에 소요시간이 기하급수적으로 증가하지 않습니다.

즉 이 문제 풀이의 핵심은 '조합을 만들지 않는 것' 에 있습니다.

좀 더 구체적인 사항으로는, 각 과정에서 다음과 같은 계산을 할 때
  [ 사전표제어의 두번째 글자인 'b'가 문제단어의 두번째 글자로 가능한 (bel) 에 포함되는지 검사 ]
어떤 방법으로 검사하느냐에 따라 속도 차이가 납니다.

예를 들어  글자 'a' 가  (guiwpzanbmxc) 에 포함되는지를 검사할 때,  (guiwpzanbmxc) 의 각 글자에 대해 a와 일치하는지를 순차적으로 검사할 수도 있습니다.
  - 'g'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'u'로 넘어가고
  - 'u'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'i'로 넘어가고
  - ...
  - 'z'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'a'로 넘어가고
  - 'a'가 'a'와 같은지 검사하여 같으니까 이번 그룹에 대해서는 일치한다고 판단.

이렇게 검사하면, 괄호 안의 글자들 중 a의 위치에 따라 계산속도가 달라집니다. a가 처음에 나오면 바로 일치한다고 판단할 것이고, 맨 마지막에 나오면 그때까지 계산을 반복해야 합니다.

이렇게 하지 않으려면 (guiwpzanbmxc) 를 그냥 텍스트나 배열로 만들어서 순차적으로 비교하는 것이 아니라, 다음과 같이 hash ( = map ) 의 형태로 만들어 놓고
   { 'g' => 1, 'u' => 1, ... , 'c' => 1 }
이 hash가 'a'라는 key를 가지는지 아닌지를 판단하면 됩니다.
( 이때 value는 뭐든 상관없습니다. value를 찾는 것이 목적이 아니라 해당 key가 존재하는가만 이용합니다. )
hash는 내부적으로 key를 빨리 찾기 위한 최적화된 자료구조를 가지고 있기 때문에 순차적인 계산을 수행하지 않으며, 그룹 내의 글자수가 많아져도 빨리 찾을 수가 있습니다.

예를 들어 hash가 내부적으로 b*tree로 이루어져 있을 경우, (abcdefghijklmnopqrstuvwxyz) 라는 26개의 글자를 가지는 그룹의 각 글자를 hash의 key로 만든 hash  안에 'q'가 있는지 없는지를 찾는 경우
 - 1번째 계산 : 2개로 분리된 그룹들 (13개 / 13개) 중 q가 속할 수 있는 그룹이 선택됨
 - 2번째 계산 : q가 속할 가능성이 있는 그룹이 다시 2개로 분리 (6개 / 7개) 되어 이 중 다시 q가 속할 수 있는 그룹이 선택됨
 - 3번째 계산 : 다시 2개로 분리 (3개 / 4개) 되어 이 중 q가 속할 수 있는 그룹이 선택됨
 - 4번째 계산 : 다시 2개로 분리 (2개 / 2개) 되어 이 중 q가 속할 수 있는 그룹이 선택됨
 - 5번째 계산 : 마지막으로 분리된 글자수 2개의 그룹에 q가 있는지 검사.
이와 같은 식으로 처리됩니다.

이 방법의 좋은 점은, 그룹 내의 글자수가 100개 증가해도 계산해야 하는 횟수가 100번 증가하는 게 아니라는 점이지요.

여튼 이런 생각을 프로그램으로 만들면 다음과 같이 됩니다. (사실 후딱 짜고 나서 정리한 거지만) 딱 100줄이네요.
변수의 scope를 따져서 reference를 서브루틴으로 넘기거나 이런 건 하지 않았습니다. 돌아가는 데 집중한 코드입니다.

#!/usr/bin/perl

use strict;
use warnings;
use FileHandle;

my $dataFileName = 'A-small-attempt0.in';
my @dic;               # 사전
my @message;           # 사전과 대조해볼 단어들, 즉 case 들
my @messageInDicCount; # 각 case 가 사전의 표제어들 중 몇 개와 일치하는지. 프로그램의 목표는 이것을 구하는 것.
my $wordLength;        # 단어의 길이. 사전의 표제어이든 사전과 대조해볼 단어든 모든 단어의 길이는 일정함.
my $dicEntryTotalNo;   # 사전에 들어 있는 표제어의 수
my $messageTotalNo;    # 사전과 대조해볼 단어들의 수

makeStructure();

calculate();

printout();

# 데이터파일을 읽어서 사전과 메시지 데이터구조를 만든다.
sub makeStructure {

    my $ifh               = new FileHandle( $dataFileName, 'r' );
    my $linecount         = 0;
    my $dicAddedCount     = 0;
    my $messageAddedCount = 0;

    while (<$ifh>) {

        $linecount++;
        chomp;
        my $line = $_;
        next if $line =~ m| \s* \# |x;
        next if $line =~ m|^$|;

        if ( $linecount == 1 ) {
            ( $wordLength, $dicEntryTotalNo, $messageTotalNo ) = split ' ', $line;
        }
        elsif ( $dicAddedCount < $dicEntryTotalNo ) {
            push @{ $dic[$dicAddedCount] }, split '', $line;
            $dicAddedCount++;
        }
        elsif ( $messageAddedCount < $messageTotalNo ) {
            my $position = 0;
            while ( $line =~ m/ ( \(\w+\) | \w ) /xg ) {
                my $element = $1;
                $element =~ s/\(//;
                $element =~ s/\)//;
                my @elArray = split '', $element;
                for my $el (@elArray) {
                    $message[$messageAddedCount]->[$position]->{$el} = 1;
                }
                $position++;
            }
            $messageAddedCount++;
        }
    }
}

# 메시지 데이터구조 내의 각 메시지건들이 각각 사전의 표제어들 중 몇 개와 일치할 수 있는지를 구한다.
sub calculate {

    $messageInDicCount[$_] = 0 for ( 0 .. $#message );

    my $entryNo = 0;
    for my $entry (@dic) {
        my $messageNo = 0;
        for my $message (@message) {
            my $letterPosition = 0;
            for my $entryLetter ( @{$entry} ) {
                unless (
                    defined(
                        $message[$messageNo]->[$letterPosition]->{$entryLetter}
                    )
                  )
                {
                    last;
                }
                $letterPosition++;
                if ( $letterPosition == $wordLength ) {
                    $messageInDicCount[$messageNo]++;
                }
            }
            $messageNo++;
        }
        $entryNo++;
    }
}

sub printout {

    for my $messageIndex ( 0 .. $#messageInDicCount ) {
        $messageInDicCount[$messageIndex] = 0
          unless defined $messageInDicCount[$messageIndex];
        print "case #"
          . ( $messageIndex + 1 )
          . " : $messageInDicCount[$messageIndex]\n";
    }
}

그리고 이 프로그램이 돌아갈 때 입력으로 받는 'A-small-attempt0.in' 파일 내용은 다음과 같습니다.

10 25 10
dheoyyidga
ebxfffvhqx
yjjpteklgp
yjwfawdkal
kgmjlupidf
feqrtmvgzd
vxnrcpqhzq
tlyhukdlsh
taljrgxoow
rjwgdyvtiw
ldjjmgvqrq
zkqmwjutzj
qqsmzvmwqw
vbzelmkgce
wdqopmxjgw
sypnmoiakb
xhcwmnkywm
esrvhghgsp
fmpuzdkkew
lbenzsdkqz
yxrqsawbjq
todikcmums
sxtwnuoqeh
pdeitylrzu
isklduprqc
lkbehqyxgf
(vzep)bzelmkgce
(mrz)(jmg)(vbl)(ac)(zhn)(mqs)(dhj)(qbg)(rux)(yci)
(rtgo)(nya)(zhlr)(ijw)(rzch)(vgh)(xado)(vlno)(opfg)(pwd)
(uwxyabcdfghijklmoprs)(ghijklmnpqrsuvwxabcdef)(wxyzabcdfgjklmnoprstuv)(knopqrstuvwxyzacdefghij)(cdefghijklmnoqrstuvwxyzab)(jklmnopqruvwzabcdfgi)(tvwxyzabcdfghijkmnopqrs)(pqrstuvxyzabcdefghjklmno)(efghijklmnopqrsuvwxyzbc)(abcefhijklmnopstuvwxy)
(wxzacdefhijklmnopqrsv)(klnopqrstuvwxyabcdfghi)(rstuvwxyabcdefgijlmnopq)(yzabdefghijklopqstvwx)(yzbcdefghijklmnopqrstuvwx)(wyzabcefghjklmnopqrstuv)(qrstuvwxzabcefhikmnp)(oprstuwxyzabcdfghijkmn)(xyzabcdefghijklmnoprsuvw)(klmnopqrstuxzabcdefghj)
(nuxy)(zerx)(raeh)(cdqs)(stbl)(sap)(djnw)(bdlq)(bejo)(qzd)
(stuvwxyzabcdefghiklmnopq)(stuvwxyzacdefghjlmnopq)(bcdefgijklmopqrstuvwyza)(xyzbcdefghiklmnpqrstvw)(qrstuvwxyzabcdfgijklmno)(ijklmnopqrsvwxyabcdfg)(gijklmopqrstuvwxyzacef)(abdefghijkmnopqrstuvwxyz)(abdefghijlnopqrstuvwxy)(ghijnoqrstuwxyzabcdef)
(fgku)(kmno)(pwbk)(ua)(zdim)(ydps)(koqy)(ahkn)(kvye)(adjw)
(tuwxyzabcdefghijklmnopqrs)(ghkmnopqtuvwxyzabcdef)(rstuvwxzacdeghijkmnoq)(lmopqstuvwxyzabdfghik)(bcdefghjklmnopqrstuvwxy)(ghijklmopqrstuvwxyzacdef)(xyzabcdefghiklmnpqrstvw)(stuvwxyzacdefghijklmnoqr)(tuvyabdefghjklmnopqs)(xyzabcdfgjklmnopqrtuvw)

프로그램의 수행 결과는 다음과 같습니다.

case #1 : 0
case #2 : 1
case #3 : 0
case #4 : 1
case #5 : 3
case #6 : 4
case #7 : 1
case #8 : 2
case #9 : 1
case #10 : 3

실제 code jam의 문제는, 입력파일이 이렇게 작지 않고
 - 단어의 글자수는 15
 - 사전의 표제어는 5000개
 - 문제단어는 500개
입니다.

예를 들어 문제단어 하나가 이런 식입니다.

(xyabdefghiklnopqrstuvw)(tuvxyzabcdefijklmnopq)(yzacdefghijklmnopqrstuvx)(bcdfghiklmnopqrstuvxyza)(pqrstuvwxyzabdefghijklmno)(pqrsuvwxyzbcdeghijkmno)(rstuvxyabcdefijklmnopq)(jklmnopqstuvwxyzabcdegh)(cdefgijklmopqrstuvwxyza)(hjklmopqrstuvwxyzabcdefg)(wxyzabcdefgiklmnoqrsuv)(npqrstvwxyzabcdefghijklm)(efghjklmnopqrstvwxyzabcd)(xyzabcefghijklnopqrstuvw)(opqrstuvwxyzacdghijklmn)

이런 게 500개니까, 망하는 방법으로 풀면 언제 끝날 지 알 수 없겠지요.

여튼 요점은, '노가다도 잘 해야 한다' 입니다.