하노이의 탑

 

   '하노이의 탑’은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 문제이다.

 

이 문제는 작은 원반 위에 큰 원반을 올릴 수 없다는 규칙을 가지고 있다. 알고리즘으로는 재귀함수의 좋은 예제가 되기도 한다. 하노이의 탑 문제를 풀기 위해 필요한 정보는 원반의 개수 n, 출발지 막대 start, 경유지 막대 via, 도착지 막대 to이다. 함수로 정의하면 다음과 같다.

 

hanoi(N, start, via, to) = hanoi(N - 1, start, to, via) + move(N, start, to) + hanoi(N - 1, via, start, to)

 

여기서 move(N, A, C)는 원반 N을 출발지 막대 A에서 도착지 막대 C로 옮기는 동작을 나타낸다. 원반의 개수가 클수록 이동 횟수가 기하급수적으로 늘어나기 때문에 재귀함수를 통해 효율적으로 문제를 풀 수 있다.

 

   [여기서 잠깐!] 재귀함수란?

 

재귀함수는 함수가 자기 자신을 호출하는 프로그래밍 기법이다. 예를 들어, 하노이의 탑 문제에서 사용한 재귀함수는 원반을 작은 부분 문제로 나누어 해결할 수 있다. 이렇게 하면 코드를 더 간결하게 작성할 수 있고, 문제를 효율적으로 해결할 수 있다.