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