1 재귀적인 문제들

• 1.1 하노이의 탑

  

  다들 하노이의 탑이라는 퍼즐에 대해서 들어봤을 것이다. 아니면 직접 해본 사람도 있을 것이고. 이 게임의 목표는 탑 전체를 다른 기둥으로 옮기는 것인데, 작은 원반 위에는 큰 원반이 올라 갈 수가 없다. 그렇다면 이 문제를 해결하기 위한 최적해를 구할 방법이 존재할까? 즉, 최소한의 이동 횟수는 얼마일까?

  그럼 천천히 계산을 해보도록 하자. 먼저, 적절한 표기법부터 사용하여, 명명정복(name and conquer)을 한다.

• n = 원반의 갯수

• T(n) = 다른 기둥으로 n개의 원반을 옮기는데 필요한 최소 이동 횟수

  먼저, 작은 차근차근 따져보자. T(0) = 0 이다.그리고 T(1) = 1, T(2) = 3 이 된다. 여기서 일반적인 규칙에 대해서 고찰해보자. 최상위 2개의 원반을 가운데 기둥으로 옮기고, 그리고 마지막 원반을 셋째 기둥으로 옮긴다. 이 부분에서 우리는 원반을 다른 기둥으로 옮기는 일반적인 문제에 대한 힌트를 얻을 수 있다.

  바로 N - 1개의 기둥을 다른 기둥으로 완전히 옮기고 난 뒤에 가장 큰 원반을 끝으로 옮겨야 한다는 점이다. 그리고 나서는 나머지 원반 N - 1개를 다시 큰 원반 위로 옮겨야한다. 따라서 원반 N 개의 이동횟수는 2T(n-1) + 1을 넘지 않는다.

  T(n) <= 2T(n-1) + 1, n > 0

  따라서 다음과 같은 식이 성립한다.

  T(0) = 0
  T(n) = 2T(n-1) + 1

  이와같은 일단의 등식들을 점화식(recurrence formula) 또는 점화 관계식(recurrence relation)이라고 부른다. 이를 통해서 임의의 n에 대해 T(n)을 계산 할 수가 있다. 하지만 n이 너무 크다면 점화식을 통한 계산이 마땅치 못하다.

  따라서 T(n)을 빠르게 계산할 수 있는 점화식의 해가 있다면, 그 해를 이용하는 것이 좋다. 그렇다면 이 임의의 해를 어떻게 구할까? 먼저, 이를 위해서 작은 사례들 부터 관찰 하는 것이다.

  T(3) = 7
  T(4) = 15
  T(5) = 31

  여기서 우리는 T(n) = 2^n - 1 임을 유추해볼수 있다. 적어도 n < 6 안에선 유효한 공식이다. 수학적 귀납법(mathematical induction) 은 정수 n에 관한 어떤 명제가 모든 n에 대해 참임을 증명하는 일반적인 방법이다. 귀납법에서 n의 가장 작은 단위부터 증명을 시작하는데, 이를 기초(basis) 라고 한다. 그리고 n - 1 까지의 값들에 대해 증명되었다는 가정하에 n을 증명한다.

  이런 방법으로 현재 도출한 공식을 증명해보도록 하자. 여기서 앞서 얻은 2가지 공식을 적용하면 다음과 같은 등식이 나온다.

  T(n) = 2T(n-1) + 1 = 2(2^(n-1) - 1) + 1 = 2^n - 1

  따라서 우리가 도출한 해를 구하는 공식이 성립함을 알 수 있다. 여기서 우리가 얻을 수 있는 결론은 다음과 같다.

  1.작은 사례들을 살펴보면서, 문제에 대해 통찰한다.

  2.수학 공식을 구하고 증명을 만든다.

  3.수학 공식의 닫힌 형식을 구하고 증명한다.

  .from 구체수학 1.1 하노이의 탑