[바미] 하노이 탑 이동 순서

문제

 

 

https://www.acmicpc.net/problem/11729

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input, 10);

let result = [];
let moveCount = 0;

function hanoi(n, from, to, aux) {
    if (n === 1) {
        result.push(`${from} ${to}`);
        moveCount++;
        return;
    }
    hanoi(n - 1, from, aux, to);
    result.push(`${from} ${to}`);
    moveCount++;
    hanoi(n - 1, aux, to, from);
}

hanoi(N, 1, 3, 2);

console.log(moveCount);
console.log(result.join('\n'));

 

재귀 함수는 아래와 같이 동작합니다.

1. hanoi(n, from, to, aux) 함수는 원판 𝑛개를 from 장대에서 to 장대로 aux 장대를 사용하여 옮겨짐.
   기본 경우 -  𝑛이 1일 때, 바로 이동하고 이동 횟수를 증가시킨다.
2. 재귀 호출 - 𝑛 − 1개의 원판을 from에서 aux로 이동.
3. 1개의 원판을 from에서 to로 이동.
4. 𝑛 − 1개의 원판을 aux에서 to로 이동.

문제 해설

하노이의 탑 문제는 재귀를 사용하여 해결할 수 있는 전형적인 문제입니다. 이 문제를 풀기 위해서는 기본적으로 다음과 같은 재귀적 접근을 필요로 하는데 원판이 𝑛개 있을 때, 첫 번째 장대에서 세 번째 장대로 이동시키는 과정은 다음과 같이 재귀적으로 정의할 수 있습니다.

1. 𝑛  - 1개의 원판을 첫 번째 장대에서 두 번째 장대로 옮긴다.
2. 𝑛번째 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다.
3. 두 번째 장대에 있는 𝑛 − 1개의 원판을 세 번째 장대로 옮긴다.

위 과정을 수식으로 표현하면 T(𝑛) = 2T(𝑛 − 1) + 1로 표현 할 수 있습니다.

• 𝑇 (𝑛) - 원판 𝑛개를 옮기는 데 필요한 총 이동 횟수
• 𝑇(𝑛−1) - 원판 𝑛 − 1개를 옮기는 데 필요한 이동 횟수

재귀 관계식 𝑇(𝑛) = 2 𝑇(𝑛−1)+1을 풀어보겠습니다.

𝑇(1)=1 (원판 1개를 옮기는 데 필요한 이동 횟수는 1)

𝑇(2) = 2𝑇 (1) + 1 = 2 ⋅ 1 + 1 = 3

𝑇(3) = 2𝑇(2) + 1 = 2 ⋅ 3 + 1 = 7

따라서 𝑇(𝑛)는 \(2^{n}-1\)이라는 공식을 만족하게 됩니다.

 

이 것을 수학적 귀납법을 통해 증명할 수 있는데 기본식은 \(T\left( 1\right) =1=2^{1}-1\), 귀납가정으로 \(T\left( k\right) =2^{k}-1\)이 성립된다고 가정해보겠습니다.

 

이 때,  \(T\left( k+1\right)\)을 구할 때 \(T\left( k+1\right) =2T\left( k\right) +1=2\left( 2^{k}-I\right) +1 =2^{k+1}-1 \)이 됩니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

위에 문제 해설에서 봤듯이 귀납적으로 \(T\left( n\right) =2^{n}-1)\이 성립되기 때문에

위 알고리즘의 시간 복잡도는 \(O\left( 2^{n}\right)\)이 됩니다.

 

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

공간 복잡도는 주로 재귀 호출 스택의 깊이에 의해 결정됩니다.

하노이의 탑 문제에서 재귀 호출의 깊이는 원판의 수 𝑛이 됩니다.

각 재귀 호출은 일정한 공간을 사용하므로, 최대 재귀 깊이는 𝑛이 됩니다.

따라서, 공간 복잡도는 𝑂(𝑛)이 됩니다.