성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Java - How to use the Foreign Funct...
[정성태] 제가 큰 실수를 했군요. ^^; Delegate를 통한 Bein...
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>방탈출3 - Room 10의 '중복가능한 조합' 문제를 위한 C# 프로그래밍 </h1> <p> 요즘, 심심할 때마다 한 번씩 iPad/iPhone의 '방탈출3'라는 게임에 시간을 보내고 있습니다. (짬짬이 하던 것이 오늘 기준으로 Room 10까지 왔군요. ^^)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 아이폰 앱리뷰 - 방탈출3무료 ; <a target='tab' href='http://www.appstory.co.kr/iphone_apps_review2001'>http://www.appstory.co.kr/iphone_apps_review2001</a> </pre> <br /> 마침 Room 10을 통과했는데요. ^^ "Room 10"에 들어서면 4개의 감옥문을 열어야 하는 곳에서 암산을 유도하는 데 '3번째 문'까지는 그런대로 풀어가다가 4번째 문부터는 슬슬 지리한 숫자 싸움이 되어서... 직업병이 도지기 시작하더군요. ^^;<br /> <br /> 문제를 대강 설명해 보면 대략 이렇습니다.<br /> <br /> 예를 들어, 화면에는 270이라는 숫자가 나오고 선택 가능한 숫자들로 다음과 같이 8개의 숫자가 제시됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 26, 52, 37, 17, 75, 89, 23, 94 </pre> <br /> 플레이어는 이 중에서 (중복가능한) 5개의 숫자를 골라서 270이라는 숫자가 합산되어야 합니다.<br /> <br /> 사실, 게임 내의 '저장하기/불러오기' 기능 및 문제가 어느 정도 반복되어 나타난다는 점을 이용하면 정해진 시간안에 충분히 해당 스테이지를 통과하는 것이 가능한데,,, 제가 ^^ 프로그래머이다 보니 키보드로 손이 가는 것을 어찌할 수 없더군요. ^^ (<a target='tab' href='http://www.sysnet.pe.kr/0/0/365'>프로그래머라면!</a>)<br /> <br /> <hr style='width: 50%' /><br /> <br /> 이 문제를 프로그램으로 옮기기 위해선, 적어도 '순열'과 '조합'에 대한 기본적인 이해를 하고 있는 것이 좋습니다. 이에 대해서는 아래의 설명을 참고하시는 것이 좋겠습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 순열(順列, permutation)과 조합(組合, combination) ; <a target='tab' href='http://ghebook.blogspot.com/2010/10/permutation-combination.html'>http://ghebook.blogspot.com/2010/10/permutation-combination.html</a> </pre> <br /> 자, 그럼 방탈출3에서 나온 감옥문 번호 문제는 순열일까요? 조합일까요?<br /> <br /> 그렇습니다. ^^ 조합입니다. 게다가, 선택해야 하는 숫자가 5개로 정해져 있기 때문에 경우의 수가 많이 줄어듭니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > n == 8 r == 5 n! / (n - r)!r! = 8! / 3!5! = 40320 / 720 = 56 </pre> <br /> 56가지 정도면... 만만하지요. 그런데, 불행히도 '방탈출3'에서 제시되는 숫자는 중복으로 고르는 것이 가능합니다. 즉 '중복 가능한 조합'이기 때문에 경우의 수가 늘어납니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > n == 8 r == 5 nHr = n+r-1 C r = (8 + 5 - 1)C(5) = 12 C 5 = 12! / (12 - 5)!5! = 479001600 / 604800 = 792 </pre> <br /> 오~~~ 문제 하나에 조합 가능한 숫자의 수가 792가지나 되니 머리에 쥐가 날 것 같은데요. 하지만, 실제로 인간이 위의 문제를 풀게 되면 '인식 능력'이 다르기 때문에 792가지나 테스트해 볼 필요까지는 없습니다.<br /> <br /> 예를 들어, 사람이라면... 26과 52라는 2개의 임의의 숫자로 시작해서, 그 2개를 더하면 78이 되고, 260에서 빼면 182가 됩니다. 이제 남은 8개의 숫자 중에서 '1의 자리' 수만 더해서 10을 넘는가에 상관없이 '2'가 되는 180 근처의 숫자 조합을 찾으면 되는 것입니다.<br /> <br /> 게다가, 5개의 숫자로 270을 만들어야 하니 평균 50 ~ 60 정도의 균형을 맞추는 숫자들이 선택되어야 하므로 17이라는 값이 3번만 중복되어도 가장 큰 숫자인 94를 남은 2번의 기회에 채워넣어도 270이 절대 넘지 못하기 때문에 이로 인해 잘려나가는 수학적 조합의 수도 존재합니다.<br /> <br /> 어쨌든... ^^ 프로그램에서는 이런 고려까지 하는 것이 더 귀찮을 수 있기 때문에 말 그대로 처음부터 끝까지 순서대로 '조합'을 해내는 코드를 만드는 것이 편합니다. (사실 웬만한 경우의 수라면, GHz 속도의 컴퓨터에게는 의미가 없지요.)<br /> <br /> <hr style='width: 50%' /><br /> <br /> '조합'을 해주는 코드를 직접 만드는 것도 좋고, 아래의 글에서 소개한 Combination 클래스를 사용하는 것도 좋겠습니다. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Using Combinations to Improve Your Software Test Case Generation ; <a target='tab' href='https://docs.microsoft.com/en-us/archive/msdn-magazine/2004/july/using-combinations-to-improve-your-software-test-case-generation'>https://docs.microsoft.com/en-us/archive/msdn-magazine/2004/july/using-combinations-to-improve-your-software-test-case-generation</a> </pre> <br /> 아쉽게도 '방탈출3'의 문제는 숫자 배열인 반면, 위의 클래스는 문자열 배열을 기준으로 하기 때문에 곧바로 가져다 쓸 수는 없습니다. Combination.cs 파일의 곳곳에 나오는 문자열 배열을 int []로 변경하고, 해당 게임의 문제를 코딩하면 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > static void Main(string[] args) { int[] elems = new int [] { 26, 52, 37, 17, 75, 89, 23, 94 }; Combination c = new Combination(elems.Length, 5); while (c != null) { int [] result = c.ApplyTo(elems); if (result.Sum() == 270) { Array.ForEach(result, n => Console.Write(n + ",")); Console.WriteLine(); Console.WriteLine("Found"); break; } c = c.Successor(); } } 출력 결과: 26, 52, 75, 23, 94 </pre> <br /> 그런데, 또 한가지 Combination.cs의 문제가 있습니다. 바로 '중복 가능한 조합'을 지원하지 않는다는 것인데요, 이 때문에 146 숫자가 나와야 하는 조합을 찾으면 없다고 나옵니다. (답이, 26, <span style='color: blue; font-weight: bold'>37, 23, 37, 23</span>이기 때문입니다.) <br /> 어쩔 수 없이, Combination.cs 파일의 코드를 '중복가능한 조합'을 산출하도록 변경해 주어야 합니다. 이를 위해서 아래와 같이 4군데의 코드를 손봐야 합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public Combination(long n, long k) { if (n < 0 || k < 0) // normally require n >= k throw new Exception("Negative parameter in constructor"); this.n = n; this.k = k; this.data = new long[k]; for (long i = 0; i < k; ++i) <span style='color: blue; font-weight: bold'>this.data[i] = 0; // 중복 가능하도록 0으로 모두 초기화 (기존 코드에서는 i로 초기화)</span> } public Combination Successor() { if (this.data.Length == 0) <span style='color: blue; font-weight: bold'>// OR 조건 이하 주석 처리 || this.data[0] == this.n - this.k)</span> return null; <span style='color: blue; font-weight: bold'> // 첫 번째 요소와 마지막 요소의 값이 (n - 1)일 때 까지 반복 (기존 코드에는 아래의 조건문이 없음) if (this.data[0] == this.n - 1 && this.data[this.k - 1] == this.n - 1) { return null; } </span> Combination ans = new Combination(this.n, this.k); long i; for (i = 0; i < this.k; ++i) ans.data[i] = this.data[i]; <span style='color: blue; font-weight: bold'> // ans.data[i] == this.n - this.k + i 비교를 다음과 같이 변경</span> for (i = this.k - 1; i > 0 && <span style='color: blue; font-weight: bold'>ans.data[i] == this.n - 1</span>; --i) ; ++ans.data[i]; for (long j = i; j < this.k - 1; ++j) { ans.data[j + 1] = ans.data[i]; <span style='color: blue; font-weight: bold'>// +1 처리하던 것을 제거</span> } return ans; } </pre> <br /> "n+r-1 C r"로 계산된 792가지 경우의 수가 맞는지 확인을 위해 다음과 같이 출력해 봅니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > static void Main(string[] args) { int[] elems = new int[] { 26, 52, 37, 17, 75, 89, 23, 94 }; Combination c = new Combination(elems.Length, 5); int i = 0; while (c != null) { Console.WriteLine(c.ToString()); c = c.Successor(); i++; } Console.WriteLine(i); } // i == 792 출력 </pre> <br /> 오호~~~ ^^ 정확히 792가 나오는 군요. 이제 다시 게임으로 돌아가서 문제가 제시되는 것마다 풀어주면 해당 스테이지를 간단하게 통과할 수 있습니다. 참고로, 아래는 제가 했을 때 제시된 4개의 문제와 답입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 270 ==> 26, 52, 75, 23, 94 146 ==> 26, 37, 23, 37, 23 362 ==> 52, 75, 89, 94, 52 315 ==> 26, 26, 75, 94, 94 </pre> <br /> 물론, 정답이 한가지만 있는 것은 아닙니다. 예를 들어, 315의 경우에 "26, 17, 89, 94, 89"의 조합으로도 나오기 때문입니다.<br /> <br /> <a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=621&boardid=331301885'>첨부된 파일은 위의 코드를 포함한 예제 프로젝트</a>입니다.<br /> <br /> (참고로, 이런 글 썼다고 홈지기가 수학을 잘하는 것 같다고 오해는 하지 마시기 바랍니다. ^^)<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
6937
(왼쪽의 숫자를 입력해야 합니다.)