03. 토끼의 번식: 피보나치 수열과 DP 엔진

1. 학습 목표 (Learning Objectives)

• 이전 두 항이 합쳐져 다음 항을 탄생시키는 3단 릴레이 점화식인 피보나치(Fibonacci) 수열 의 패턴 구조를 익힙니다.
• 재귀 함수로 피보나치를 짤 경우 발생하는 최악의 중복 연산 병목 참사와, 이를 메모리 저장소 기반 다이내믹 프로그래밍(DP) 방어벽으로 회피하는 최적화 파이썬 스크립트를 체감합니다.

2. 과거 2대가 합쳐져 1대를 창조한다

수학에서 가장 성스럽게 여겨지는 점화식 체계, 13세기 수학자 레오나르도 피보나치가 ‘갓 태어난 토끼 한 쌍이 달마다 낳는 새끼 토끼 번식량’을 연구하다가 세상에 공개해버린 공식입니다.

[피보나치 수열의 점화식] $\mathbf{a_{n+2} = a_{n+1} + a_n} \quad (단, a_1 = 1, a_2 = 1)$ “전 항과 전전항, 뒤의 2개 숫자를 모조리 더해야만 나의 다음 모습이 렌더링 된다!”

수열 전개: $1, 1, 2, 3, 5, 8, 13, 21, 34 …$ 꽃잎의 개수, 솔방울의 나선 모양 구도, 태풍 소용돌이 형태 우주 은하계 등 대자연을 관장하는 신비한 프랙탈 증가 구조의 뼈대입니다.

3. 재귀 함수의 파멸적 버그 폭발 ($Fib(40)$ 의 악몽)

앞서 팩토리얼을 구현했던 것처럼 파이썬으로 “내 자신을 부르고 또 내 자신을 2번 더 부르자!”라는 재귀 함수로 피보나치 수열 40번째 항을 돌려보겠습니다. 결과는 참혹합니다.

• $Fib(5)$ 를 구하려면 컴파일러는 $Fib(4)$ 와 $Fib(3)$ 를 따로따로 동시에 불러야 합니다.
• 근데 $Fib(4)$ 는 또 자기 안에서 $Fib(3)$ 과 $Fib(2)$ 를 또 찢어서 동시에 부릅니다.
• 어라? 컴파일러는 방금 $Fib(3)$ 처리를 해놓고서, 다른 가지에서 똑같은 계산인 $Fib(3)$ 를 아무 뇌 없이 또 쌩판 처음부터 재기동 연산 합니다!!

나무뿌리처럼 수천만 개의 연산 복제가 일어나고 컴퓨터는 과부하 렉에 걸려 뻗어버립니다. (시간 복잡도 $O(2^n)$ 지수 폭발).

4. 다이내믹 프로그래밍 (DP: Memoization) 해결사!

천재 해커들과 수학자들은 এই 중복 연산 지옥을 막기 위해 다이내믹 프로그래밍(Dynamic Programming), 그중에서도 ‘메모이제이션(Memoization, 메모하기)’ 이라는 기적의 룰을 만들었습니다.

[DP 메모이제이션 해킹 법칙] “한 번 계산해 낸 피보나치 항의 결과는 무조건 별도의 딕셔너리 창고(캐시/Cache) 에 적어둔다. 다음번에 함수가 또 그 똑같은 녀석을 부르면? 처음부터 무식하게 연산 나무뿌리로 들어가지 말고, 그냥 창고에 적혀있던 값을 순식간에 읽어와서 던져버리고 루프를 강제 탈출 시켜버린다!”

5. 파이썬 피보나치 엔진 (재귀 vs DP 속도 비교)

얼마나 드라마틱하게 스피드가 차이 나는지 파이썬 코드 시뮬레이터로 극강의 대비를 체험해 봅시다!

import time

# ---------------------------------------------------------
# [엔진 A]: 최악의 효율, 우직한 단순 재귀 피보나치
# (똑같은 f(n) 계산을 백만 번씩 중복해서 멍청하게 반복함)
# ---------------------------------------------------------
def fib_naive_recursive(n):
    if n <= 2:
        return 1
    # 좌우 뿌리를 갈라가며 우후죽순 연쇄 폭발
    return fib_naive_recursive(n - 1) + fib_naive_recursive(n - 2)

