괴짜 프로그래머의 일상사~@@
프로그래밍, 컴퓨터, 그리고 일상에 관한 소소한 이야기들...
Blog | Guestbook
Keyword | Local | Tag
T 588 / Y 754 / Total 3471313
Catergories
Calendar
«   2023/09   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tag
워드 2007, 프로리그, 휴리스틱, 함수 호출 규약, parser, exceptional C++, 퍼즐, 세벌식, mfc, 캐리이반해적2, 인생, 홍진호, 호환성, 수퍼페치, 태그, 프레스티지, 포크, Heap, 부모님이 살아 계실 때 꼭 해드려야 할 45가지, 무승부,
Archive
Link
Search
  submit
Recent Articles
Recent Comments
Recent Trackbacks
2007/07/05 13:19
NIM 게임으로 배워보는 알고리즘 디자인
[GGGG]NIM 게임은 테이블 위에 놓여진 13개의 동전을 번갈아 가면서 1~3개까지 가져가서 마지막 남은 동전을 가져가는 사람이 지는 게임이다. NIM 게임에서 컴퓨터가 이기기 위한 알고리즘을 다양한 방법으로 구현해 보도록 하자.
 
1. 결정 트리
13개라는 동전의 개수는 우리가 한번에 생각하기에는 너무 많은 동전의 개수다. 따라서 게임이 진행된 후 자기 차례에 4개의 동전이 남은 상황을 생각해 보자. 이 상황에서 벌어질 수 있는 모든 일이 <그림 1>에 나와있다. <그림 1>과 같은 트리를 보통 결정 트리 내지는 게임 트리라고 부른다. 이 트리는 동전이 4개 남은 상황에서 앞으로 발생할 수 있는 모든 경우를 담고 있다.

트리를 보는 방법은 간단하다. 루트에 있는 4는 현재 동전이 네 개 남아있음을 나타낸다. 자식으로 3, 2, 1이 있는 것을 볼 수 있다. 각각은 우리가 한 개, 두 개, 세 개의 동전을 가져간 경우에 테이블에 남게 될 동전의 개수다. 각각의 상황에서 상대방이 선택할 수 있는 모든 경우가 그 노드의 자식으로 있다. 예를 들면, 3개가 남은 상황에서는 상대방의 선택에 따라 테이블에 동전이 두 개, 한 개, 내지는 없을 수 있는 것이다.

자 그렇다면 4개가 남은 상황에서 우리는 이기기 위해서 몇 개의 동전을 가져가야 할까? 당연히 똑똑한 플레이어라면 3개를 집을 것이다. 왜냐하면 세 개를 가져가고 나면 테이블엔 동전이 하나 밖에 남지 않아 무조건 이기기 때문이다. 반면에 한, 두 개를 가져간 경우엔 상대방의 선택에 따라 우리가 질 수도 있다.

 
사용자 삽입 이미지
그림 1 테이블에 4개의 동전이 남은 경우의 결정 트리

좀 더 복잡한 상황을 생각해 보자. 5개, 6개, 7개, 8개가 테이블에 남은 상황에 대한 결정 트리가 <그림 2>에 나와있다. 5개 남은 경우엔 이길 수 있는 방법이 없고, 6개 남은 경우엔 하나를 가져감으로써 이길 수 있다. 나머지 경우에 대해서도 곰곰 생각해 보자.

 
사용자 삽입 이미지
그림 2 테이블에 5, 6, 7, 8개의 동전이 남은 경우의 결정 트리


2. 분할 정복법 (Divide-and-Conquer)
분할 정복법은 큰 문제를 여러 개의 작은 문제로 분할한 다음 각각의 결과를 결합해서 큰 문제에 대한 해답을 찾는 방법이다. 큰 문제에서 점차적으로 작은 문제로 내려가는 형태를 취하기 때문에 이런 방식의 접근 법을 하향식(top-down) 접근법이라고 부른다.

앞서 살펴본 결정 트리를 위에서 아래로 내려가면서 문제를 푼다고 생각하면 간단하다. <리스트 1>에 분할 정복법을 사용한 코드가 나와있다. IsBad는 테이블에 coins의 개수만큼 동전이 남아있는 경우에 상대방이 이길 수 있는지 없는지를 나타낸다. IsBad(1)은 당연히 TRUE가 된다. IsBad(2), IsBad(3), IsBad(5)등의 리턴 값을 앞서 게임 트리를 보면서 생각해 보도록 하자. GetCoinCount는 테이블에 n개의 동전이 남았을 때 우리가 이기기 위해서 선택해야 하는 동전의 개수를 리턴 하는 함수다. GetCoinCount(4)는 3을 리턴 한다. 만약 n개의 동전이 남은 상황에서 이길 수 있는 방법이 없다면 0을 리턴 한다. 따라서 GetCoinCount(1), GetCoinCount(5)는 0을 리턴 한다.

