13. 피보나치수열의 컴퓨터 과학적 응용과 파이썬 (Python)

1. 학습 목표 (Learning Objectives)

• 수열의 점화식 원리를 컴퓨터 과학(CS)의 알고리즘 기법인 ‘동적 계획법(Dynamic Programming)’으로 승화시켜 봅니다.
• 중복되는 연산을 피하고 엄청난 스피드로 피보나치 천 단위 항을 계산해내는 파이썬(Python) 최적화 코드를 체험합니다.

2. 컴퓨터를 괴롭히는 순진한 수식의 맹점

이전 챕터에서 우리는 수식을 1:1로 복사한 재귀함수(Recursion)에 대해 가볍게 다뤄보았습니다.

\[F(n) = F(n-1) + F(n-2)\]

이를 곧바로 구현한 코드가 있었습니다.

def fib(n):
    if n <= 2: return 1
    return fib(n-1) + fib(n-2)

이 코드가 5번째 항인 fib(5)를 풀기 위해 컴퓨터 머릿속에서 일어나는 일을 나열해보면:

1. fib(5)는 fib(4)와 fib(3)을 달라고 요청합니다.
2. fib(4)는 다시 fib(3)과 fib(2)를 달라고 요청합니다.
3. 아까 fib(5)가 불렀던 fib(3)은 따로 또 fib(2)와 fib(1)을 요청합니다…

숫자 하나를 도출하기 위해 컴퓨터 백그라운드에서는 똑같은 연산(fib(3), fib(2) 등)을 수십 수백 번 중복해서 다시 계산하며 엄청난 나무(스택 트리)를 그려야 합니다. 만약 50번째 달의 토끼 수를 세라고 fib(50)을 치면, 데스크탑 컴퓨터 팬이 미친듯이 돌아가며 수십 분을 멍하니 멈춰있는 현상(시간복잡도 $O(2^n)$의 저주)을 맛보게 됩니다.

3. 동적 계획법 (Dynamic Programming)

프로그래머들은 이 무식한 중복 연산을 혐오합니다. 그래서 ‘기억력 보조장치’를 덧붙이는 획기적 아이디어를 냈습니다. “한 번 고생해서 구한 피보나치 숫자는 공책(리스트나 사전)에 메모해 두고, 나중에 누군가 또 물어보면 계산하지 말고 메모장(Cache)에서 즉시 꺼내 주자!”

이것을 컴퓨터 공학에서는 메모이제이션(Memoization) 또는 큰 덩어리를 잘개 쪼개고 저장해 푸는 동적 계획법(DP)이라고 부릅니다.

# 공책(메모장) 역할을 할 딕셔너리를 바깥에 마련해 둡니다.
memo = {1: 1, 2: 1} # 1번째와 2번째 달은 1이라는 걸 미리 적어둠

def fib_DP(n):
    # 1. 앗! 공책(memo)에 이미 적혀있는 번호(n)라면?
    if n in memo:
        return memo[n] # 계산하지 않고 메모장을 열어서 바로 정답을 뱉음!
        
    # 2. 공책에 없다면, 어쩔 수 없이 단 한번만 수학 점화식 계산을 수행
    result = fib_DP(n-1) + fib_DP(n-2)
    
    # 계산된 뜨끈뜨끈한 정답을 나중을 위해 재빨리 공책(memo)에 적어둡니다
    memo[n] = result
    return result

# 동적 계획법 캐시의 무서운 스피드 체험!!
# 옛날 방식이면 우주가 멸망할 때까지 계산못할 100번째 토끼의 쌍 수도 단숨에 호출합니다.
print("100번째 피보나치 수:", fib_DP(100))
# 출력: 100번째 피보나치 수: 354224848179261915075

이 10여 줄의 메모리 저장 코드를 하나 추가한 것만으로, 시간복잡도는 $O(N)$ 으로 수조 배 단축되어 0.0001초 만에 3542해(垓)라는 기하급수적인 토끼 수를 단숨에 구출해 냅니다.

4. 학습 정리 (Summary)

1. 재귀의 저주: 수식을 그대로 코드 구조에 복사하는 것은 보기엔 예쁘지만 컴퓨터의 구조적 한계(중복 스택 반복 연산)로 무참히 박살납니다.
2. 동적 계획법 (Dynamic Programming): 한 번 연산한 결과는 무조건 캐싱(메모이제이션)하여 재활용하는 알고리즘 최적화의 꽃입니다.
3. 수학 공식에 프로그래머의 기지와 자료구조 응용력이 합쳐질 때, 세상을 바꿀 초고속 인공지능과 슈퍼컴퓨터 성능이 탄생하는 것입니다.