재귀 (Recursion) - 하노이 탑

하노이의 탑(탑의 하노이, Tower of Hanoi)은 세 개의 막대와 여러 개의 크기가 다른 원반을 사용하여 퍼즐을 푸는 문제. 퍼즐은 원반들이 한 막대에 크기 순으로 쌓여있는 상태에서 시작하며, 목표는 다음 규칙을 지키면서 다른 막대로 모든 원반을 옮기는 것:

1. 한 번에 하나의 원반만 옮길 수 있다.
2. 각 이동은 맨 위의 원반만 옮길 수 있다.
3. 더 큰 원반은 더 작은 원반 위에 놓을 수 없다.

하노이의 탑 알고리즘

1. n개의 원반이 있을 때:
   • n-1개의 원반을 출발 막대에서 보조 막대로 옮긴다.
   • 가장 큰 원반을 출발 막대에서 목표 막대로 옮긴다.
   • n-1개의 원반을 보조 막대에서 목표 막대로 옮긴다.

이를 자바스크립트로 구현한 예시:

function hanoi(n, from, to, aux) {
    if (n === 1) {
        console.log(`1번 원반을 ${from}에서 ${to}로 이동`);
        return;
    }
    hanoi(n - 1, from, aux, to);
    console.log(`${n}번 원반을 ${from}에서 ${to}로 이동`);
    hanoi(n - 1, aux, to, from);
}

// 하노이의 탑 실행 예시
const numberOfDisks = 3; // 원반의 개수
hanoi(numberOfDisks, 'A', 'C', 'B');

 

• 하향식 계산법으로 접근한다고 하면 n개의 원반이 있을때 나머지 부분은 n-1.