# ---------------------------------------------------------
# [엔진 B]: 스마트 캐싱, 다이내믹 프로그래밍(DP) 방어벽 탑재 피보나치
# ---------------------------------------------------------
# 딕셔너리 창고 (1번 항과 2번 항은 미리 1이라고 적어두자)
memoization_cache = {1: 1, 2: 1}

def fib_dp_memoization(n):
    # 1. 묻지도 따지지도 않고, 내 캐시 창고에 이 계산 결괏값이 이미 있는지 훑어본다.
    if n in memoization_cache:
        # 오우! 옛날에 계산해 둔 게 기록돼 있네? 창고 값 바로 토해내고 뒤도 안 돌아보고 함수 강제 탈출!!
        return memoization_cache[n]
        
    # 2. 창고에 처음 보는 값이면? 
    # 눈물을 머금고 한 번은 하위 재귀 연산을 때려서 정답을 만든 뒤,
    fresh_result = fib_dp_memoization(n - 1) + fib_dp_memoization(n - 2)
    
    # 3. [핵심 방어력] 바로 그 값을 모른 척하지 않고 내 캐시 창고 딕셔너리에 평생 기록해 둔다! (다음엔 0.0001초컷)
    memoization_cache[n] = fresh_result
    return fresh_result

# =========== 시뮬레이션 =============
target_term = 35 # 35번째 피보나치수열 렌더링

print("🔴 [엔진 A 가동] 바보 같은 순수 재귀 함수 (무한 중복 연산의 늪)")
start_time = time.time()
ans_A = fib_naive_recursive(target_term)
end_time = time.time()
print(f"   결과 팩트: {ans_A} / 연산 딜레이 스톱워치: {end_time - start_time:.4f} 초 걸림 🥵")


print("\n🟢 [엔진 B 가동] DP 메모이제이션 탑재형 최적화 엔진")
start_time = time.time()
ans_B = fib_dp_memoization(target_term)
end_time = time.time()
print(f"   결과 팩트: {ans_B} / 연산 딜레이 스톱워치: {end_time - start_time:.6f} 초 컷!! ⚡🚀")

터미널 실행 콘솔 렌더링:

🔴 [엔진 A 가동] 바보 같은 순수 재귀 함수 (무한 중복 연산의 늪)
   결과 팩트: 9227465 / 연산 딜레이 스톱워치: 2.1852 초 걸림 🥵

🟢 [엔진 B 가동] DP 메모이제이션 탑재형 최적화 엔진
   결과 팩트: 9227465 / 연산 딜레이 스톱워치: 0.000034 초 컷!! ⚡🚀

단순 재귀 엔진A는 컴퓨터 CPU가 터질 듯이 불타며 2.1초나 걸렸지만, 캐시 메모리 창고 기술(DP)을 탑재한 엔진B는 불과 0.00003초 만에 계산을 끝내버렸습니다. 무려 6만 배나 빠른 시간 복잡도($O(n)$) 기적을 창조한 것입니다. 점화식과 재귀의 치명적 독은 DP로 해독해야 한다는 컴퓨터 과학의 철상(Iron Rule)입니다.

6. 학습 정리 (Summary)

1. 피보나치 수열 식: 앞의 2개 항을 합병시켜 다음 항을 뽑아내는, 자연의 황금비율이 녹아 있는 2중 점화식입니다.
2. 다이내믹 프로그래밍(DP) 최적화의 진수: 똑같은 점화식 수열 함수라 할지라도, 한 번 수고스럽게 계산된 하위 블록의 답을 캐시 메모리에 ‘기록장’ 삼아 덮어두었다가 읽어오는 메모이제이션(Memoization) 스킬 하나만 코드에 박으면 CPU의 중복 덧셈 스파이럴(지연)을 완전히 격파하고 빛처럼 빠른 엔진을 구축할 수 있습니다.