리스트 1 top-down 방식으로 풀어본 NIM 게임
[CPP]int GetCoinCount(int coins);

int IsBad(int coins)
{
    if(coins <= 1)
        return TRUE;
    else
        return GetCoinCount(coins) == 0;
}

int GetCoinCount(int coins)
{
    for(int i=1; i<=3; ++i)
    {
        if(coins - I <= 0)
            break;

        if(IsBad(coins - i))
            return i;
    }

    return 0;
}[/CPP]
분할 정복법은 코드를 작성하기 쉽고 직관적이라는 장점이 있다. 하지만 분할 정복법의 가장 큰 단점은 결정 트리가 커질수록 경우의 수가 많아지고 반복적인 부분이 늘어나기 때문에 코드의 수행 속도가 비 정상적으로 느려진다는 단점이 있다. 얼마나 반복적인 부분이 많이 호출 되는지 알고 싶은 독자는 GetCoinCount, IsBad 함수의 시작 부분에 각각 printf를 추가한 다음 GetCoinCount(4)를 호출해 보도록 하자.

3. 동적 계획법 (Dynamic Programming)
동적 계획법 또한 분할 정복법과 마찬가지로 작은 문제의 답을 통해서 큰 문제의 답을 구한다는 점에서는 비슷하다. 하지만 동적 계획법은 분할 정복법과는 달리 한번 구해진 답을 계속 계산하지 않고 메모리에 저장해 두고 참고한다. 분할 정복법과 동적 계획법의 차이는 <그림 1>과 <그림 2>의 차이라고 할 수 있다. <그림 1>에는 동일한 노드가 여러 번 그려져 있다. 2개가 남은 경우에 대한 결정 트리가 두 번 포함된 것을 보면 알 수 있다. 하지만 <그림 2>에서는 이미 구해진 트리에 대한 부분은 표시를 하지 않았다. 전자가 분할 정복법 이라고 한다면, 후자의 그림은 동적 계획법이 된다. 분할 정복법이 트리를 위에서 아래로 타고 내려오는 형태라면, 동적 계획법은 트리를 하나의 노드에서 점진적으로 키워 나가는 형태를 취한다. 그래서 동적 계획법은 상향식(bottom-up) 접근 방법이다.

동적 계획법은 일반적으로 테이블을 사용해서 구현된다. 작은 문제에 대한 해답을 테이블에 기록해 둔 다음 이후에 그 값이 필요하다면 테이블을 참조해서 이미 구해진 답을 이용하는 것이다.

<리스트 2>에는 NIM 게임 테이블을 생성시키는 코드가 나와있다. GenerateNimTable 함수에 생성할 테이블 포인터와 개수를 입력하면 개수만큼 답을 구해서 테이블을 채워준다. win은 해당 노드에서 우리가 이길 수 있는지 없는지를 나타낸다. solution에는 각각의 선택에 대한 승, 패 여부가 기록된다. T가 GenerateNimTable 함수를 통해 생성한 테이블이라고 할 때, 5개가 남은 상황에서 우리가 이길 수 있는지 여부는 T[5].win을 참고하면 된다. 만약 이길 수 있는 노드라면 몇 개를 가져가야 이길 수 있는지는 T[5].solution[0], T[5].solution[1], T[5].solution[2]를 살펴보면 알 수 있다.

리스트 2 NIM 게임 테이블을 생성하는 코드
[CPP]#define MAX_SEL 3

typedef struct _NIMITEM
{
    bool    win;
    bool    solution[MAX_SEL+1];
} NIMITEM, *PNIMITEM;

void GenerateNimTable(PNIMITEM tb, int last)
{
    tb[1].win = false;
    for(int i=1; i<=MAX_SEL; ++i)
        tb[1].solution[i] = false;

    bool win;
    for(int i=2; i<=last; ++i)
    {
        win = false;
        for(int j=1; j<=3; ++j)
        {
            if(i-j > 0)
            {
                if(tb[i-j].win)
                    tb[i].solution[j] = false;
                else
                {
                    tb[i].solution[j] = true;
                    win = true;
                }
            }
            else
                tb[i].solution[j] = false;
        }

        tb[i].win = win;
    }
}[/CPP]
일반적으로 동적 계획법은 분할 정복법보다 이해하기 힘들고, 덜 직관적이다. 하지만 수행 속도는 분할 정복법보다 훨씬 빠르다는 장점이 있다. 왜냐하면 반복적인 부분을 다시 계산하지 않기 때문이다.

