하노이 탑 재귀 문제는 엉뚱하게 해결할 수 있으니 주의해야 한다.

@freeCodeCamp

1. 하노이의 탑

하노이의 탑은 알고리즘 과목에서 "재귀"를 공부할 때 단골로 나오는 예제 중 하나다. 너무 자주 나와서 모르는 개발자가 없는 것 같다. 그래서인지, 문제는 사실 꽤 어려운 편에 속하는 데도 불구하고 문제 난이도가 최하로 분류되곤 한다.

 

문제는 매우 간단하다. 왼쪽의 원판 N개를 3번째 막대기로 하나씩 옮기면 된다. 이때 각 원판은 자신보다 무거운 것이 위에 있으면 안 된다.

 

하노이의 탑 알고리즘은 구글링을 해서 누구나 쉽게 알 수 있으니, 이 글에서는 내가 이 문제를 풀면서 저질렀던 실수를 작성하고 이에 대해 피드백(반성)을 하려고 한다.

 

 

2. 알고리즘은 풀기만 하면 안 된다.

알고리즘 문제들을 가지고 IT기업에서 면접을 보는 이유는 그것을 풀 수 있는가의 여부가 아니라, 그것을 어떻게 푸는지 직접 확인하기 위해서다. 만약 알고리즘 문제를 푸는 것 자체가 중요했다면 알고리즘 테스트를 통째로 필기 시험으로 대체했을 것이다. 하지만 면접을 본다. 알고리즘 문제를 푼다고 해서 그 사람이 컴퓨팅 사고력을 갖췄는지는 100% 확신할 수 없기 때문이다.

 

IT 개발자에게 필요한 역량은 똑똑한 지능이 아니라 컴퓨팅 사고력이다. 컴퓨팅 사고력이란 컴퓨터의 관점에서 문제를 정의하고 그 문제를 해결할 수 있는 시스템을 구성하는 능력을 말한다.

 

하노이의 탑 문제도 마찬가지다. 이것은 "재귀" 개념을 알고 있는지 묻는 문제다. 재귀는 컴퓨팅 사고력에서 매우 중요한 위치를 차지하는 개념이다. 하노이의 탑 문제는 주의해야 한다. 이 문제를 풀었다고 재귀적 사고방식을 갖췄다고 평가할 수가 없기 때문이다. 재귀를 쓰지 않아도, 즉 컴퓨팅 사고력을 갖추지 않아도 얼렁뚱땅 재귀를 구성할 수도 있어서 주의해야 한다.

 

 

3. 하노이의 탑을 "실수로 해결해버리기"

내가 처음에 대학 C언어 강의에서 나온 하노이의 탑 문제를 해결했을 때, 나는 그것을 제대로 푼 줄 알았다. 재귀를 이해하고 사용할 수 있는 사람이라고 생각했다. 그러나 그것은 착각이었다. 나는 컴퓨팅 사고력을 전혀 사용하지 않고 재귀를 구성해버렸다.

 

나는 이 문제를 어떻게 접근했는가? 재귀고 뭐고 간에, 일단 3개의 원판이 있다고 가정하고 그것을 세 번째 막대로 옮기는 풀이법을 생각해보았다. 여러 번의 시행착오 끝에, 1번 원판을 세 번째 막대로 옮기고, 2번 원판을 두 번째 막대로 옮기고, 다시 1번 원판을 두 번째 막대로 옮겼다. 그리고 가장 무거운 3번 원판을 세 번째 막대로 옮기고, 1번 원판을 첫 번째에, 2번 원판을 세 번째, 그리고 마지막으로 1번 원판을 최종적으로 세 번째 막대로 옮겼다.

 

