과제 4: 레드-블랙 하노이탑 하노이탑은 모두가 잘 알고 있는 문제이다. a, b, c 3개의 원기둥이 있고, 서로 다른 크기의 n개의 구멍뚫린 원반이 a에 크기 순으로 놓여 있는데 이를 c로 다음 규칙을 지키면서 이동하면 된다. - 한번에 한개씩 - 작은 원반 위에 큰 원반 x 이제 2n개의 구멍뚫린 원반을 이용하는 하노이탑을 생각해보자. 원반의 크기는 n가지로, 각 크기마다 빨간 원반, 까만 원반 둘이 있다. 처음 a기둥에는 원반이 크기순서대로 놓여 있는 것은 같지만, 같은 크기의 원반 둘은 빨간 원반이 까만 원반 위에 있다. 이제 하노이탑 규칙을 따르면서, c 기둥에 그대로 원반을 모두 옮기려고 한다. (크기 순서대로, 같은 크기는 빨간 원반이 까만 원반 위) 이 때 필요한 원반의 최소 이동회수를 ..