성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
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'>동전을 여러 더미로 나누는 경우의 수 세기</h1> <p> 생각을 정리해 두는 것이 좋을 것 같아서 써봅니다. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>*** 유의사항: "<a target='tab' href='http://euler.synap.co.kr/prob_detail.php?id=70'>프로젝트 오일러의 76, 78번 문제</a>"를 풀지 않은 분들의 경우 가능한 문제를 풀고 나서 읽기를 바랍니다.</span> </pre> <br /> 사실 76번과 78번 문제는 같은 유형의 문제입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Problem 76 (숫자 100을 두 개 이상의 자연수의 합으로 나타내는 방법은 모두 몇 가지 ; <a target='tab' href='http://euler.synap.co.kr/prob_detail.php?id=76'>http://euler.synap.co.kr/prob_detail.php?id=76</a> Problem 78 (동전을 여러 더미로 나누는 경우의 수 세기) ; <a target='tab' href='http://euler.synap.co.kr/prob_detail.php?id=78'>http://euler.synap.co.kr/prob_detail.php?id=78</a> </pre> <br /> 우선, 각 동전별로 나올 수 있는 경우의 수를 성능을 고려하지 않은 코드를 이용해서 출력을 해 보니 다음과 같은 결과를 얻을 수 있었습니다.<br /> <br /> <pre style='height: 400px; margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 3 ==> 2가지 2,1 1,1,1 4 ==> 4가지 2,1,1 1,1,1,1 3,1 2,2 5 ==> 6가지 2,1,1,1 1,1,1,1,1 3,1,1 2,2,1 4,1 3,2 6 ==> 10가지 2,1,1,1,1 1,1,1,1,1,1 3,1,1,1 2,2,1,1 4,1,1 3,2,1 5,1 4,2 2,2,2, 3,3, 7 ==> 14가지 2,1,1,1,1,1 1,1,1,1,1,1,1 3,1,1,1,1 2,2,1,1,1 4,1,1,1 3,2,1,1 5,1,1 4,2,1 2,2,2,1 3,3,1 1,6 2,5, 2,2,3, 3,4, </pre> <br /> 잘 보면, 일정한 규칙이 나오는데 딱 3가지로 정리해 볼 수 있습니다.<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>1. n의 숫자에서는 n - 1의 경우의 수를 모두 포함</div> <br /> 예를 들어, 3의 경우에 "2,1", "1,1,1"을 포함하는데, 4에서는 3이 가지고 있는 경우의 수에 "+1"만 하는 모든 경우의 수가 포함됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 4 ==> 4가지 <span style='color: blue; font-weight: bold'> 2,1,1 1,1,1,1</span> 3,1 2,2</pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>2. 2자리 수의 합이 n이 되는 경우의 수가 새롭게 추가됨.</div> <br /> 4의 경우에 새롭게 "3 + 1", "2 + 2"이 추가되는 것을 볼 수 있습니다. 중복되는 경우의 수가 나오면 안되기 때문에 다음과 같이 절반만 루프를 돌아주면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > for (int t = 1; t <= i / 2; t++) { 배열 { i - t, t } 추가 } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>3. 이전 수로부터 물려받은 3자리 이상의 배열에서 가장 마지막 2자리 수의 차가 1 이상인 경우 마지막 자리에 +1을 한 경우의 수를 추가</div> <br /> 말이 좀 긴데요. 예를 들어, 숫자 6에 대한 경우의 수가 5로부터 물려받은 수는 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 2,1,1,1 <== 마지막 2자리 수의 차가 0 1,1,1,1,1 <== 마지막 2자리 수의 차가 0 3,1,1 <== 마지막 2자리 수의 차가 0 <span style='color: blue; font-weight: bold'>2,2,1 <== 마지막 2자리 수의 차가 1 이상</span> 4,1 <== 2자리 수 3,2 <== 2자리 수 </pre> <br /> 따라서, 조건을 만족하는 배열이 "2,2,1"이므로, 이런 배열을 만나면 마지막 자리 수에 +1을 해서 추가를 해주면 됩니다. 위의 상황에서는 "2,2,2" 배열이 추가되는 것입니다.<br /> <br /> <hr style='width: 50%' /><br /> <br /> 그래서, 처음에는 이전 배열 목록을 만들어서 누적시켜 나가는 방향으로 코드를 만들어서 결과를 내려고 했는데요. 아쉽게도 답까지 가지 못했습니다. ^^; 문제는 메모리! 제 노트북 메모리가 8GB인데 금방 소진을 하고 엄청난 하드 디스크 스와핑 현상이 발생하면서 시간 지연이 너무 길어서 중도에 포기를 했습니다.<br /> <br /> 어쩔 수 없이 메모리 소비를 줄이는 아이디어를 내야 했는데... 다행히 2가지 정도의 방안이 떠 올랐습니다.<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>1. 이전 경우의 수에 대해서는 누적 숫자만 보관하고 메모리에서 제거</div> <br /> 예를 들어, 4의 경우의 수와 5의 경우의 수를 비교해 보면,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 4 ==> 4가지 <span style='color: blue; font-weight: bold'> 2,1,1 1,1,1,1 3,1 2,2</span> 5 ==> 6가지 <span style='color: blue; font-weight: bold'>2,1,1</span>,1 <span style='color: blue; font-weight: bold'>1,1,1,1</span>,1 <span style='color: blue; font-weight: bold'>3,1</span>,1 <span style='color: blue; font-weight: bold'>2,2</span>,1 4,1 3,2 </pre> <br /> 달라지는 것이라고는 그저 "1"만 추가되는 것일 뿐 사실상 메모리에 들고 있을 필요가 없습니다. 게다가 연이어서 5의 경우의 수가 6으로 넘어가도 모든 것들에 "+1"만 되는 것일 뿐이어서 굳이 보관할 필요가 없어서 제거 대상이 될 수 있습니다.<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>2. 모든 경우의 수를 보관할 필요 없이 최대 마지막 3자리 수만 보관하면 됨.</div> <br /> 숫자도 모든 수를 보관할 필요는 없습니다. 이전 수가 가진 배열에서 판단이 필요한 것은 "3번 조건"으로 "이전 수로부터 물려받은 3자리 이상의 배열에서 가장 마지막 2자리 수의 차가 1 이상인 경우 마지막 자리에 +1을 한 경우의 수를 추가"하기 위해서는 "3자리 이상의 배열" 값인 것만 알면 됩니다. 그래서, 이전 배열로부터 물려받은 것 중 마지막 2자리 숫자의 차가 1 이상인 배열만 물려받고 그중에서도 3자리 수만 보관하고 있으면 됩니다.<br /> <br /> <hr style='width: 50%' /><br /> <br /> 이렇게 해도 소비 메모리가 약 18GB에 달해서 하드 스와핑이 발생합니다. 하지만 ^^ 이번 경우에는 저도 더 이상의 방법이 없다고 생각하고 데스크톱에서 테스트를 하여 결과를 냈는데 시간도 16분이 걸렸습니다.<br /> <br /> 성능 좋은 데스크톱을 이용하여 넘어간 꼼수는 ^^; 아쉽게도 오래가지 못했습니다. 문제는 78번에서 걸린 것입니다. 겨우 숫자 100에 해당하는 76번의 답을 내는 수준에서도 메모리가 18GB를 넘는데 78번의 답에서는 영영 답이 안 나올지도 모른다는 생각이 들었습니다. ^^ 어쩔 수 없이 지난번 생각에 대해 개선이 필요했는데요.<br /> <br /> 다시 뚫어지게 경우의 수를 쳐다봤습니다. ^^<br /> <br /> 그랬더니... 오호~~~ 보이기 시작합니다. 이번엔 이전 배열의 수에 대해 보관을 하지 않고도 가능한 방법이 나타났습니다.<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>1. (n - 1)의 누적값은 숫자로만 보관</div> <br /> 이에 대해선 이미 이전에 설명했기 때문에 생략합니다. 어쨌든 배열을 보관하지 않아도 된다는 것이 중요합니다.<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>2. 두자리 숫자의 합에 대한 경우의 수도 계산 가능</div> <br /> 숫자리 숫자의 합은 "((n / 2) - 1)"이라는 간단한 공식으로 표현이 되어서 그 부분에 대한 루프도 생략이 가능했습니다.<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>3. n번째 배열의 경우의 수에 영향을 주는 이전 배열의 경우의 수에 대한 결과만 보관</div> <br /> 숫자 6의 경우를 보면 다음과 같이 구성된 것을 볼 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > [5의 경우의 수를 포함] 2,1,1,1,1 1,1,1,1,1,1 3,1,1,1 2,2,1,1 4,1,1 3,2,1 5,1 <= 2자리 숫자의 합 (1) <span style='color: blue; font-weight: bold'>4,2 <= 2자리 숫자의 합 (2)</span> <span style='color: blue; font-weight: bold'>2,2,2,</span> 3,3, <= 2자리 숫자의 합 (3) </pre> <br /> 여기서, "2,2,2"가 어디서 왔는지를 판단해야 하는데, 이것은 2자리 숫자의 합 중에서 "2 + 4"에 힌트가 있습니다. 4의 구성요소를 보면, 다음과 같은데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 2,1,1 1,1,1,1 3,1 <= 2자리 숫자의 합 (1) <span style='color: blue; font-weight: bold'>2,2 <= 2자리 숫자의 합 (2)</span> </pre> <br /> 보시는 것처럼, 6의 경우의 수에서 "2 + 4"의 조합에서 "4"에 대한 경우의 수를 이어받게 되어 있습니다. 그런데, 4에 대한 모든 경우의 수를 이어받는 것이 아니고, 6의 2자리 숫자의 합의 순서와 일치하는 4의 2자리 숫자의 합에 대한 경우의 수를 가져옵니다. (정확하게는 누적값을 가져오게 되는데, 이에 대해서는 좀 더 설명이 필요하지만 장황해지므로 생략합니다. 차근차근히 보면 누적 규칙을 어렵지 않게 발견할 수 있습니다. ^^)<br /> <br /> <hr style='width: 50%' /><br /> <br /> 결과는 아주 만족스럽습니다. 위와 같이 해주면 이전의 알고리즘으로 메모리 18GB에 16분이나 걸렸던 작업이 메모리 소비 거의 없이 10ms도 체 안되는 시간에 숫자 100에 대한 경우의 수를 계산해 냅니다.<br /> <br /> 그런데, 여전히 78번 문제에서는 위의 알고리즘도 문제가 되었습니다. 1백만으로 나눠 떨어지는 경우의 수를 찾아야 하는데, 숫자 100에 대한 경우의 수에서도 1억이 넘어가 버리는 바람에 숫자가 너무 커져 버려서 부득이 BigInteger를 써야만 정상적인 합이 나올 정도로 숫자가 커져갔습니다.<br /> <br /> 어느 정도냐면??? 숫자 14574에 대한 경우의 수가 "3023230991908581568928363906501639271939935875772000955326621702587696794760453659405017864587829790913886891883621070101089120000" 로 나왔으며 그 순간에 메모리는 1.5GB까지 소비되어 있었습니다. 그야말로 '헉'소리 나오는데요. ^^;<br /> <br /> 78번 문제를 풀기 위해서는 뭔가 개선이 필요하다는 생각이 다시 들었습니다. 음... 그러다 한 가지 묘책이 떠오르더군요. ^^ 어차피 1백만으로 나눠서 떨어지면 되기 때문에 모든 숫자를 보관할 필요 없이 백만 이상의 값은 잘라 버리고 보관을 하는 식으로 바꾸고 그래서 BigInteger 값이 아닌 보통의 int 값으로 자료구조를 바꿀 수 있었고, 이로 인해 메모리가 약 4.0GB 소비로 바뀌고 376초만에 결과를 냈습니다.<br /> <br /> 일단, 여기까지 해서 76번/78번에 대한 제 탐구는 끝이 났고 답을 낸 다음에 "<a target='tab' href='http://euler.synap.co.kr/'>Project Euler</a>"에서 다른 이들이 답을 쓴 것을 보았습니다. 오호~~~ 점화식을 이용해서 풀었는데요. 코드를 보니, 마법같은 점화식 변수가 하나 나옵니다. 수학에 대한 깊이가 없는 저로써는 도저히 알아낼 수가 없는 ^^ 식이더군요. 저 역시 나름대로 76번 문제를 풀면서 숫자가 점진적으로 증가하는 것에 대해 무언가 점화식을 추론할 수 있지 않을까 싶었는데, 생각만 했을 뿐 발견해낼 수가 없었습니다. 점화식 답을 보고 나서... 추론하는 데 시간을 보내지 않기를 잘했다는 생각이 들더군요. ^^;<br /> <br /> 어쨌든... 문제를 풀다보니 재미있는 것들을 많이 알게 됩니다. ^^ 게다가 역시, 수학을 알고 모르고의 차이가 분명히 있다는 것도 알게 되었고.<br /> <br /> 참고로, 76번의 경우 답을 제외하고 99번까지의 단계별 경우의 수는 다음과 같습니다. ^^ 문제 푸는 분들께 도움되길 바랍니다.<br /> <br /> <pre style='height: 400px; margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 3 ==> 2 4 ==> 4 5 ==> 6 6 ==> 10 7 ==> 14 8 ==> 21 9 ==> 29 10 ==> 41 11 ==> 55 12 ==> 76 13 ==> 100 14 ==> 134 15 ==> 175 16 ==> 230 17 ==> 296 18 ==> 384 19 ==> 489 20 ==> 626 21 ==> 791 22 ==> 1001 23 ==> 1254 24 ==> 1574 25 ==> 1957 26 ==> 2435 27 ==> 3009 28 ==> 3717 29 ==> 4564 30 ==> 5603 31 ==> 6841 32 ==> 8348 33 ==> 10142 34 ==> 12309 35 ==> 14882 36 ==> 17976 37 ==> 21636 38 ==> 26014 39 ==> 31184 40 ==> 37337 41 ==> 44582 42 ==> 53173 43 ==> 63260 44 ==> 75174 45 ==> 89133 46 ==> 105557 47 ==> 124753 48 ==> 147272 49 ==> 173524 50 ==> 204225 51 ==> 239942 52 ==> 281588 53 ==> 329930 54 ==> 386154 55 ==> 451275 56 ==> 526822 57 ==> 614153 58 ==> 715219 59 ==> 831819 60 ==> 966466 61 ==> 1121504 62 ==> 1300155 63 ==> 1505498 64 ==> 1741629 65 ==> 2012557 66 ==> 2323519 67 ==> 2679688 68 ==> 3087734 69 ==> 3554344 70 ==> 4087967 71 ==> 4697204 72 ==> 5392782 73 ==> 6185688 74 ==> 7089499 75 ==> 8118263 76 ==> 9289090 77 ==> 10619862 78 ==> 12132163 79 ==> 13848649 80 ==> 15796475 81 ==> 18004326 82 ==> 20506254 83 ==> 23338468 84 ==> 26543659 85 ==> 30167356 86 ==> 34262961 87 ==> 38887672 88 ==> 44108108 89 ==> 49995924 90 ==> 56634172 91 ==> 64112358 92 ==> 72533806 93 ==> 82010176 94 ==> 92669719 95 ==> 104651418 96 ==> 118114303 97 ==> 133230929 98 ==> 150198135 99 ==> 169229874 </pre> <br /> </p><br /> <br /> <br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
1164
(왼쪽의 숫자를 입력해야 합니다.)