Description

하노이 탑 문제는 재귀로 풀이할 수 있는 대표적인 문제이다.

하노이 탑 문제를 탑 다운 방식으로 쪼개보면,

1. A막대의 가장 밑에 있는 disk를 제외한 나머지 disk들이 B막대에 위치하고 (일련의 과정들에 의해)

2. A막대의 가장 밑에 있는 disk가 C막대로 이동하고

3. B막대의 n-1개의 disk들을 C로 이동시키는 일련의 과정들을 수행한다.

이 세가지를 그대로 점화식으로 표현할 수 있다이때, Base Condition은 n==1일 때로, disk를 from 에서 to로 옮겨주는 task를 수행한다.

Solution

Complexity

Time Complexity

>$O(2^N)$

Space Complexity

$O(N)$

지적 및 질문 환영