JavaScript로 이해하는 하노이의 탑 (Tower of Hanoi)

하노이의 탑이란

하노이의 탑(Tower of Hanoi)은 대표적인 재귀 알고리즘 문제로 널리 알려져 있습니다. 이 문제는 세 개의 기둥과 여러 개의 크기 다른 원판으로 구성되며, 모든 원판은 크기가 큰 것이 아래에, 작은 것이 위에 쌓여 있는 형태로 첫 번째 기둥에 위치해 있습니다. 목표는 특정 규칙을 지키며 모든 원판을 세 번째 기둥으로 옮기는 것입니다.

이때 적용되는 규칙은 다음과 같습니다:

• 한 번에 하나의 원판만 옮길 수 있습니다.
• 더 작은 원판만 큰 원판 위에 놓을 수 있습니다.
• 중간 기둥을 보조 기둥으로 활용할 수 있습니다.

이 문제는 단순한 퍼즐처럼 보이지만, 재귀 함수의 구조, 함수 호출 흐름, 분할 정복 사고방식을 익히는 데 매우 효과적입니다. 특히 자바스크립트로 알고리즘을 연습하는 초급 개발자에게 재귀 호출의 동작 방식을 눈에 보이듯 이해하는 데 도움을 줍니다.

---

하노이의 탑 재귀 구현 (JavaScript)

다음은 자바스크립트로 하노이의 탑을 재귀 함수로 구현한 예제입니다.

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

hanoi(3, 'A', 'C', 'B');

이 함수는 n개의 원판을 from 기둥에서 to 기둥으로 옮기기 위해 via 기둥을 보조로 사용하는 구조입니다. 원판의 개수가 1개일 때는 직접 이동하고, 그 외에는 전체를 세 단계로 나누어 재귀적으로 처리합니다.

---

함수 호출 흐름 설명

이제 위 함수가 호출되는 과정을 단계적으로 살펴보겠습니다. 예를 들어 hanoi(3, 'A', 'C', 'B')를 실행하면 다음과 같은 흐름으로 함수가 호출됩니다:

1. hanoi(3, A, C, B) → 3개의 원판을 A에서 C로 이동
   • 2개의 원판을 A에서 B로 이동: hanoi(2, A, B, C)
     • 1개를 A에서 C로 이동: hanoi(1, A, C, B) → 출력
     • 원판 2를 A에서 B로 이동 → 출력
     • 1개를 C에서 B로 이동: hanoi(1, C, B, A) → 출력
   • 원판 3을 A에서 C로 이동 → 출력
   • 2개의 원판을 B에서 C로 이동: hanoi(2, B, C, A)
     • 1개를 B에서 A로 이동: hanoi(1, B, A, C) → 출력
     • 원판 2를 B에서 C로 이동 → 출력
     • 1개를 A에서 C로 이동: hanoi(1, A, C, B) → 출력

이처럼 각 단계는 이전 원판들을 옮긴 후 가장 큰 원판을 목표 위치로 옮기고, 다시 남은 원판들을 재귀적으로 이동시키는 방식으로 구성되어 있습니다.

---

출력 예시

다음은 위 함수의 실행 결과입니다.

원판 1을 A에서 C로 이동
원판 2를 A에서 B로 이동
원판 1을 C에서 B로 이동
원판 3을 A에서 C로 이동
원판 1을 B에서 A로 이동
원판 2를 B에서 C로 이동
원판 1을 A에서 C로 이동

총 7번의 이동이 출력됩니다. 이는 일반적으로 하노이의 탑 문제에서 발생하는 최소 이동 횟수 2^n - 1의 공식과 일치합니다. 여기서 n은 원판의 개수를 의미하며, 위 예제에서는 n = 3이므로 2^3 - 1 = 7번의 이동이 수행된 것입니다.

---

하노이의 탑과 재귀 학습의 연관성

하노이의 탑은 단순한 문제처럼 보이지만, 실제로는 매우 강력한 재귀 학습 도구입니다. 이 문제를 통해 다음과 같은 개념들을 익힐 수 있습니다:

• 함수가 자기 자신을 어떻게 호출하고 되돌아오는지에 대한 구조적 이해
• 재귀 깊이에 따라 프로그램의 흐름이 어떻게 전개되는지 분석하는 능력
• 문제를 작게 나누고 해결해 나가는 분할 정복(divide and conquer) 방식

또한, 이 문제는 시각화하기 쉬워 화이트보드 코딩 또는 면접 상황에서도 설명력이 높은 편입니다. 호출 순서와 상태 추적이 분명하기 때문에, 자신만의 언어로 알고리즘을 설명하는 연습에도 좋습니다.

---

마무리 및 학습 자료 추천

하노이의 탑은 자바스크립트로 재귀 알고리즘을 연습하는 데 적합한 예제입니다. 재귀 호출의 흐름을 이해하고, 출력 결과를 분석하는 과정에서 알고리즘적 사고력을 키울 수 있습니다.

재귀뿐만 아니라 다양한 알고리즘 문제를 더 연습하고 싶은 분들에게 다음 자료를 추천드립니다:

• 프로그래머스 알고리즘 입문 강의: https://school.programmers.co.kr/
• LeetCode JavaScript 재귀 문제 목록: https://leetcode.com/
• replit 온라인 코드 실습: https://replit.com/

위 자료들을 활용해 알고리즘에 대한 실전 감각을 꾸준히 다듬는 것이 중요합니다. 기본기부터 탄탄히 다져 나가는 과정에서 하노이의 탑 문제는 매우 훌륭한 출발점이 될 수 있습니다.