하노이의 탑:
점화식 → 닫힌형 → 최소성(엄밀) → 이동 규칙 공식화 → 구현
분해 논리로 점화식을 세우고, 닫힌형을 두 방식으로 유도하고, 최소성을 강한 귀납으로 엄밀히 확정한다. 이어서 어느 디스크가 언제 움직이는가를 $v_2$ 가측과 “ruler function”으로 공식화하고, 재귀·반복 구현까지 연결한다.
1) 문제와 불변식
- 세 기둥 $A,B,C$, 크기 다른 $n$개의 원반.
- 제약
- 한 번에 한 원반만 이동.
- 큰 원반은 작은 원반 위에 올 수 없음.
- 목표: 모든 원반을 $A\to C$로 최소 이동으로 옮기기.
불변식
- 초기 상태에서 성립하는 제약 1–2는 모든 이동 후에도 유지되어야 한다.
- 기저 $n=0$이면 이동 0회.
2) 분해와 점화식
가장 큰 원반을 움직이려면 그 위의 $n-1$개를 보조 기둥으로 치워야 한다.
- $n-1$개를 $A\to B$: $T_{n-1}$
- 가장 큰 원반 1개 $A\to C$: $+1$
- $n-1$개를 $B\to C$: $+T_{n-1}$
$$
\boxed{T_n=2T_{n-1}+1,\quad T_0=0.}
$$
3) 닫힌형(closed form) 두 가지 유도
3.1 특수해 + 동차해
$$
T_n-2T_{n-1}=1.
$$
- 동차해: $T_n^{(h)}=C\cdot 2^n$
- 특수해(상수 가정): $T_n^{(p)}=-1$
$T_n=C2^n-1$, $T_0=0\Rightarrow C=1$ 이므로
$$
\boxed{T_n=2^n-1.}
$$
3.2 전개(대치)
$$
T_n=2(2T_{n-2}+1)+1=4T_{n-2}+3=\cdots=2^nT_0+(2^n-1)=2^n-1.
$$
4) 최소성의 엄밀 증명(강한 귀납)
정리. 임의의 합법 알고리즘에 대해 최소 이동 횟수는 $T_n=2^n-1$.
증명.
- 기저 $n=0$: 0회로 자명.
- 귀납 가정: 모든 $k<n$에 대해 최소 이동 횟수는 $T_k=2^k-1$.
- 귀납 단계 $n$:
- 가장 큰 원반을 움직이는 순간을 보자. 그때까지 그 위에는 작은 원반이 없어야 하므로 그 이전에 최소 $T_{n-1}$회가 필요.
- 가장 큰 원반 1회 이동: $+1$.
- 이후 남은 $n-1$개를 목적 기둥으로 옮기는 데 다시 최소 $T_{n-1}$회 필요.
- 어떤 합법 알고리즘도 $2T_{n-1}+1$ 미만으로는 불가능. 귀납 가정 대입으로 $2(2^{n-1}-1)+1=2^n-1$.
- 표준 알고리즘이 이 상한을 달성하므로 하한과 상한이 일치. QED.
부언(유일성). 시작·목적 기둥을 고정하면 최소 해의 이동 순서가 유일(peg 레이블 동형 제외).
5) “어느 디스크가 움직이는가”의 공식화
$k$번째($1\le k\le 2^n-1$) 이동에서 움직이는 디스크 번호는
$$
\boxed{d(k)=v_2(k)+1,}
$$
여기서 $v_2(k)=\max{t\ge 0:2^t\mid k}$는 2-진 가측(끝의 0의 개수)이다. 이는 이진 카운터 증가 시 올림(carry)이 최초로 멈추는 자릿수에 해당한다. 문헌에서는 $v_2$ 값의 열을 ruler function이라 부른다.
최소 원반의 방향 규칙
- $n$이 홀수면 최소 원반은 $A\to C\to B\to A$ 시계 순환.
- $n$이 짝수면 최소 원반은 $A\to B\to C\to A$ 반시계 순환.
- 최소 원반 사이사이에는 $d(k)>1$인 유일 합법 이동이 끼어들어 전체 순서가 완성된다.
6) 복잡도와 규모 감각
- 시간: $2^n-1$ 이동(지수)
- 공간: 재귀 스택 $O(n)$
- 출력 자체가 지수 크기이므로 실습은 보통 $n\le 15$ 권장.
7) 구현
7.1 재귀 구현
def hanoi(n, src='A', aux='B', dst='C'):
if n == 0:
return
hanoi(n-1, src, dst, aux)
print(f"{src} -> {dst}")
hanoi(n-1, aux, src, dst)
# 예시: hanoi(3)장점: 점화식과 1:1 대응. 단점: 스택 사용.
7.2 반복(비재귀) 구현 — (v_2)/LSB 이용
아이디어
- $k$번째 이동 디스크 $d=v_2(k)+1$.
- $\mathrm{lsb}(k)=k&(-k)=2^{v_2(k)}\Rightarrow v_2(k)=\texttt{lsb}(k).\text{bit_length}()-1$.
- 최소 원반 방향은 $n$의 홀짝으로 결정. 나머지는 “유일 합법 이동” 선택.
def hanoi_iter(n, src='A', aux='B', dst='C'):
# peg 순서: n 홀수는 시계, 짝수는 반시계에 맞춰 배치
pegs = [src, dst, aux] if n % 2 == 1 else [src, aux, dst]
# 각 원반의 peg 인덱스(0/1/2). 모두 src에서 시작
pos = [0] * n
total = (1 << n) - 1
for k in range(1, total + 1):
d = (k & -k).bit_length() - 1 # 0-based 디스크 번호 = v2(k)
cur = pos[d]
if d == 0:
# 최소 원반은 한 방향으로만 회전 이동
to = (cur + 1) % 3
else:
# 두 후보 중 제약을 깨지 않는 유일 합법 이동 선택
cands = [p for p in (0, 1, 2) if p != cur]
def legal(to):
# 도착 peg 위의 최상단 원반 번호가 d보다 크면 합법
for smaller in range(d):
if pos[smaller] == to:
return False
return True
to = cands[0] if legal(cands[0]) else cands[1]
print(f"{pegs[cur]} -> {pegs[to]}")
pos[d] = to
# 예시: hanoi_iter(3)8) 드라이런 (n=3)
총 23 − 1 = 7회.
| 단계 k | 이동 | d(k) = v₂(k) + 1 |
|---|---|---|
| 1 | A → C | 1 |
| 2 | A → B | 2 |
| 3 | C → B | 1 |
| 4 | A → C | 3 |
| 5 | B → A | 1 |
| 6 | B → C | 2 |
| 7 | A → C | 1 |
검증: 제약 위반 없음. 총 7회.
9) 자주 하는 오류 체크
- 점화식에서 상수항 $+1$ 누락.
- 기저 $T_0, T_1$ 모호.
- 반복 구현에서 최소 원반 방향을 $n$의 홀짝과 반대로 설정.
- “큰 원반 먼저 이동” 같은 위반 시나리오 허용.
10) 요약
- 분해 → $T_n=2T_{n-1}+1$
- 닫힌형 $2^n-1$
- 강한 귀납으로 최소성 확정, 순서의 유일성 언급
- $k$번째 이동 디스크: $\boxed{v_2(k)+1}$
- 최소 원반 방향: $n$ 홀수=시계, 짝수=반시계
- 재귀는 명료, 반복은 스택 없음