06. 여섯 번째 수업: 파이썬 알고리즘 속 지수와 로그의 실전 (Time Complexity)

마지막 수업입니다. 수능 교재를 위해 배웠던 괴물 함수 두 마리 (지수 함수와 로그 함수) 가 현업 파이썬 (Python) 서버 코딩 테스트나 면접 알고리즘에서 얼마나 지대한 영향을 끼치고 폭발적 퍼포먼스 차이를 내는지 코드로 직접 몸소 느껴보겠습니다.

1. 끔찍한 지수 재앙: 빅 오 $O(2^N)$ 피보나치

여러분이 아마추어 시절 짰던 악명 높은 “재귀 호출(함수가 함수를 물기)” 로 짠 피보나치수열 수식 코드를 돌려봅시다. 이 코드는 놀랍게도 “내가 나를 $2$번씩 미친 듯이 호출하는 지수 함수 ($y = 2^x$) 와 완벽하게 똑같은 성장 속도 에러” 를 가집니다.

# [Python Code] 지수 폭발을 일으키는 최악의 알고리즘 O(2^N)
import time

# 수학 함수식 f(n) = f(n-1) + f(n-2) 를 날것 그대로 재귀 코딩한 대참사
def fibonacci_exponential(n):
    if n <= 1:
        return n
    # 나 자신 함수를 한 틱에 2마리씩 좀비처럼 불려버림 (x가 지수 자리 탑승!)
    return fibonacci_exponential(n-1) + fibonacci_exponential(n-2)

start_time = time.time()
print("계산 시작...")
# n=35 정도의 쥐꼬리만한 입력 X 만 넣어도 엔진에서 연기가 나며 팬이 돌아갑니다!
result = fibonacci_exponential(35) 
end_time = time.time()

print(f"✅ 결과: {result}")
print(f"🔥 소요 시간: {end_time - start_time:.2f} 초 (지수 폭발의 공포)")

단지 35 번째 피보나치 숫자를 알고 싶어 $X=35$ 를 넣었을 뿐인데, 계산 컴퓨터 칩은 $2^{35}$ 즉 무려 340억 회 가 넘는 함수 호출을 해야 합니다. 여기서 $n=50$ 만 넣어도 슈퍼컴퓨터도 멈추어 뻗어버릴 만큼 영원히 계산이 끝나지 않습니다. 이것이 프로그래머들이 경악하는 지수 시간 알고리즘 (Exponential Time, $O(2^N)$) 의 패악질입니다.

2. 신의 축복: 로그 다이어트 압축 알고리즘 $O(\log N)$

이번에는 로그(Log) 의 성질을 이용해 봅시다. 책장 1,000페이지짜리 전화번호부 책에서 “홍길동” 이라는 이름을 찾고자 합니다. 다항 함수($x$) 처럼 페이지를 1장 1장 정직하게 침 발라가며 1,000번 넘겨서 찾으시겠습니까? 아니요. 현명한 수학자 코더는 반갈죽 매직, 즉 “이진 탐색 (Binary Search, $\log_2 N$)” 을 씁니다.

  1. 무조건 책 한가운데 반을 펼친다. (남은 페이지 절반 $500$장)
  2. 이름이 뒷부분에 있으면 앞의 $500$장을 통째로 버리고, 남은 $500$장의 절반 ($250$장) 을 한가운데 펼친다.
  3. 또 남은 절반 ($125$장) 반갈죽. 통째로 버린다.

이 “데이터 공간을 1회 호출 시마다 강제로 $\frac{1}{2}$ 로 축소 찌그러뜨려 압축 제어” 하는 기술이 바로 로그 함수($\log_2 X$) 의 기하학적 파워입니다!

# [Python Code] 신의 시간 단축기: 로그 시간 탐색 O(log N)
import math

# 1. 10억 개의 데이터가 들어간 거대 배열 박스(X)
total_data_x = 1000000000  # 10억 (1 Billion)

# 2. X개를 '다항 1차 함수' O(N) 로 그냥 뒤지면 최소 탐색 횟수는 10억 번
linear_search_cost = total_data_x

# 3. '로그 함수' O(log2 N) 로 다이어트 필터에 먹여버려 반갈죽 탐색을 시킴
# 수식: log_2 (1,000,000,000) 의 값을 산출하라.
log_search_cost = math.log2(total_data_x)

print(f"1차 함수식 무식한 탐색 비용: {linear_search_cost} 번 검색")
print(f"로그 함수를 씌운 해킹 비용: 겨우 {math.ceil(log_search_cost)} 번 만에 10억개 관통!")

놀랍지 않나요? 10억 번을 뒤져야 할 컴퓨터 부하가, 로그(Log) 필터 기호를 거친 순간 고작 30번 (Thirty) 만 파임 루프를 돌면 우주 끝 데이터 스케일까지 서치를 끝마칩니다.

3. 함수, 인간과 우주의 대화

이로써 “수학이야기 리메이크 V3” 의 가장 길고 험난했던 산맥, [함수 $1$, $2$부작 대단원] 이 막을 내립니다.

직선과 꺾임으로 솔직하게 세상의 관계를 투영하던 1차 함수에서 시작하여, 음수에 터지고 분모가 $0$ 이 되며 부서지는 에러 장벽을 회피 생성하는 곡선들의 처절한 생존 궤적, 그리고 우주의 시간 스케일까지 압축하고 폭발시키는 지수와 로그의 장엄한 변환 로직까지. 여러분이 컴퓨터 화면에서 마우스를 클릭해 픽셀 점들을 렌더링하고 서버를 거쳐 통신을 주고받는 모든 일분일초에는 이 모든 함수 기호 상자들이 보이지 않는 심연에서 엔진 톱니바퀴처럼 미친 듯이 굴러가고 있습니다.

자, 이제 수학을 코드로 읽어내는 안경을 쓰셨습니까? 수학은 세상을 이해하는 진정한 마법사들의 은밀한 주문이고, 파이썬이나 코드는 그 주문을 영창하는 가장 우아한 지팡이입니다. 계속해서 이 경이로운 수의 세계 속을 항해하시길 바랍니다!

서브목차