12강 / 20강

점화식 — 자기를 자기로 설명하기

피보나치 · 하노이 · 그리고 알고리즘의 비용

토끼 한 쌍이 있습니다. 태어난 지 두 달이 지나면 매달 한 쌍씩 새끼를 낳아요. n개월 뒤 토끼는 몇 쌍일까요?

이번 달 토끼는 지난달 토끼 전부 + 두 달 전 토끼가 낳은 새끼입니다. 그래서 이렇게 쓸 수 있어요.

F(n) = F(n−1) + F(n−2), F(1) = F(2) = 1

이렇게 앞의 항으로 다음 항을 정의하는 식을 점화식(recurrence relation)이라 합니다. 11강의 귀납법과 정확히 같은 모양이에요 — 시작값(기초)과 넘기는 규칙(귀납).

고등학생자기를 자기로 설명하기

11강의 귀납법과 정확히 같은 모양입니다.

시작값 + 넘기는 규칙 = 점화식

유명한 예들

이름	점화식	뜻
등차	aₙ = aₙ₋₁ + d	일정하게 더한다
등비	aₙ = r·aₙ₋₁	일정하게 곱한다
피보나치	aₙ = aₙ₋₁ + aₙ₋₂	앞의 둘을 더한다
하노이	aₙ = 2aₙ₋₁ + 1	—

규칙 한 줄이 수열 전체를 정한다

왜 유용한가

많은 문제가 "한 단계 줄이면 같은 문제" 이기 때문입니다.

문제	줄이면
원반 n개 하노이	원반 n−1개 하노이 × 2
n개 정렬	n/2 개 정렬 × 2 + 합치기

알고리즘의 비용이 점화식으로 나온다 — 그래서 배운다

비유 — 러시아 인형

인형을 열면 똑같이 생긴 작은 인형이 나옵니다.

—	—
"n번째 인형의 무게"	= "n−1번째 무게" + 껍데기

전체를 몰라도 한 겹의 관계만 알면 된다

점화식 = 재귀 함수. 한 줄씩 그대로 옮겨집니다.

Python 브라우저에서 실행

# 점화식을 그대로 코드로 옮기면 재귀 함수가 됩니다
def 피보(n):
    if n <= 2:            # 기초
        return 1
    return 피보(n - 1) + 피보(n - 2)      # 점화

for n in range(1, 13):
    print(f"F({n:>2}) = {피보(n)}")

🎮 점화식 계산기

시작값과 규칙을 바꿔 가며 수열이 어떻게 자라는지 보세요. 재귀로 계산할 때 몇 번을 호출하는지도 세어 줍니다 — 같은 값을 몇 번이나 다시 계산하는지 보면 놀랄 거예요.

고등학생그대로 재귀로 짜면 느립니다

note 의 이 경고가 중요한 실전 교훈입니다.

피보나치를 그대로 재귀로 짜면 — 지수 시간

왜 그런가

fib(5) 를 계산하려면 fib(4) 와 fib(3) 이 필요합니다. 그런데 fib(4) 도 fib(3) 을 부르죠.

호출	fib(3) 을 계산한 횟수
fib(5)	2번
fib(10)	수십 번
fib(40)	수억 번 ⚠

같은 것을 몇 번이고 다시 계산한다

숫자로

n	호출 횟수	시간
10	177	즉시
40	3억	수십 초
50	400억	몇 시간

약 1.6ⁿ 으로 늘어난다 — 황금비다

해결 — 기억해 둔다

메모 = {}
def fib(n):
    if n in 메모: return 메모[n]     # ← 한 줄
    ...

방식	fib(40)
그냥 재귀	3억 번
메모이제이션	40번 ✔

한 줄로 3억 배 빨라진다 — 계산한 것을 버리지 않으니까

비유 — 계산 과정 적어 두기

방식	—
매번 처음부터	같은 계산을 되풀이
공책에 적어 둔다	보면 된다 ✔

공간을 써서 시간을 산다 — /ca 8강의 캐시와 같은 발상

n을 30, 32로 올려 보세요. 차이가 폭발합니다.

Python 브라우저에서 실행

# 계산 횟수를 직접 세어 봅니다
호출 = {"단순": 0, "메모": 0}

def 단순(n):
    호출["단순"] += 1
    return 1 if n <= 2 else 단순(n - 1) + 단순(n - 2)

기억 = {}
def 메모(n):
    호출["메모"] += 1
    if n <= 2: return 1
    if n in 기억: return 기억[n]
    기억[n] = 메모(n - 1) + 메모(n - 2)
    return 기억[n]

n = 25
print(f"F({n}) = {단순(n)}  · 단순 재귀 호출 {호출['단순']:,}번")
print(f"F({n}) = {메모(n)}  · 기억하며 호출 {호출['메모']:,}번")
print(f"→ {호출['단순'] // max(호출['메모'], 1):,}배 차이")

하노이 탑 — 점화식이 답을 알려 줍니다

원반 n개를 옮기려면 몇 번 움직여야 할까요? 생각해 보면 이렇습니다.

위의 n−1개를 보조 기둥으로 옮긴다 … T(n−1)번
가장 큰 원반을 목표로 옮긴다 … 1번
보조 기둥의 n−1개를 목표로 옮긴다 … T(n−1)번

T(n) = 2·T(n−1) + 1, T(1) = 1

