잠깐 추억얘기

초딩 5학년때 난데없는 정보올림피아드 전국대회 출전!에 엄청나게 고무되었던 우리 엄마아빠는 더 잘할 줄 알았던 6학년 전국대회에서 황당한 사건을 겪으시게 된다.

나는 화면 입출력밖에 모르는데 파일 입출력을 할 수 있어야 채점과정을 볼 수 있대요.

동네 학원에서 배운 GW-basic 만으로는 전국대회에서 싸울 능력을 키울 수 없다고 판단하신 부모님께서는 부랴부랴 지인을 총동원해서 알아낸 경시대회 학원으로 나를 끌고가셨는데, 거기 원장님이 처음 물어본 문제가 바로 이 하노이의 탑 문제였다.

문제 소개

룰은 간단하다. 기둥 세개가 있고, 원반이 기둥에 꽂혀있다.

1. 원반은 한번에 하나만 옮길 수 있다.
2. 큰 원반은 작은 원반 위에 못올린다.

모든 원반이 A 기둥에 있었다면 그것들을 모두 C 기둥으로 옮기는 게 목표이다.

자 이제 그럼 문제를 풀어보자

링크 - hash 부분을 변경해서 여러개의 문제집을 생성할 수 있다. 괜찮은 UI를 만들지 못했습니다…!

단계별 힌트

(힌트를 그냥 읽어주시는 것보다, 아이가 막혀있는 부분을 판단해서 상황에 맞는 힌트를 주는 것이 중요합니다)

1. 먼저 원반이 딱 하나만 있는 문제를 푼다고 생각해보세요.
2. 원반이 두개 있으면 어떻게 풀 수 있을까요?
3. 원반 두개 옮기는 비법을 세개 옮길 때 활용할 수 있을까요?
4. 문제에서 가장 큰 원반을 찾아보세요. 해당 원반을 옮겨야 하는지 알 수 있나요?
5. 원반을 옮기는 비법에 따라, 나머지 원반들을 어떻게 옮겨야 할지 생각해 봅시다.

친절한 해설

N개의 원반이 크기 순서대로 1,2,3,…,N 원반이라고 이름붙여보자.

N 원반을 옮길 때를 상상해보면, A 기둥에 가장 큰 원반 하나만 남아있고, C 기둥은 비어있어야 한다. 그럼 자연스럽게 B 기둥에 1..N-1 원반이 차곡차곡 쌓여있는 상태가 되어야만 한다는 것을 알 수 있다.

그렇게 N 원반을 C 기둥으로 옮기고 나면, 이제 다시 B 기둥에 쌓여있던 1..N-1 원반들을 이제 B에서 C로 옮겨야 한다.

문제 전체에서 1..N-1 원반을 옮길 때 N 원반은 어떤 영향도 주지 못한다 - 그 한번을 제외하곤 N 원반을 옮길 일도 없고, 다른 원반을 옮기는 데 방해하는 경우도 없다. 즉, 1..N-1 원반을 옮기는 문제를 풀 수 있으면, 자연스럽게 1..N 원반을 옮기는 문제 또한 풀 수 있게 되는 셈이다.

1. 1..N-1 원반을 A에서 B로 옮기는 문제를 푼다.
2. N 원반을 A에서 C로 옮긴다.
3. 1..N-1 원반을 B에서 C로 옮기는 문제를 푼다.

결론

막상 우리 애들은 아무리 알려줘도 못풀더라.

이 문제로 problem solving 맛을 좀 보여줘 보고 싶었는데, 개념설명은 이해한 것처럼 고개를 주억거리던 아이들이 막상 문제집을 가져다주자 오답 연속이었다. 뭐… 문제집 문제에 적용하려면 머릿속에서 다음과 같은 생각이 이뤄져야 한다.

• N 원반은 어디로 가야하나? 1..N-1 무더기는 어디로 가야하나?
• 1..N-1 무더기를 옮기는 문제에서, N-1 원반은 어디로 가야하나? 1..N-2 무더기는 어디로 가야하나?
• … 를 반복해서 결국 X 원반은 어디로 가야하나? 어? 갈 수 있네?

상황까지 recursion stack을 머릿속에서 시뮬레이션이 가능해야 한다. 어이쿠, 난이도가 너무 어려웠나…?