초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
기둥에 쌓인 원반을 규칙에 맞게 다른 기둥으로 옮기는 하노이 탑 퍼즐이 있습니다. 원반이 3개면 손으로 풀지만, n개일 때 옮기는 순서를 출력하는 프로그램은 반복문으로 적기 막막합니다. 큰 문제를 같은 모양의 작은 문제로 줄여 푸는 방법을 쉬운 예부터 알아봅시다.
경우의 수 글에서 본 5!은 1부터 5까지 곱한 값입니다. 잘 보면 5!은 5 × 4!이고, 4!은 4 × 3!입니다. 그렇게 내려가다 1!에 닿으면 답은 1입니다. 이 관찰을 코드로 옮기면 다음과 같습니다.
출력 없음함수 안에서는 지금 호출의 n만 보입니다.
factorial 안에서 다시 factorial을 부릅니다. 이렇게 함수가 자기 자신을 부르는
것을 재귀(recursion)라 합니다. 재귀 함수는 두 부분으로 이루어집니다.
n == 1). 이것을 기저 사례(base case)라
합니다. 수학적 귀납법의 기초 단계와 같은 역할입니다.factorial(n - 1)).기저 사례가 없으면 호출이 끝없이 내려갑니다. 문제가 작아지다 반드시 기저 사례에 닿는지 확인해야 합니다.
factorial(4)는 factorial(3)의 값을 받아야 4를 곱할 수 있습니다.
factorial(3)도 factorial(2)를 기다립니다.
factorial(4)의 값을 구합니다.
끝나지 않은 호출이 위로 쌓였다가 factorial(1)부터 거꾸로 풀립니다. 가장 나중에
부른 호출이 가장 먼저 끝납니다. 스택 프레임 글에서 본 대로,
컴퓨터는 호출마다 스택 프레임을 쌓아 끝나지 않은 호출의 n을 따로 기억합니다.
하노이 탑은 A 기둥에 큰 것부터 쌓인 원반을 모두 C 기둥으로 옮깁니다. 한 번에 맨 위 원반 하나만 옮길 수 있고, 작은 원반 위에 큰 원반을 올릴 수 없습니다.
옮길 원반이 있는 기둥을 누릅니다.0 / 최소 7
원반 3개를 C로 옮긴 뒤 4개로도 해 봅시다.
가장 큰 원반만 생각해 봅시다. 이 원반이 C의 바닥에 가려면 그 순간 나머지 n − 1개는 모두 B에 있어야 합니다. 그러니 순서가 정해집니다.
1과 3은 원반이 하나 적은 하노이 탑이고, 원반이 한 개면 그냥 옮기면 됩니다(기저 사례). 코드로 옮기면 다음과 같습니다.
// 원반 n개를 start에서 end로 옮긴다
void hanoi(int n, char start, char end,
char via) {
if (n == 1) {
printf("%c → %c\n", start, end);
return;
}
hanoi(n - 1, start, via, end);
printf("%c → %c\n", start, end);
hanoi(n - 1, via, end, start);
}
n − 1개를 어떻게 옮길지는 따지지 않고 같은 함수에 맡깁니다. n − 1개에서 맞으면 n개에서도 맞으니 수학적 귀납법의 귀납 단계와 같습니다.
"다음"을 눌러 재귀 풀이를 한 수씩 따라갑니다.0 / 최소 7
수마다 어느 호출 안에서 둔 수인지 보입니다.
n개를 옮기는 횟수는 n − 1개일 때의 두 배에 1을 더한 값이라 1, 3, 7, 15, …로 늘어 n개면 2ⁿ − 1번입니다. 시간 복잡도로는 O(2ⁿ)입니다.
원반 6개짜리 하노이 탑을 글의 방법대로 63번 만에 옮깁니다. 40번째 수에서 옮기는 원반은 작은 쪽에서 몇 번째 원반일까요? 가장 작은 원반이 1번째입니다. 숫자로 답하세요.