[알고리즘 연습] 하노이의 탑

하노이의 탑

def hanoi(height) :
​​​​result = []
​​​​def move(begin, end, height):
​​​​​​​​if (height == 1):
​​​​​​​​​​​​result.append((begin, end))
​​​​​​​​else:
​​​​​​​​​​​​mid = (6 - begin - end)
​​​​​​​​​​​​move(begin,mid,height-1)
​​​​​​​​​​​​result.append((begin,end))
​​​​​​​​​​​​move(mid,end,height-1)        
​​​​move(1,3,height)
​​​​return result

def main():
​​​​print(hanoi(3))

• 유명한 하노이의 탑 문제이다.
• 처음 프로그래밍을 접했을 때, 이 문제로 하루종일 끙끙댔엇는데 이번엔 3분정도 고민 후 해결했다. (새삼 뿌듯했다.)
• 최대한 단순하게 접근하는 것이 포인트였다.
• 10개의 링을 마지막으로 옮겨야한다고 하자. 그럼 9개의 링을 두번째로 옮기고 마지막링을 세번째로 옮긴다음, 두번째있던 링들을 세번째로 옮겨야한다.
• 이를 범용적으로 표기한 후 재귀적으로 생각하면 위와 같은 코드로 처리된다.