하노이의 탑과 재귀 알고리즘

하노이의 탑

하노이의 탑은 세 개의 기둥과 여러 개의 크기가 다른 원반으로 구성된 퍼즐 게임입니다. 게임의 목표는 첫 번째 기둥에 있는 모든 원반을 세 번째 기둥으로 옮기는 것입니다. 단, 다음의 규칙을 따라야 합니다.

1. 한 번에 하나의 원반만 옮길 수 있습니다.
2. 큰 원반은 작은 원반 위에 놓일 수 없습니다.

재귀 알고리즘

하노이의 탑 문제를 해결하는 데에는 재귀 알고리즘이 효율적입니다. 재귀 알고리즘은 함수가 자기 자신을 다시 호출하는 방식으로 문제를 해결하는 알고리즘입니다. 하노이의 탑 문제에서는 작은 문제를 해결하는 방법을 반복적으로 사용하여 전체 문제를 해결합니다.

재귀 알고리즘의 깊이

재귀 알고리즘은 문제를 더 작은 부분 문제로 나누어 해결하는 방법입니다. 이러한 방식은 특히 하노이의 탑과 같이 동일한 패턴의 반복이 있는 문제에서 효율적입니다. 재귀 알고리즘을 이용해 간단하게 코딩할 수 있는 문제들이 있지만, 문제에 따라 너무 많은 재귀 호출을 일으키는 경우 "최대 재귀 깊이 초과"와 같은 오류를 발생시킬 수 있습니다.

재귀 알고리즘의 효율성

재귀 알고리즘은 코드를 간결하고 이해하기 쉽게 만들어주지만, 때로는 비효율적일 수 있습니다. 대표적인 예로 피보나치 수열을 들 수 있습니다. 피보나치 수열의 정의에 따라 재귀함수를 이용하면 간단하게 코딩할 수 있지만, 반복을 이용하는 것에 비해 재귀 알고리즘을 사용하면 계산의 양이 기하급수적으로 늘어나고 메모리 사용에 있어서도 비효율적입니다.

def fibonacci(n):
    if n <= 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)


print(fibonacci(35))  # 출력: 9227465

피보나치 수열의 n번째 항을 계산하는 재귀 알고리즘은 간단하고 직관적입니다. 그러나 이 방법은 n이 커질수록 매우 비효율적이게 됩니다. 이유는 중복 계산이 많기 때문입니다.

예를 들어, fibonacci(5)를 계산하기 위해 fibonacci(4)와 fibonacci(3)을 호출합니다. 그런데 fibonacci(4)를 계산하기 위해서는 다시 fibonacci(3)과 fibonacci(2)를 호출해야 합니다. 여기서 fibonacci(3)의 계산이 중복되는 것을 볼 수 있습니다. 이러한 중복 계산은 n이 커질수록 기하급수적으로 증가합니다.

하노이의 탑 - 파이썬 코드 예제

아래의 코드는 하노이의 탑 문제를 해결하는 파이썬 예제입니다. 예제는 '제로베이스 데이터스쿨' 강의 일부를 참고하였습니다. 주어진 obj1 리스트의 원반들을 obj2 리스트로 옮기는 과정을 재귀적으로 구현하였습니다.

obj1 = [1, 2, 3, 4]  # 원반이 담겨 있는 기둥
obj2 = [] # 옮길 기둥
obj3 = []  # 임시 기둥으로 사용

def hanoi(disc_count, from_bar, to_bar, aux_bar):
    if disc_count == 1:        
        to_bar.insert(0, from_bar.pop(0))
    else:
        hanoi(disc_count-1, from_bar, aux_bar, to_bar)
        hanoi(1, from_bar, to_bar, aux_bar)
        hanoi(disc_count-1, aux_bar, to_bar, from_bar)

hanoi(len(obj1), obj1, obj2, obj3)
print("Final state of obj2:", obj2)

작동 원리

1. disc_count가 1이면, from_bar의 맨 위 원반을 to_bar로 옮깁니다.
2. disc_count가 1보다 크면, disc_count-1개의 원반을 from_bar에서 임시 기둥 temp로 옮긴 후, 남은 원반을 to_bar로 옮깁니다. 그리고 aux_bar에 있는 원반을 to_bar로 옮깁니다.
3. 이 과정을 재귀적으로 반복합니다.