4. 휴리스틱
휴리스틱이란 우리가 경험이나 관찰에 의해서 알고 있는 지식을 통해서 알고리즘을 설계하는 것을 말한다. 교통 신호 제어 시스템의 알고리즘을 설계할 때 출, 퇴근 시간에 붐비는 도로에 더 많은 가중치를 두는 것이 그러한 예라고 할 수 있다.

<표 1>은 앞서 살펴보았던 동적 계획법으로 만들어진 테이블의 결과를 담고 있다. 테이블을 정렬해 두어서 규칙이 쉽게 눈에 들어올 것이다. 남은 동전의 개수에서 1을 뺀 다음 4로 나눈 나머지가 이기기 위해서 우리가 선택해야 하는 동전의 개수다. 여기서 0이 나오면 그 상황에서 우리가 반드시 이길 수 있는 방법은 없다는 것을 나타낸다. <리스트 3>에는 이러한 방법을 사용해서 개수를 구하는 GetCoinCount 함수가 나와있다.

표 1 동전 개수에 대한 승, 패 여부
개수    승, 패     개수   승, 패      개수    승, 패
1           패         5        패            9        패
2        승 (1개)    6      승 (1개)     10     승 (1개)
3        승 (2개)    7      승 (2개)     11     승 (2개)
4        승 (3개)    8      승 (3개)     12     승 (3개)

리스트 3 휴리스틱 방법을 사용한 코드
[CPP]int GetCoinCount(int coins)
{
    return (coins - 1) % 4;
}[/CPP]
휴리스틱 방법은 대부분의 경우 수행 속도가 빠르고, 좋은 실행 결과를 가진다는 장점이 있다. 하지만 그런 만큼 휴리스틱 알고리즘을 생각해 내기는 가장 어렵다. 물론 이렇게 간단한 문제에 대해서는 쉽게 답이 나오지만 복잡한 문제에 대해서는 몇 년을 고민해도 답이 나오지 않는 경우가 많다. 또한 휴리스틱을 사용한 코드는 별도의 주석이 없으면 나중에 유지 보수 하는 사람이 이해하기 어려운 코드가 되기 쉽다. 앞서 구현한 GetCoinCount의 경우도 왜 저렇게 하는지 부연 설명이 없다면 코드를 유지 보수하는 사람에게는 마치 마법 같은 코드가 되는 것이다. 따라서 이러한 코드에는 반드시 숫자들이 어디서 왔는지 그리고 그 원리가 무엇인지를 주석으로 남겨둘 필요가 있다.

Trackback : http://jiniya.net/tt/trackback/529
fap turbo 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://fapturbo2x.com/ 2014/10/30 19:46
fapturbo 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://ordinancetracker.com/ 2014/11/18 07:49
anita 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://makemoney890mcom.gearhostpreview.com/?c=4&p=41 2020/11/19 20:37
by reference 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://thebadabing.com/__media__/js/netsoltrademark.php?d=mxk2020.xsl.pt 2020/11/21 17:33
here 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://analitika.kz/?go=korecomtr.gearhostpreview.com%2F%3Fc%3D4%26p%3D370 2020/11/22 02:02
by reference 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://rapolanoterme.wordpress.com/2011/07/27/festival-accademia-delle-crete/ 2020/12/24 15:23
francoise 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://dorita.qualityassociates.org 2021/01/04 09:59
mari 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://www.pinterest.it/aconceiao/resume-writing-services/ 2021/01/11 20:34
here 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://mycareerapparel.com/__media__/js/netsoltrademark.php?d=www.pinterest.at%2Fanlegta%2Fcollege-essay-application%2F 2021/02/17 10:16
sdplumbingnetau.somee.com 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://sdplumbingnetau.somee.com/buy-admission-essay-online/page-39-2020-11-27.html 2021/02/20 04:39
creditdirectorycoza.gearhostpreview.com 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://creditdirectorycoza.gearhostpreview.com/buy-research-paper-online/page-288-2021-01-11.html 2021/02/21 11:49
uniapaemgorgbr.gearhostpreview.com 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://uniapaemgorgbr.gearhostpreview.com/professional-coursework-writers/page-68-2021-03-24.html 2021/04/26 08:50
10ln.c2.xsl.pt 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://10ln.c2.xsl.pt 2021/05/03 07:43
10lp.cq.xsl.pt 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://10lp.cq.xsl.pt 2021/05/03 10:18
matti 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://essay-leader.somee.com/big-dick/page-188-2021-07-01.html 2021/07/06 01:39
assets.pinterest.com 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://assets.pinterest.com/ext/embed.html?id=355080751878108348 2021/07/07 22:03
https://assets.pinterest.com/ext/embed.html?id=664281013791262051 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://assets.pinterest.com/ext/embed.html?id=664281013791262051 2021/07/07 22:06
https://assets.pinterest.com/ext/embed.html?id=298926494026163289 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://assets.pinterest.com/ext/embed.html?id=298926494026163289 2021/07/08 00:16
there 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://localbusiness.starnewsonline.com/__media__/js/netsoltrademark.php?d=assets.pinterest.com%2Fext%2Fembed.html%3Fid%3D277675133265644252 2021/07/27 00:56
electronic dissertation 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://y-fukushi-or-jp.somee.com/creampie-gangbang/page-143-2021-05-06.html 2021/08/13 05:02
there 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://visitrockportmaine.businesscatalyst.com/Redirect.aspx?destination=http%3a%2f%2fpinterest.com%2fpin%2f812266482796892053 2021/09/03 01:38
https://pinterest.com/pin/355080751878131058 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://pinterest.com/pin/355080751878131058 2021/09/03 05:25
https://pinterest.com/pin/635711303655756770 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 https://pinterest.com/pin/635711303655756770 2021/09/03 06:57
%E3%A7%8B%E3%9C%87.xsl.pt 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://%E3%A7%8B%E3%9C%87.xsl.pt 2021/10/20 07:06
tsk-g-co-jp.somee.com 괴짜 프로그래머의 일상사~@@ - NIM 게임으로 배워보는 알고리즘 디자인 http://tsk-g-co-jp.somee.com/japanese-wife/page-j16vtd87fs.html 2021/10/20 12:20
maid agency singapore (2020/03/23 23:38)
Great article with excellent idea!Thank you for such a valuable article. I really appreciate for this great information..

