하노이의 탑

안녕하세요!

오늘은 “하노이의 탑"에 대해 Python 샘플 프로그램을 곁들여 설명해보고자 합니다.

하노이의 탑이란?

하노이의 탑은 3개의 기둥과 여러 개의 원판을 사용하는 퍼즐입니다. 원판은 크기가 다르며, 처음에는 하나의 기둥에 크기 순서대로 쌓여 있습니다. 규칙은 다음과 같습니다:

한 번에 옮길 수 있는 원판은 1개뿐입니다.
작은 원판 위에 큰 원판을 놓을 수 없습니다.

이 퍼즐은 재귀적 사고를 배우는 데 최적의 교재로 알려져 있습니다. 재귀란 어떤 문제를 같은 종류의 더 작은 문제로 분해하여 해결하는 방법입니다. 하노이의 탑에서는 n개의 원판을 이동하기 위해 n-1개의 원판을 이동하는 조작을 반복합니다.

Python으로 하노이의 탑을 풀어보자

아래는 Python으로 하노이의 탑을 풀기 위한 샘플 코드입니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

# 예: 3개의 원판을 A에서 C로 이동
hanoi(3, 'A', 'C', 'B')

이 코드에서는 hanoi 함수가 재귀적으로 호출되어 원판을 이동하는 순서가 출력됩니다. 예를 들어, 3개의 원판의 경우 다음과 같은 출력을 얻을 수 있습니다:

1
2
3
4
5
6
7
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

이렇게 재귀적인 접근 방식을 사용하면 복잡한 문제도 간단하게 해결할 수 있습니다.

64개의 원판을 옮기는 데 시간이 얼마나 걸릴까?

하노이의 탑의 이동 횟수는 최소한 2^n - 1번 필요합니다. 즉, 64개의 원판을 이동하려면 2^64 - 1번, 약 1.84×10^19번의 이동이 필요합니다. 만약 1초에 1번 이동할 수 있다고 하더라도 약 5849억 년이 걸립니다. 이것은 우주 나이(약 137억 년)의 약 42배입니다.

이렇게 원판의 수가 늘어나면 필요한 이동 횟수가 지수함수적으로 증가합니다. 따라서 실제로 64개의 원판을 이동하는 것은 현실적이지 않습니다.

정리

하노이의 탑은 재귀적 사고를 배우기에 가장 좋은 퍼즐입니다. Python을 사용하면 그 해법을 간단하게 구현할 수 있습니다. 하지만 원판의 수가 늘어나면 필요한 이동 횟수가 급격히 증가하므로 주의가 필요합니다.

재귀적 접근 방식을 이해하고 실제로 코드를 작성해 보는 것으로 프로그래밍 스킬을 향상시킬 수 있습니다. 꼭 하노이의 탑에 도전해 보세요.