이 C++ 프로그램은 이진수(binary) 값을 활용하여 하노이의 탑(Tower of Hanoi) 문제의 해답을 출력합니다. 재귀 호출 없이 비트 연산만으로 원판의 이동 순서를 계산할 수 있다는 점이 특징입니다.
이진수로 하노이의 탑을 표현하는 원리
각 원판(disk)에는 하나의 이진 자릿수(bit)가 대응됩니다.
- 최상위 비트(MSB)는 가장 큰 원판을 나타냅니다. 값이 0이면 해당 원판이 시작 기둥에, 1이면 최종 목적지 기둥에 있다는 의미입니다.
- 비트열은 왼쪽에서 오른쪽으로 읽으며, 각 비트를 통해 대응되는 원판의 위치를 판별할 수 있습니다.
비트 값이 바로 앞 비트와 같으면, 해당 원판은 같은 기둥에서 이전 원판 위에 쌓여 있습니다. 반대로 값이 다르면, 해당 원판은 이전 원판 기준으로 왼쪽 또는 오른쪽 한 칸 떨어진 기둥에 위치하게 됩니다.
알고리즘
Begin
원판 개수 n을 입력받는다.
변수 n과 a를 선언한다.
a = 1부터 (1<<n) - 1까지 반복문을 실행한다.
//
여기서,
(a & a - 1) = a와 a - 1의 비트 AND 연산
(a | a - 1) = a와 a - 1의 비트 OR 연산
% 는 나머지(모듈로) 연산자이다.
//
(a & a - 1) % 3 번 기둥에서 ((a | a - 1) + 1) % 3 번 기둥으로
원판을 옮긴다는 결과를 출력한다.
End예제 코드
#include<iostream>
using namespace std;
int main() {
int n, a;
cout<<"\nEnter the no of Disks: ";
cin>>n;
for (a = 1; a < (1 << n); a++) {
cout<<"\nDisk Move from Peg "<<(a&a-1)%3<<" to Peg "<<((a|a-1)+1)%3;
}
cout<<"\n";
}실행 결과
Enter the no of Disks: 3 Disk Move from Peg 0 to Peg 2 Disk Move from Peg 0 to Peg 1 Disk Move from Peg 2 to Peg 1 Disk Move from Peg 0 to Peg 2 Disk Move from Peg 1 to Peg 0 Disk Move from Peg 1 to Peg 2 Disk Move from Peg 0 to Peg 2
동작 방식 설명
반복문은 1부터 2^n - 1까지 실행되며, 이는 하노이의 탑 문제에서 필요한 총 이동 횟수와 정확히 일치합니다. 즉, 원판이 n개일 때 총 2^n - 1번의 이동이 발생하고, 반복 변수 a를 1씩 증가시키며 카운트하는 과정이 곧 이진수 계산과 동일한 패턴을 따르게 됩니다.
매 단계에서 (a & a - 1)은 a의 가장 오른쪽에 있는 1비트를 제거한 값이 되고, (a | a - 1)은 그 아래 비트들을 모두 1로 만든 값이 됩니다. 이 두 값에 3으로 나머지 연산을 적용하면 출발 기둥과 도착 기둥의 번호(0, 1, 2)가 자연스럽게 결정됩니다.
이처럼 비트 연산을 활용하면 재귀 함수나 스택 자료구조 없이도 하노이의 탑의 전체 이동 순서를 간결하고 효율적으로 구현할 수 있습니다.