하노이의탑1

• 

  [알고리즘] Towers of Hanoi - 하노이의 탑 알고리즘 분할정복 알고리즘을 사용하여 하노이탑(Towers of Hanoi) 문제를 풀어보자. 하노이탑은 말뚝 3개와 크기가 모두 다른 구멍난 디스크 n개로 구성되어 있다. 문제는 한 말뚝에 쌓여있는 n개의 디스크를 모두 지정한 말뚝으로 옮기는 것이다. 규칙 문제를 풀 때 다음 규칙을 반드시 준수해야 한다. (1) 세 개의 말뚝 이외에는 디스크를 놓을 수 없다. (2) 한 번에 하나의 디스크만 옮길 수 있고, 말뚝의 맨 위에 있는 디스크만 옮길 수 있다. (3) 큰 디스크를 작은 디스크 위에 올려놓을 수 없다. 디스크의 수가 n개인 하노이 탑은 최소 $2^n - 1$단계로 풀 수 있다. 위 사진은 디스크의 수가 3개인 하노이 탑이 $2^3 - 1 = 7$단계를 거쳐 풀이됨을 보여준다. 알고리즘 일단, 세개의 기둥.. ETC/알고리즘 이론 2020. 10. 4.