그리고 이 복잡한 과정을 이해하기 위해 원판이 4개가 있는 경우를 생각했다. 훨씬 더 복잡해졌으나, 여러 번의 시행 착오 끝에, 패턴을 발견하고 가설을 세웠다. 가장 무거운 원판이 세 번째 막대의 가장 아래로 가야 한다. 따라서 가장 먼저 N-1개의 원판이 두 번째 막대로 가야 한다. 그리고 무거운 원판을 세 번째 막대로 옮기고, N-1개의 원판을 다시 세 번쨰 막대로 옮기면 된다.

 

나는 이렇게 패턴을 발견하고 일반화해서 하노이의 탑 문제를 풀었다. 빠르게 패턴을 발견했다고 생각하고 스스로 대견하게 생각했으나, 이것은 재귀의 본질을 생각하면 아쉬운 풀이였다.

 

 

4. 패턴을 귀납적으로 추론하는 것은 재귀가 아니다.

내가 잘못한 핵심은 바로 재귀 패턴을 귀납적으로 추론했다는 점에 있었다. 원판이 3개 있는 경우의 해결책을 먼저 만들어보고, 그 다음 원판이 4개가 있는 경우, 그 다음 원판이 5개인 경우, .... 이런 식으로 일반화된 패턴을 추론했다. 그저 추론해놓고 보니 재귀였을 뿐이었다.

 

이런 패턴 추론 사고방식이 틀린 것은 아니다. 수능 수학에서 수열 문제의 단골로 출제될 정도로 아주 중요한 사고 방식 중 하나다. 귀납적으로 개별 요소들을 모아보며 거기서 규칙을 이끌어내는 방법이다.

 

문제는 이것이 재귀가 요구하는 컴퓨팅 사고력과는 별개라는 점이다. 재귀는 귀납이 아니라 연역이며, 그 구조는 개별 요소에서 일반화된 규칙을 떠올리는 것이 아니라, 처음부터 거꾸로 문제를 추상적으로 푸는 구조다.

 

프로그램의 구조

 

애초에 컴퓨터 프로그램이란게 원래 그렇게 동작하도록 되어 있다. 알고리즘의 최초 진입점이 되는 함수(main)에서 제어 흐름이 시작되고, 차례대로 하위 함수들이 호출된다. 각 함수들은 각자 main 함수의 일부 문제를 담당하며, 다시 하위 함수는 또 다른 하위 함수로 분해된다. 그렇게 함수 스택이 쌓이고 해체되는 과정을 거쳐 최종적으로 main 함수로 제어흐름이 돌아온다. ( ※ 객체지향의 사고 방식 또한 메소드 단위에서는 위와 같이 분해한다. )

 

그 어떤 컴퓨터도 데이터를 찬찬히 살펴보며 일반화된 규칙을 떠올려서 풀지 않는다. 인공지능 또한 별개의 알고리즘이다! 컴퓨터 자체에는 그런 추론 능력이 없다.

 

 

5. 하노이의 탑 문제를 제대로 푸는 법

바로 main 함수에서 시작한다는 상상을 하는 식으로 접근해야 한다. 처음부터 이 문제는 거꾸로 생각해야 한다. 큰 문제부터 해결해야 한다. 원판 3개와 같이 작은 문제부터 해결하고 거기서 패턴을 추론하는 것은 아쉬운 접근이다.

 

제일 마지막 단계, 최종 단계, 즉 main 함수가 처리하는 단계에서 하노이의 탑 문제를 해결하려면 어떻게 해야 할까?

 

답은 쉽다. 가장 무거운 원판을 세 번째 막대로 옮겨야 한다. 그러기 위해선 무거운 원판 위의 원판들을 임시로 두 번째 막대에 옮겨야 할 것이다. 그리고 마지막에 나머지 원판을 그 무거운 원판 위로 옮겨야 한다.

 

이렇게 하면 전체 문제를 즉시 해결할 수 있다. 거꾸로 생각한 것이다! 거꾸로 생각했기 때문에 문제를 즉시 풀었다.

 

