[ALGORITHM] 15. 하노이의 탑

하노이의 탑 (위키피디아)

하노이의 탑 - 위키백과, 우리 모두의 백과사전

 

재귀 알고리즘의 대표적인 예시 중 하나인 하노이의 탑 문제다.

하노이의 탑 문제에서 원판이 이동하는 횟수는 2^n - 1(메르센 넘버) 이기에 시간 복잡도는 O(2^n)으로 볼 수 있으며

원판의 수가 많아질수록 계산시간이 오래 걸린다.

 

void hanoi(int n, int from, int to, int by) {

	if (n == 1) {

		std::cout << from << "▶" << to << std::endl;
	
	} else {

		hanoi(n - 1, from, by, to);
		std::cout << from << "▶" << to << std::endl;
		hanoi(n - 1, by, to, from);
	}
}