https://mediawiki.zeropage.org/index.php?action=history&feed=atom&title=HanoiProblemHanoiProblem - Revision history2026-05-14T09:39:43ZRevision history for this page on the wikiMediaWiki 1.39.8https://mediawiki.zeropage.org/index.php?title=HanoiProblem&diff=32054&oldid=previmported>Unknown at 05:23, 7 February 20212021-02-07T05:23:21Z<p></p>
<p><b>New page</b></p><div>= 하노이 문제 =<br />
* 하노이탑 문제 모두들 아시죠?<br />
* 링 3개가 있으면 1번 링에서 3번 링까지 링들을 이동 시키는 것이죠.<br />
* 그때 링 크기는 각자 다르고, 처음에 링은 제일 밑에 제일 큰 링, 그 위에 다음으로 큰링, 이런식으로 있고, 앞으로도 계속 그런식으로 밖에 쌓일수 밖에 없습니다.<br />
<br />
= 필요한 지식 =<br />
* C++ 기초 지식<br />
* Recursive Function <br />
<br />
=== 문제 소스들 ===<br />
* 아래와 같은 예제 식으로 소스를 만든 페이지에 넣어 주세요.<br />
{| class="wikitable"<br />
|-<br />
| 도전자<br />
| 총개발시간<br />
| 소스라인수('''주석제외''')<br />
| 사용언어<br />
| Source<br />
|-<br />
| 남상협<br />
| x시간x분<br />
| 30라인<br />
| C++<br />
| [[HanoiProblem/상협]]<br />
|-<br />
| 장은지<br />
| .<br />
| .<br />
| C++<br />
| [[HanoiProblem/은지]]<br />
|-<br />
| 신재동<br />
| .<br />
| 20라인<br />
| C++<br />
| [[HanoiProblem/재동]]<br />
|-<br />
| 임영동<br />
| 이틀 걸림<br />
| 100라인 초과<br />
| 어셈블리 언어<br />
| [[HanoiProblem/영동]]<br />
|-<br />
| 임인택<br />
| 1시간<br />
| 100라인<br />
| Java<br />
| [[HanoiProblem/임인택]]<br />
|}<br />
<br />
----<br />
학생들이 HanoiProblem을 푸는 것이 어려웠다면 이게 쉬운 문제라고(혹은 그다지 어려운 문제는 아니라고) 학생들이 느낄 수 있도록 하기 위해 무엇을 할 수 있을까 생각해 보는 것이 필요합니다.<br />
<br />
저는 학생들이 HanoiProblem에 도전하기 이전에 다음 세가지를 이야기 해주고 싶습니다.<br />
* 재귀함수에 대한 이해<br />
* 단순화<br />
* 미로거슬러내려오기<br />
<br />
'''재귀함수에 대한 이해'''<br />
<br />
재귀함수가 사용되는 대표적인 예 몇가지를 보여줍니다. 재귀함수 사용에도 그 종류가 다른데, 대표적인 종류들을 보여주는 것이 중요합니다. "아, 재귀함수라는 것이 이렇게도 사용될 수 있구나!" 퍼뮤테이션/콤비네이션, 피보나치수열, 트리검색, 팩토리알, 조건문과 재귀호출로 반복문(while) 만들기 등이면 충분하지 않을까 합니다.<br />
<br />
만약 HanoiProblem을 풀게 하기 이전에 팩토리알과 비슷한 형의 문제만 보여줬다면, 오히려 HanoiProblem을 어렵게 느끼고 학습이 많이 발생하지 못한 것이 더 당연하다고 생각됩니다.<br />
<br />
그리고 재귀함수를 만들 때 유의점과 사고보조물을 가르쳐 줍니다. 유의점이라면 재귀함수는 리턴되는 값의 종류(타입)가 모두 동일해야 한다는 것, 재귀호출을 벗어나는 지점 근방에서 유의해야 한다는 점 등이고, 사고보조물로는 스택의 상태를 그림으로 그리는 방법이나, 수식을 사용하는 방법 등이 있겠죠.<br />
<br />
'''단순화'''<br />
<br />
호주의 심리학자 존 스웰러(John Sweller) 교수는 순서효과(sequence effect)라 부르는 것을 증명했습니다.<br />
<br />
순서효과는 복잡한 것과 쉬운 것이 있을 때 어느 것을 먼저 제시받느냐에 따라 문제를 푸는데 걸리는 시간에 큰 차이가 있다는 것입니다.<br />
<br />
시작하는 수를 하나 주고, 특정한 연산을 사용하여 정해진 스텝만에 다른 수로 전환시키는 문제를 주었습니다. 예를 들어, 8에서 시작해서 곱하기 2나, 빼기 7을 사용해서 6번의 스텝만에 15를 만드는 문제입니다.<br />
<br />
한 그룹은 예를 들은 복잡한 문제를 먼저 제시받았고, 다른 그룹은 단순한 문제(예컨대 2번만에 8을 9로 바꾸는 것) 두개를 먼저 제시받았습니다.<br />
<br />
첫번째 그룹은 한 문제를 푸는데 평균 406초 이상 걸렸지만, 두번째 그룹은 복잡한 문제를 푸는데 97초 걸렸고, 세 문제를 모두 푸는데 192초 밖에 걸리지 않았습니다.<br />
<br />
이를 HanoiProblem에 적용하면, 3개(혹은 5개, 6개)의 원반 문제가 복잡하다면, 하나, 둘 등의 좀 더 단순한 문제를 먼저 풀고 거기서 문제풀이의 "구조적 유사성"을 발견해 낸 뒤에 좀 더 어렵거나 좀 더 일반적인 (즉 원반 n개) 문제에 도전하는 것이 효과적이라는 말이 됩니다.<br />
<br />
반대로 문제가 너무 단순해서 복잡할 경우에는 오히려 100개, 200개 등의 복잡/일반적인 경우를 생각하는 것이 도움이 될 수도 있습니다.<br />
<br />
'''미로거슬러내려오기'''<br />
<br />
종종 미로가 너무 복잡할 때 목적지에서 거꾸로 내려오는 것이 더 간단할 때가 있습니다. TestDrivenDevelopment도 이 방법을 사용합니다. 자신이 원하는 것을 컴퓨터에게 설명해 주고, 그 목적지에서 거슬러 내려옵니다.<br />
<br />
HanoiProblem이 복잡하게 느껴진다면, 우선 목적지에 도달한 상태, 즉, 모든 원반이 다른 막대기로 옮겨가 있는 상태를 상정합니다. 다음에는 여기에서 바로 직전의 상태로 거슬러 내려옵니다.<br />
<br />
혹은, 중간을 끊어서 볼 수도 있습니다. 어찌되었건 모든 원반이 옮겨가려면 어느 순간엔가는 가장 큰 원반이 비어있는 막대기로 이동해 가야 합니다. 이 상황에서 가장 큰 원반이 있는 막대기에는 큰 원반 하나만 있을 것이고, 그 원반이 옮겨갈 막대기는 비어있어야 하므로, 결국 두개의 막대기가 모두 사용되고, 나머지 하나의 막대기에는 나머지 원반들이 모두 크기 순으로 쌓여있게 될 것이라는 추측을 할 수 있습니다. 여기서 앞 뒤 상황을 생각해 보면 어떤 통찰을 얻을 수 있습니다.<br />
<br />
--JuNe<br />
<br />
----<br />
see Also [[데블스캠프2002]],[[데블스캠프2002/진행상황]]<br />
----<br />
[[문제분류]]<br />
</div>imported>Unknown