하노이탑 문제는 이산수학이나 프로그래밍의 재귀 함수에서 자주 나오는 유형의 문제입니다.
오늘은 하노이탑의 원리에 대해 알아 보도록 하겠습니다.
하노이탑이 유래된 것은 인도 베나레스에 있는 한 사원에 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세개의 다이아몬드 바늘이 동판 위에 세워져 있습니다.
이 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다.
가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기 까지 쌓아 있습니다.
이것이 신성한 브라흐마의 탑입니다.
브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮기는데요.
해당 규칙은 다음과 같습니다.
1. 한번에 하나의 원판만 옮길수 있다.
2. 작은 원판 위에 큰 원판을 올릴 수 없다.
이 규칙에 따라 원판을 하나씩 옮기는데 이 일이 끝날 때 탑은 무너지고 세상은 종말을 맞게 된다는 전설이 있는 문제인데요.
아직까지 세상의 종말을 맞이 하지 않았다는 것은 현재도 하나씩 옮기고 있는 중인지도 모르겠네요.^^
원리를 살펴 보면 위와 같이 3개의 원판을 세번째에 옮기기 위해서는 맨 아래를 세번째로 옮겨야 합니다.
그러기 위해서는 다음과 같이 두개의 원반이 가운데에 가 있어야 합니다.
이렇게 이동 한 후에 1번의 가장 큰 원판을 3번에 이동 후에 2번에 있는 2개의 원판을 규칙에 맞게 3번에 옮겨 주면 되는데요.
이러한 문제는 전형적인 귀납적인 사고를 필요로 합니다.
귀납적인 증명을 하기 위해서는 단위가 가장 작은 원판의 갯수가 하나일때 한번의 이동으로 1번 바늘에서 3번 바늘로 움직일 수 있다는 것을 확인 할 수가 있습니다.
이때 F(1) = 1
그렇다면 원판의 갯수가 2개 인 경우에는 한개의 원판을 2번 바늘에 옮긴 후에 1번에 있는 원판을 3번에 옮긴 후 다시 2번에 있는 원판을 옮깁니다.
이때 F(2) = F(1) (1개를 2번으로 이동횟수) + 1 (1번의 원판을 3번으로 이동횟수) + F(1)(2번의 원판을 3번으로 이동 횟수) = 3 이 됩니다.
그 다음 3개 짜리를 생각해 봅니다.
3개 짜리는 2개를 2번 원판에 옮긴 횟수 F(2) + 1(1번의 가장 아래를 3번으로 옮긴 횟수) + F(2) (2번에 있는 원판 2개를 3번으로 이동하는 횟수) 가 됩니다.
이렇게 계산을 하면 다음과 같은 식을 유도할 수 있습니다.
F(n) = F(n-1) + 1 + F(n-1) = 2 * F(n-1) + 1 이 됩니다.
그렇다면 위의 식에 값을 대입해 보면 다음과 같이 식을 유도해 볼수가 있습니다.
F(1) = 1
F(2) = 2 * 1 + 1 = 2 + 1 = 3
F(3) = 2 * 3 + 1 = 4 + 2 + 1 = 7
F(4) = 2 * 7 + 1 = 8 + 4 + 2 + 1 = 15
...
어떤 규칙이 보이시나요?
어떤 수 n 에 대해서 2^n - 1 의 규칙을 찾게 됩니다.
따라서 신이 말한 64개의 원판을 옮기기 위해서는 2^64 - 1 의 시간이 걸릴 텐데요.
이 값은 무려 18,466,744,073,709,551,615 의 값이 되기 때문에 1번의 이동시간을 1초로 계산 하여도 약 5000 억년이 된다고 하니 아무리 빠른 승려라고 해도 1초에 하나씩 옮기기는 어렵지 않을까 생각 되네요.^^
이러한 문제를 C언어로 구현하면 다음과 같이 구현 할 수가 있는데요.
| void hanoi(int n,int from, int to, int temp) // n개의 원판을 from 에서 to로 보내는데 ,temp 를 거쳐서 보내자. { if(n==0) return; //보낼 원판이 없다면 빠져 나가자. hanoi(n-1,from,temp,to); //n-1개의 원판을 거쳐가는 temp에 보내자 이때는 to를 이용해서 보내면 재귀적이기 때문에 알아서 보내 준다.^^ printf("%d번째 원판 : %d번 바늘 -> %d번 바늘\n",n,from,to); //from 에 있는 가장 아래 원판을 to 에 보내는 것을 확인 하자. hanoi(n-1,temp,to,from); //temp 에 있는 n-1개의 원판을 from을 거쳐서 to 에 보내면 끝난다. } |
메인에서 호출은 다음과 같이 호출하면 되겠네요.
hanoi(3,1,3,2);// 3개의 원판을 1번에서 3번으로 보내는데 2번을 거쳐서 보내라...
64개를 보내는데 1초에 1억번을 계산 한다고 해도 엄청난 시간이 걸릴테니... 64개는 실험을 안 해 보셔도 될것 같아요.^^
하노이탑 - 프로그래밍 언어에서 재귀 함수를 배울때 자주 나오는 문제이기도 하고 이산수학에서 귀납적 사고 부분에서 자주 나오는 유형의 문제였는데요...
이런 유형의 문제를 해결 하다 보면 실생활에 있는 문제들에서 어떤 규칙을 끌어 내는 것에 많은 도움이 될것이라 생각 되네요.
오늘도 열심히 공부하고 있는 우리 학생들을 응원합니다.
인천 서구 알고리즘 학원 - 인천 원당 컴퓨터 학원
'강의실 > 정보영재' 카테고리의 다른 글
| [컴퓨팅 사고력]2의 보수 3의 보수는 무엇일까? (8) | 2019.09.23 |
|---|---|
| CodeBlock 환경설정 초기화 방법 (7) | 2019.09.18 |
| [컴퓨팅 사고력]하노이탑 문제(Hanoi Tower Problem) 이해하기 (5) | 2019.09.03 |
| 비둘기집 원리에 대해 알아 봅니다. (9) | 2019.08.12 |
| 프로그래밍은 문제해결능력이다. (9) | 2019.08.09 |
| 알고리즘 대회에서 입력 데이터를 만드는 경우의 수를 생각하기 (11) | 2019.07.19 |
