[Jungle My Note | W02] 하노이의 탑 정리.md

[Jungle My Note | W02] 하노이의 탑 정리.md

하노이의 탑 정리

알아두면 좋은 재귀의 조건 3가지:

1. 문제를 더 작은 하위 문제로 쪼갤 수 있는가?
2. 하위 문제들이 원래 문제와 같은 구조인가?
3. 종료 조건(base case)이 존재하는가?

1. 아이디어와 설명

핵심 아이디어 1

n4가 to로 가면, 더 이상 신경 쓸 필요 없어진다.
즉, n의 처리 과정 중 일부를 n-1로 볼 수 있다. (주 문제를 동일한 유형의 Sub 문제를 사용해서 처리)

핵심 아이디어 2

hanoi(n)은 n개의 원판을 옮긴다. 어떻게인지는 중요하지 않음.
(최소한 당장은, 나중에 base case로 해결할 것.- 믿음으로 가는거임.)

---

2. 실제 flow 그리기

예시는 n=4에서 시작한다.

1) 시작 상태

────────────────────────────────────────
  [1]
  [2]
  [3]
  [4]              .                 .
────────────────────────────────────────
 from             temp               to

2) hanoi(3): 1,2,3을 temp로 이동 완료

────────────────────────────────────────
                  [1]
                  [2]
  [4]             [3]                .
────────────────────────────────────────
 from             temp               to

즉, 4만 목적지로 보내면 된다.

3) move 4 → to

────────────────────────────────────────
                  [1]
                  [2]
   .              [3]               [4]
────────────────────────────────────────
 from             temp               to

여기서 4는 없어진다. (이미 원하는 위치에 존재하고, 나머지 블록을 위치시키는데 4를 신경쓰지 않아도 되므로)

temp와 from은 swap 가능하다. = hanoi(3) (하지만 문제 풀이를 위해선 to는 유지되어야 한다.)

즉 1,2,3이 남아 있고, 기둥 이름만 바뀐 채 다시 같은 문제를 푸는 것이다.

이제 hanoi(3): 1,2,3을 to로 옮겨야 한다.
먼저 hanoi(2): 1,2를 from으로.

4) 1,2가 from으로 이동 완료

────────────────────────────────────────

  [1]
  [2]              .                [4]
────────────────────────────────────────
 from             temp               to

5) move 3 → to

────────────────────────────────────────

  [1]                               [3]
  [2]              .                [4]
────────────────────────────────────────
 from             temp               to

이제 hanoi(2): 1,2를 to로 옮겨야 한다.
먼저 hanoi(1): 1을 temp로.

6) move 1 → temp

────────────────────────────────────────

                                    [3]
  [2]             [1]               [4]
────────────────────────────────────────
 from             temp               to

7) move 2 → to

────────────────────────────────────────
                                    [2]
                                    [3]
   .              [1]               [4]
────────────────────────────────────────
 from             temp               to

이제 hanoi(1): 1을 to로.
Base Case — 1이 temp(=from 역할)에 있음.

8) Base Case 시작 — 1을 옮기기 전

────────────────────────────────────────
                                    [2]
                                    [3]
   .              [1]               [4]
────────────────────────────────────────
(temp)          (from)              (to)

9) move 1 → to — 완료!

────────────────────────────────────────
                                    [1]
                                    [2]
                                    [3]
   .               .                [4]
────────────────────────────────────────
 from             temp               to

                 Done!

---

3. 의사코드

화이트보드에 적힌 형태를 최대한 그대로 옮기면:

h(n, from_idx, to_idx)
h(n-1, from, temp)
move n to
h(n-1, temp, from)

문맥상 정리해서 쓰면:

h(n, from_idx, to_idx, temp_idx):
    if n == 1:
        move from_idx to to_idx
        return
    h(n-1, from_idx, temp_idx, to_idx)
    move n to to_idx
    h(n-1, temp_idx, to_idx, from_idx)

---

해결 flow 요약

화이트보드 오른쪽 아래 내용 정리:

1. from에서 n-1개를 temp로 옮긴다
2. 그럼 to로 n 블록을 옮길 수 있다
3. 이제 n 블록은 해결됨 (이미 옮겨졌으므로)
4. 이제 n-1을 temp에서 to로 옮긴다

base case는 n이 1일 때, 바로 from에서 to로 이동.

---

생각 정리에 사용한 화이트보드 메모