프로젝트 오일러 002

피보나치 수열의 일반항

4백만까지의 피보나치 수열을 모두 구하고 그 중에 짝수인 것을 합하면 됩니다. 피보나치 수열을 처음 두 개의 항이 주어지고, 그 다음 항은 앞 2개의 항의 합으로 만들어집니다. 피보나치 수열의 일반항을 구하는 함수를 나이브하게 작성해보겠습니다.

def fibonacci(n: int) -> int:
  assert n > 0
  if n < 2:
    return n + 1
  return fibonacci(n - 2) + fibonacci(n - 1)

말 그래도 '이전 2개 항의 값의 합'을 찾도록 했습니다. 그리고 이 함수를 아래와 같이 테스트해보죠.

for i in range(1, 50):
  print(f"{i:02d} {fibonacci(i)}")

이 코드는 항의 번호와 그 항의 값들을 차례로 출력합니다. 그리고 예상하시겠지만, 30번대 정도부터 천천히 출력되다가 어느 순간 멈춘 것처럼 오래 걸리게 됩니다. 이 코드는 쓸데없는 연산을 계속해서 반복하기 때문에, 이 문제를 푸는데는 어울리지 않습니다.

튜닝 : 메모이제이션

사실 피보나치 수열과 관련된 문제를 접해본 사람이라면, '이건 이전 계산 값을 미리 저장해놓고 계산하면 시간을 극적으로 줄일 수 있지'라고 생각할 수도 있습니다. 물론이죠! 아래와 같이 어떤 함수에서 계산한 결과를 입력과 결과의 쌍으로 저장했다가, 다음 번에 같은 값이 전달되면 계산하지 않고 캐시된 값을 바로 돌려주는 함수를 작성해보겠습니다.

from functools import wraps
from typing import Callable


def memoize[T, U](f: Callable[[T], U]) -> Callable[[T], U]:
    cache: dict[T, U] = {}

    @wraps(f)
    def inner(a: T) -> U:
        if a in cache:
            return cache[a]
        r = f(a)
        cache[a] = r
        return r

    return inner

이렇게 한 번 계산한 결과를 캐싱해두는 기법을 '메모이제이션'이라고 하는데, 이를 적용하면 한 번 계산된 피보나치 항은 불필요하게 재계산하지 않기 때문에 아주 빠르게 작동합니다. 아, memoize 함수는 데코레이터로 사용하도록 작성되었기 때문에, 기존의 코드 윗줄에 아래와 같이 적용해주기만 하면 됩니다.

@memoize
def fibonacci(n: int) -> int:
  ....

이제 문제를 풀어볼까요?

result = 0
n = 0
fib = 0
while fib <= 400_0000:
  if fib % 2 == 0:
    result += fib
  n, fib = n + 1, fib(n + 1)
print(result)
    

다른 접근

그런데 이 문제는 사실 피보나치 수열의 일반항과는 별 관련이 없습니다. 두 개의 숫자가 있다면 다음 항은 얼마든지 계속 만들어 나갈 수가 있기 때문이죠. 1, 2 두 개의 값에서 2, 3을 만들고, 다시 3, 5를 만들어 나가는 식으로 다음 항을 만들 수만 있다면 간단히 풀 수 있습니다.

a, b = 1, 2
result = 0
while b <= 400_0000:
  if b % 2 == 0:
    result += b
  a, b = b, a + b

print(result)

이 간단한 while 루프에서 a, b = b, a + b 가 피보나치 수열의 두 항으로 다음 항을 계속 만들어나가는 식이 됩니다. 이 루프를 이용해서 제너레이터를 만든다면 아래와 같이 풀이할 수도 있습니다.

def fibs():
    a, b = 0, 1
    while True:
        if b % 2 == 0:
          yield b
        a, b = b, a + b
        if b > 400_0000:
            break

print(sum(fibs()))

이유는 알 수 없지만, 그냥 while루프를 도는 것보다, 제너레이터를 사용한 풀이가 거의 완전히 똑같은 로직임에도 불구하고 조금 더 빠릅니다.