컴퓨터과학: 하노이탑

3개의 기둥(타워)가 있는 전설속 장소가 있다.

제일 왼쪽 타워에 금으로 된 고리 64개가 놓여져 있다.

제일 큰 고리가 제일 아래 있고, 순서대로 크기가 작아져 제일 작은 고리가 제일 위에 있는 형태다.

사람들은 다른 타워에 고리가 모두 옮겨지면 세상이 끝날 것으로 믿었다.

고리를 옮길 때 사용되는 규칙은 다음과 같다

1. 고리는 제일 위에서 부터 한번에 하나씩 옮겨집니다.

1. 위에 놓는 고리는 아래 고리보다 클 수 없습니다. (피라미드 모습으로 놓여져야 합니다)

비밀리에 어떤 사람이 1초에 하나씩 고리를 옮긴다면,

왼쪽 타워에서 오른쪽 타워까지 고리를 모두 옮기는데 시간이 얼마나 걸릴까요?

( ) 시간 / 일 / 년

이 문제를 풀 때 원래 문제처럼 64개 고리를 모두 이용할 수 있지만,

이 문제를 나눠서 보다 작은 문제로 만들어 해결할 수 있다.

이에 따라 고리의 수에 따른 최소 이동수를 결정하는 것이다. 아니면 머리로 생각할 수 있다.

컴퓨팅 사고력에서는 이 과정을 분해라고 말한다.

계속하려면 [다음]을 클릭하세요.