개요
하노이탑 문제는 재귀를 말할 때 항상 예시로 드는 알고리즘이라고 한다. 하지만 전공자가 아닌 나는 오늘 처음 들었다. 그리고 이해하는데 어려움을 겪었는데, 내 식대로 이해한 것을 같이 공유하고자 한다.
먼저 하노이탑이란 세 개의 기둥과, 그 기둥에 꽃을 수 있는 서로 다른 N개의 디스크를 가진 퍼즐이다.
이 퍼즐의 규칙은 밑과 같다.
- 디스크는 한번에 하나 씩 옮길 수 있다.
- 디스크는 자신보다 큰 디스크 위에만 쌓을 수 있다.(큰 원판이 작은 원판 위에 위치해선 안된다.)
이 때, 우리는 가장 왼쪽 기둥에 있는 모든 원판을 가장 오른쪽에 있는 기둥에 옮겨야 한다.
최소 몇 번으로 오른쪽으로 다 옮길 수 있을까?
가정(개인적인 의견)
나는 위의 규칙에서 편하게 생각하기 위해 하나의 규칙을 더 정했다.
3. 빈 기둥은 모든 디스크보다 큰 디스크가 쌓여 있는 것으로 가정한다.
이 규칙은 역도 성립한다고 가정한다.
4. 모든 디스크보다 큰 디스크는, 빈 기둥으로 가정한다.
디스크의 갯수가 N개 일 때, 위의 가정 대로 하노이 탑을 풀어보자!
N == 1
N이 1일 때, 빨간색 디스크는 가운데 기둥, 오른쪽 기둥으로 모두 옮길 수 있다.
하지만 최소로 이동해야 하기 때문에, 목표 기둥인 오른쪽 기둥으로 옮긴다.
N이 1일 때는 그저 왼쪽의 디스크를 오른쪽(목표 기둥)으로 옮기면 된다.(중요. 기억 해 놓자.)
그럼 디스크의 갯수가 1일 때, 최소 이동 횟수는 1이 된다.
코드로 표현하면 밑과 같다.
N == 2
N이 2일 때는 조금 다르게 생각해 보자.
먼저, 모든 디스크를 옮기기 위해서는 빨간 디스크를 가운데 기둥에 임시로 옮겨야 한다.
이 행위를 다르게 생각해 보자.
가운데 디스크를 목표 기둥(가장 오른쪽 기둥)이라고 생각한다면,
N==1일 때 옮기는 횟수랑 같고, N==1일 때 옮기는 방식과 같아진다.
("N이 1일 때는 그저 왼쪽의 디스크를 오른쪽(목표 기둥)으로 옮기면 된다.")
이것을 위의 추가한 규칙 (4.모든 디스크보다 큰 디스크는, 빈 기둥으로 가정한다.) 를 적용 시키면 N==1일 때와 더욱 비슷해 지는데,
주황색 디스크가 있는 기둥은 빨간색 디스크 입장에서 빈 기둥이 된다. 또한 목표 기둥을 가운데 기둥으로 설정했다. 따라서 빨간색 디스크의 입장으로 위의 그림을 다시 표현한다면 밑의 그림처럼 된다.
(위의 그림과 다를 바가 없음.)
위의 그림에서, 빨간색 입장으로 생각한다면,
위의 하노이 함수를 한번 실행했는데, N의 변수에 1이 들어간 경우인 것이다. 코드로 표현하면 밑과 같다.
이제 다시 원래대로 돌아와 보자. 빨간색을 목표 지점에 옮기고, 원래 목표 지점인 오른쪽 기둥으로 설정한다. 그럼 주황색 디스크는 목표 지점인 오른쪽으로 옮긴다.
이는 주황색 디스크를 그저 목표 기둥으로 옮겼으니, N==1일 때와 상황이 같다고 생각할 수 있겠지만, 가운데 기둥과 오른쪽 기둥으로 옮길 수 있는 빨간색 디스크와 달리, 주황색 디스크는 선택지가 하나 밖에 없다.(자신보다 작은 디스크 위에는 올릴 수 없기 때문.)
따라서 주황색 디스크를 옮긴 것은 함수 hanoi(1)로 표현할 수 없고, 그저 상수 1로 표현해야 한다.
이제 다시 빨간색 입장으로 돌아와 보자.
빨간색 입장에서는 규칙 (4.모든 디스크보다 큰 디스크는, 빈 기둥으로 가정한다.)덕분에 주황색 디스크가 있는 기둥을 빈 기둥으로 정의할 수 있다.
따라서 빨간색 입장에서의 상황은 다시 밑의 그림처럼 바뀐다.
이렇게 바뀌면, 빨간색 입장에서는 또 N==1인 상황이 된다. 따라서 N이 1일 때는 그저 왼쪽의 디스크를 오른쪽(목표 기둥)으로 옮기면 된다. 의 상황과 같아진다.
이는 N==1일 때와 똑같이 옮길 수 있는 선택지는 두 개(목표 기둥과 목표가 아닌 기둥.)이며, 최소로 움직여야 하기 때문에 목표 지점으로 그저 디스크를 옮기면 되기 때문이다.
위를 코드로 표기한다면, N==1과 같이, 함수를 실행시켰는데, 매개변수에 1이 들어간 경우와 같다.
위를 종합해 보면, N==2 일 때, 즉 디스크 두 개를 옮기는 방법을 코드로 옮기면 밑과 같이 된다.
그럼 이것을 N으로 표현하자면, 밑과 같이 된다.
그리고 맨 위에 N==1일 때를 가정한 함수를 다시 끌어 와 보자.
이 모든 것을 합쳐 본다면 밑과 같이 된다.
N이 3일 때도 마찬가지인데, N이 2일때의 과정에 그저 +1을 한 것과 같기 때문이다.
함수로 표현하면 밑과 같다.
댓글
댓글 쓰기