하지만 뭔가 이상하다. 그렇다면 가장 무거운 원판 위에 있는 원판들을 어떻게 해야 두 번째 막대로 옮길 수 있을까? 그리고 두 번째 막대로 옮겨진 원판들을 어떻게 해야 세 번째 막대로 옮길 수 있을까? 

 

이 질문은 첫 단계에선 중요하지 않다. 우리는 하노이의 탑 문제를 거꾸로 생각하고 있다. 해결의 최종 단계부터 생각했기 때문에 우리는 필연적으로 문제를 풀면서 동시에 새로운 하위 문제들로 분할하는데 성공했다. 이것이 컴퓨터 과학에서 그토록 중요시 여기는, "문제를 분해하라!"이다.

 

가장 처음 신경써야 할 것은 문제의 최종 단계를 고려해가며 문제를 풀어버리는 것이다. 그 과정에서 문제를 작은 문제들로 분할하기 마련이다. 이 하위 문제들은 풀렸다고 가정하자. 최종 단계만 신경쓰자.

 

 

그리고 이제 하위 문제를 풀면 되는 것이다.

하위 문제는 다음 두 개다. 가장 무거운 원판 위에 있는 원판들을 어떻게 해야 두 번째 막대로 옮길 수 있을까? 두 번째 막대로 옮겨진 원판들을 어떻게 해야 세 번째 막대로 옮길 수 있을까?

 

이 하위 문제들은 방금 우리가 푼 하노이의 탑 문제와 똑같은 구조다. 따라서 이 문제의 구조는 재귀적 구조다. 즉, 문제 풀이 논리가 복사된다는 것이다. 그저 재귀 구조의 탈출 조건만 신경쓰면 된다. 탈출 조건이란 작은 문제(3개의 원판 옮기기)이므로 이것 또한 쉽게 풀린다.

 

이 문제가 재귀 구조라는 깨달음은 바로 이 단계에 이르러서야 비로소 발견되어야 하는 것이다. 처음부터 하노이의 탑을 재귀 문제라고 알고 시작하는 것은 이 문제의 해법을 미리 알고 있거나, 혹은 교과서에 재귀를 막 배우고 나서 이 문제를 봤기 때문에 그런 것일 뿐이다. 처음부터 어떤 문제가 재귀 구조라고 알고 시작하는 경우는 드물다.

 

 

6. 귀납 추론이 재귀가 요구하는 컴퓨팅 사고력의 본질이 아닌 이유

이유는 아주 간단하다. 일단 귀납적으로 패턴을 발견하고 수학으로 기술하는 것은 너무 어렵다.

 

하노이의 탑 문제는 시행착오를 겪으면 아주 간단하게 해결된다. 귀납접으로 접근해도 패턴을 알아차릴 수 있다. 그러나 이런 교과서적인 문제를 벗어나 실제로 어려운 알고리즘 문제를 시행착오를 통한 귀납 추론을 사용해 풀려면 그대로 멘붕에 빠지게 된다. 그렇게 도출할 최종적인 공식이나 패턴의 복잡도가 우리의 상상을 항상 뛰어넘기 때문이다. 심지어 귀납 추론으로 패턴을 발견하려는 경우, 그 결과가 학부 과정을 뛰어넘는 수학 지식이 요구되는 경우도 있다. (빅테크 기업은 의도적으로 이러한 문제를 제시한다고 한다)

 

컴퓨터의 본질은 계산을 대용량으로 빠르게 처리할 수 있다는 점에 있다. 추론 기계가 아니다. 수학 기계가 아니므로, 컴퓨터를 십분 활용하기 위해서는 보편 수학 법칙을 추론하는 것이 아니라 컴퓨터가 빠르게 계산만 하게 만들면 된다. 대신 그 계산 구조가 효율적이고 간단해야 할 것이다. 따라서 개발자란 문제를 분할하고 하나하나 정복하는 식으로 문제를 컴퓨터의 도움을 받아 해결한다.