이 점화식을 풀면 T(n) = 2ⁿ − 1 입니다. 원반이 하나 늘 때마다 시간이 두 배가 돼요. 64개짜리 전설의 탑은 5,800억 년이 걸립니다.

점화식 하나로 5,800억 년을 계산했습니다.

Python 브라우저에서 실행

def 하노이(n): return 1 if n == 1 else 2 * 하노이(n - 1) + 1

print(" n | 점화식 계산 | 2^n - 1 | 1초에 1번씩 옮기면")
print("-" * 52)
for n in (1, 3, 5, 10, 20, 40, 64):
    t = 하노이(n) if n <= 20 else 2 ** n - 1
    초 = t
    if 초 < 60:            기간 = f"{초}초"
    elif 초 < 86400:       기간 = f"{초/3600:.1f}시간"
    elif 초 < 31536000:    기간 = f"{초/86400:.0f}일"
    else:                  기간 = f"{초/31536000:,.0f}년"
    print(f"{n:>2} |{t:>12,} |{2**n - 1:>8,} | {기간}")

고등학생자주 나오는 점화식과 그 정체

note 의 표를 알고리즘과 이어 봅시다.

점화식	답	어느 알고리즘
T(n) = T(n−1) + 1	O(n)	선형 탐색
T(n) = T(n/2) + 1	O(log n)	이진 탐색 ⭐
T(n) = 2T(n/2) + n	O(n log n)	병합 정렬 ⭐
T(n) = T(n−1) + n	O(n²)	선택 정렬
T(n) = 2T(n−1) + 1	O(2ⁿ)	하노이 ⚠

점화식의 모양만 봐도 알고리즘의 비용을 안다

두 가지를 구별하세요

줄이는 방식	결과
n → n−1 (빼기)	느리다 — n 또는 2ⁿ
n → n/2 (나누기)	빠르다 — log n

"하나씩 줄이기" 와 "절반씩 줄이기" 가 운명을 가른다

왜 그렇게 다른가

방식	1이 되기까지
−1 씩	n 번
÷2 씩	log₂ n 번

100만이면 100만 번 vs 20번입니다.

이게 /ds 16강의 log 의 마법이다

앞의 계수도 중요합니다

점화식	답
T(n) = 1T(n/2) + n	O(n)
T(n) = 2T(n/2) + n	O(n log n)
T(n) = 4T(n/2) + n	O(n²)

몇 조각으로 나누느냐가 차수를 바꾼다 — 마스터 정리

같은 n인데 결과의 자릿수가 완전히 다릅니다.

Python 브라우저에서 실행

# 점화식이 만드는 성장 속도를 나란히 비교
import math
print(f"{'n':>4}{'n':>8}{'log n':>8}{'n log n':>10}{'2^n':>16}")
print("-" * 48)
for n in (2, 4, 8, 16, 32, 64):
    print(f"{n:>4}{n:>8}{math.log2(n):>8.0f}{n * math.log2(n):>10.0f}{2**n:>16,}")
print()
print("2^n 열만 봐도 왜 '지수 시간'이 무서운지 알 수 있습니다.")

고등학생꼭 기억하세요

12강의 정리와 실전 감각입니다.

점화식 = 시작값 + 넘기는 규칙

점화식을 푸는 세 방법

방법	설명
펼쳐 보기	몇 항을 써 보고 패턴을 찾는다
추측하고 귀납	답을 짐작하고 11강으로 확인 ⭐
공식 (마스터 정리)	모양이 맞으면 바로

두 번째가 정석이다 — 11강과 12강이 짝을 이룬다

하노이 탑의 무서움

T(n) = 2T(n−1) + 1 → 2ⁿ − 1

원반	이동 횟수	1초에 한 번이면
10	1,023	17분
20	약 100만	12일
64	약 1800경	5800억 년 ⚠

전설의 64개 원반은 우주 나이보다 오래 걸린다

그리고 실전 교훈

신호	의미
점화식에 2T(n−1) 이 있다	지수 — 큰 입력에 못 쓴다 ⚠
T(n/2) 가 있다	로그가 낀다 — 좋다 ✔

알고리즘을 짜기 전에 점화식을 세워 보면 — 헛수고를 막는다

코드를 다 짜고 너무 느리다는 걸 발견하는 것보다 종이에서 미리 아는 게 낫죠.

🤔 확인 문제

a(1) = 2, a(n) = 3·a(n−1) 일 때 a(4) 는?

해설 2 → 6 → 18 → 54 입니다. 일반항으로는 a(n) = 2·3ⁿ⁻¹ 이고 2 × 27 = 54. 이렇게 일정 배수로 커지는 점화식을 등비수열이라 합니다.

🤔 확인 문제

하노이 탑의 점화식 T(n) = 2T(n−1) + 1 이 뜻하는 것은?

해설 앞의 n−1개를 두 번 옮겨야 하므로 대략 두 배씩 커집니다 (2ⁿ−1). 이런 지수적 증가는 n이 조금만 커져도 감당할 수 없게 돼요.

🤔 확인 문제

단순 재귀로 짠 피보나치가 느린 이유는?

해설 F(30)을 구하는 동안 F(10)을 수만 번 다시 계산합니다. 한 번 구한 값을 적어 두면(메모이제이션) 호출 수가 n에 비례하게 줄어들어요 — 답은 같고 방법만 바꾼 겁니다.