모두의 알고리즘 문제06. 하노이의 탑 옮기기

def hanoi(n, from_pos, to_pos, aux_pos): # from출발점, to도착점, aux중간과정에 사용할 보조기둥
    if n==1:
        print(from_pos, "->", to_pos)#원판 한개를 옮기는 문제면 그냥 옮기면 됨
        return

    hanoi(n-1, from_pos, aux_pos, to_pos) # 출발점에서 중간과정으로 원판n-1개 이동. 도착점 기둥을 이용해서
    print(from_pos, "->", to_pos) #가장 큰 원반을 목적지로 이동
    hanoi(n-1, aux_pos, to_pos, from_pos) # 중간 기둥에서 도착점 기둥으로 원판 n-1개 이동

print("n=1")
hanoi(1, 1, 3, 2) #원판 1개를 1번기둥에서 3번기둥으로 2번기둥을 보조기둥으로

print("n=2")
hanoi(2, 1, 3, 2)

print("n=3")
hanoi(3, 1, 3, 2)

print("n=5")
hanoi(5, 1, 3, 2)

재귀호출 문제로 유명한 하노이탑 문제다. 솔직히 이해 안된다.

 

이해 가능하도록 노력해야겠다.

 

머리아프다.

 

하노이의 탑 알고리즘의 시간복잡도를 알아보자.

 

1층짜리는 1번, 2층은 3번, 3층은 7번, 4층은 15번 이동한다. 즉 n층짜리 하노이탑을 옮기려면 원판은 2^n-1번 옮겨야한다.

 

저번에 배웠듯이 증가량을 수식으로 나타냈을 때 가장 영향이 큰 걸 빅 오 표기법에 반영하면 된다. 그러므로 시간복잡도는 O(2^n)으로 표현할 수 있다.

 

n값이 커짐에 따라 값이 기하급수적으로 증가하는데 교재에 따르면 20층짜리 하노이탑은 하나 옮기는데 1초가 걸린다 가정하면 열이틀이 걸려서 다 옮길 수 있다고 한다.