maid agency singapore (2020/03/23 23:38)
Great article with excellent idea!Thank you for such a valuable article. I really appreciate for this great information..

how to get rid of dandruff fast (2020/06/23 21:26)
Thanks for sharing the post.. parents are worlds best person in each lives of individual..they need or must succeed to sustain needs of the family.

fluorococaine buy (2020/06/26 22:44)
I like this post,And I guess that they having fun to read this post,they shall take a good site to make a information,thanks for sharing it to me.

SD-WAN (2020/06/27 19:34)
Great knowledge, do anyone mind merely reference back to it

previous (2020/06/27 21:45)
It proved to be Very helpful to me and I am sure to all the commentators here!

paving a driveway (2020/07/11 11:33)
This is a great article thanks for sharing this informative information. I will visit your blog regularly for some latest post.

the travelers within (2020/07/15 19:10)
Friend, this web site might be fabolous, i just like it.

citizenship for sale (2020/07/20 20:10)
I would like to say that this blog really convinced me to do it! Thanks, very good post.

roof replacement (2020/08/01 15:08)
Your blog provided us with valuable information to work with. Each & every tips of your post are awesome. Thanks a lot for sharing. Keep blogging,

bitcoin update (2020/08/04 17:37)
I was looking at some of your posts on this website and I conceive this web site is really instructive! Keep putting up..

find here (2020/09/06 18:59)
I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post.

Catalogue bim (2020/09/06 21:26)
Hello There. I found your blog using google. This is a very well written article.
I’ll be sure to bookmark it and return to read more of your helpful information. Thanks for the post. I’ll
certainly comeback.

ที่เที่ยวพังงา (2020/10/21 19:08)
Very nice article, I enjoyed reading your post, very nice share, I want to twit this to my followers. Thanks!.

tiling Leeds (2020/11/29 03:46)
I felt very happy while reading this site. This was really very informative site for me. I really liked it. This was really a cordial post. Thanks a lot!.

photo booths for sale (2020/12/02 18:44)
Thank you so much for the post you do. I like your post and all you share with us is up to date and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job.

printing derby (2020/12/04 02:43)
Nice blog and absolutely outstanding. You can do something much better but i still say this perfect.Keep trying for the best.

mechanic Reading (2020/12/09 21:03)
This content is written very well. Your use of formatting when making your points makes your observations very clear and easy to understand. Thank you.

Wakefield pest control (2020/12/10 19:46)
I am very enjoyed for this blog. Its an informative topic. It help me very much to solve some problems. Its opportunity are so fantastic and working style so speedy.

maison intelligente (2020/12/22 02:13)
Interesting post. I Have Been wondering about this issue, so thanks for posting. Pretty cool post.It 's really very nice and Useful post.Thanks

Name   Password   Home   Secret   Submit
 Prev   1  ...  173   174   175   176   177   178   179   180   181  ...  604   Next 
codewiz’s Blog is powered by Tattertools.com / Designed by faido