문제 정의

1. 목표: 크기가 다른 원판 N개를 한 기둥(A)에서 다른 기둥(C)으로 모두 옮기기
2. 조건:
   1) 한 번에 하나의 원판만 옮길 수 있음
   2) 큰 원판이 작은 원판 위에 놓일 수 없음
   3) 임시 기둥(B)을 사용할 수 있음

알고리즘

1. 전체 문제: 기둥 A에서 N개의 원반을 기둥 B를 사용하여 기둥 C로 옮기는 알고리즘
2. 부분 문제
   1) 기둥 A에서 N-1개의 원판을 기둥 C를 사용해서 기둥 B로 옮김
   2) 기둥 A에 남은 1개의 원판을 기둥 C로 옮김
   3) 기둥 B에서 N-1개의 원판을 기둥 A를 사용해서 기둥 C로 옮김

구현 코드

def hanoi(n, start, target, aux):
  if n == 1:
    print(f"{start} -> {target}")
  
  # 부분문제1
  hanoi(n-1, start, aux, target)
  
  # 부분문제2
  print("f{start} -> {target}")
  
  # 부분문제3
  hanoi(n-1, aux, target, start)

분할 정복

분할 정복이란?

• 분할: 문제를 작은 부분으로 나눔
• 정복: 부분 문제를 해결
• 결합: 부분 문제의 해답을 합쳐서 전체 문제 해결

하노이의 탑에서 분할 정복은?

• 분할: N개의 원판을 옮기는 문제를 아래 3가지 작은 문제로 나눔
  • 시작 기둥에 있는 N-1개 원판을 목표 기둥을 사용해 보조 기둥으로 옮기고
  • 남은 1개 원판을 목표 기둥으로 옮기고
  • 보조 기둥에 있는 N-1개 원판을 시작 기둥을 사용해 목표 기둥으로 옮김
• 정복:
  • N-1개 원판을 옮기는 문제도 동일한 방식으로 재귀적으로 문제를 나눠서 풀어감
  • 이때 옮겨야 하는 원판의 개수가 1개이면 바로 목표 기둥으로 옮김
• 결합: 부분 문제를 합쳐서 N개 옮기기 문제 해결