brunch

라이킷 2 댓글 공유 작가의 글을 SNS에 공유해보세요

You can make anything
by writing

C.S.Lewis

하노이탑 알고리즘

30층짜리 하노이탑을 옮기려면 무려 34년간을 쉬지도 않고 옮겨야 한다.

by Younggi Seo Jul 03. 2018


브런치 글 이미지 1

하노이탑을 옮기려면 원반을 모두 (2의 n승)-1번만큼 옮겨야 한다. 원반이 3개라면 총 7번을 옮겨야 한다. 마찬가지로 n이 커지면 -1은 큰 의미가 없으므로 하노이탑 알고리즘의 계산 복잡도는 O(2n)으로 표현할 수 있다. 이는 2를 n번 제곱한 값이므로 n이 커짐에 따라 값이 기하급수적으로 증가한다. 그래서 원반 하나를 옮기는 데 1초가 걸린다고 가정하더라도 30층짜리 하노이 탑을 옮기려면 무려 34년간 먹지도 쉬지도 않고 원반만 옮겨야 한다(이승찬, 2017).



브런치 글 이미지 2


재귀 호출을 이용한 하노이탑 알고리즘 함수의 작성은 간단하나, 직접 순서를 짜는 것은 일련의 과정을 머릿속에서 그릴 수 없다면 시도조차 하기 어려울 것이다. 그래서 머릿속에서 먼저 처음 그림의 과정을 하나씩 그려보고 수식으로 표현할 줄 아는 단계를 거쳐야 원반 세 개를 옮기는 것의 일반적인 경우(원반이 n개일 때)도 생각할 수 있다.



알고리즘을 적어보면 아래와 같다.

1. 원반이 한 개면 그냥 옮기면 끝이다(종료 조건).
2. 원반이 n개일 때
  1) 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮긴다(3번 기둥을 보조 기둥으로 사용).
  2) 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다.
  3) 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮긴다(1번 기둥을 보조 기둥으로 사용).


원반이 한 개일 때가 '종료 조건'에 해당한다. 원반 n개 문제를 풀려면 n-1개 원반 문제를 풀어야 하는데, 이는 바로 '좀 더 작은 값으로 자기 자신을 호출하는 과정'이다. 따라서 이 문제는 전형적인 재귀 호출 알고리즘에 해당한다(이승찬, 2017).


같은 과정의 반복이 이루어지는 하노이탑 옮기기의 재귀(Recusion)같은 과정의 반복이 이루어지는 하노이탑 옮기기의 재귀(Recusion)



참조

1) 이승찬 저. (2017). 모두의 알고리즘 with 파이썬, 서울:(주)도서출판 길벗.

2) Towers Of Hanoi. (2018, May 28). Retrieved from https://algorithms.tutorialhorizon.com/towers-of-hanoi/

매거진의 이전글 유클리드 공식을 통한 G.C.D. 구하기

브런치 로그인

브런치는 최신 브라우저에 최적화 되어있습니다. IE chrome safari