프로젝트 오일러 002

4백만 이하의 피보나치 수 중에서 짝수인 것의 합

피보나치 수열은 수열의 앞 두 수의 합으로 전개되는 수열입니다. 0과 1로부터 시작한다면 [0, 1, 1, 2, 3, 5, ..] 이렇게 마지막 항과 그 직전항을 더하면 다음항이 되는, 간단한 점화식으로 표현할 수 있는 수열이지만, 여러 흥미로운 성질을 가지고 있고, 특히 프로그래밍 문제와 관련해서도 시사점이 많습니다. 이 문제는 피보나치 수열이 진행하면서 4백만보다 작은 범위에서 짝수인 것의 합계를 구하는 것입니다.

피보나치 수열의 점화식은 매우 간단하고, 점화식이 간단하다는 것은 쉽게 구현할 수 있다는 것입니다. 점화식은 ‘n번째 항’을 구하는 함수로 두면, ‘f(n)‘과 같은 식으로 구현할 수 있습니다. 대부분 점화식으로 정의되는 수열은 재귀적인 방법을 통해서 코드로 작성할 수 있습니다. 그런데 문제는 피보나치 수열의 일반항을 재귀로 구현하면 성능의 함정에 빠지게 된다는 것입니다. 피보나치 수열의 일반항을 구하는 코드는 다음과 같습니다.

def f(n):
    if n < 3:
        return n - 1
    return f(n-2) + f(n-1)

처음 스무개의 피보나치 수열을 출력해보면 다음과 같습니다.

print([f(i + 1) for i in range(20)])
# [0,  1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  144,  233,  377,  610,  987,  1597,  2584,  4181]

하지만 35번대쯤의 일반항을 구하려는 시점부터는 매우 느려지기 시작합니다. 피보나치 점화식은 이전 수열과 그 이전 수열을 각각 구해야 하기 때문에 두 번으로 나눠지는 이전항 계산을 해야하고, 각각의 이전항 계산에서도 같은 식으로 두 번의 계산 경로를 진행해야 합니다. 결국 35번째 항을 계산하기 위해서는 수십업번에 해당하는 함수 호출이 필요하고 너무나 느려집니다. 이 느려지는 문제를 해결하는 방법은 이전 결과를 계산해두는, ‘메모이제이션’이 있습니다. 메모이제이션은 반복되는 계산의 결과를 기억해두고 재계산을 피하는 것으로 성능을 높이는 방법인데, 여기서는 일단 다음에 다뤄보는 것으로 하고 문제 자체의 집중하는 다른 접근을 채택해보기로 합니다.

피보나치 수열을 생성하기

문제를 푸는 과정에서 피보나치 수열의 n번째 항을 찾고, 그 수가 짝수인지 판단해서 결과에 누적하여 더하는 일을 하기 위해, ‘피보나치 수열 일반항’을 구하는 함수가 필요한데, 이 함수가 극악의 퍼포먼스를 보이기 때문에 갑자기 쉬운 문제가 아니게 되었습니다. 하지만 다른 측면으로 이 문제를 바라 봅시다. 이전 항과, 그 앞 항을 기억해두어야 할 때, 그냥 리스트 같은 곳에 순서대로 있으면 찾기 편하지 않을까요? 아니, 아예 4백만 이하의 피보나치 수의 배열을 가지고 있다면 이 문제는 엄청 간단한 거 아닐까요?

피보나치 수는 N이 커짐에 따라 기하급수적으로 값이 커지게 됩니다. 위의 20개의 예시에서도 알 수 있지만 거의 두 배씩 커지고 있다고 볼 수 있습니다. 이정도면 4백만까지는 금방 도달하기 때문에, 실제로 4백만 이하의 피보나치 수는 몇 개 안될 것이라고 추측할 수 있습니다. 초기값 0, 1을 각 각의 변수에 두고 각각을 다음 수와 두 수의 합으로 바꿔나가면 피보나치 수열을 만들어나갈 수 있습니다. 반복문을 사용해서 반복의 특정 위치에서 값을 검사하고 합산하는 방법이 고전적인 C 언어 식의 문제 풀이 방식입니다. 그러나 파이썬은 제너레이터라는 좀 더 우아한 기법이 있기 때문에 이 방식으로 문제를 풀어볼 것입니다. 여러가지 문제를 풀다보면 값을 변경하기 전에 누적합계 변수에 더해야하는지 이런 것들을 매번 속으로 생각하는 것이 귀찮아서 이 방식을 선호합니다.

def fib(limit=400_0000):
    a, b = 0, 1
    while a < limit:
        yield a
        a, b = b, a + b

print(sum(x for x in fib() if x % 2 == 0))

피보나치 수열에서 짝수가 나타나는 패턴 살펴보기

문제를 해결하기는 했지만, 피보나치 수열에서 짝수가 나타나는 패턴을 더 살펴보겠습니다. 피보나치 수열을 이웃한 항을 더해서 다음 항을 만듭니다. 그리고 홀수와 짝수의 덧셈에서는 다음과 같은 규칙이 있습니다.

• 짝수 + 홀수 = 홀수
• 홀수 + 홀수 = 짝수

피보나치 수열이 0, 1의 (짝, 홀)로 시작되기 때문에 (짝, 홀, 홀, 짝, 홀, 홀, 짝,…)과 같은 패턴이 반복됩니다. 즉, 피보나치 수열에서 짝수는 3번째마다 한 번씩 나타납니다. 또한 짝수 피보나치 수열을 만들면 묘한 규칙을 찾을 수 있는데요, 짝수 피보나치 수열은, $Fe(n)=4\cdot Fe(n-1)+Fe(n-2)$의 점화식을 갖습니다.

그래서 이 성질을 적용하기 위해서는 위 코드에서 살짝만 손을 보면 됩니다.

def fib_even(limit=400_0000):
    a, b = 0, 2
    while a < limit:
        yield a
        a, b = b, a + b * 4
        
print(sum(fib_even()))

피보나치의 일반항

피보나치 수열에 대해서는 몇 가지 재미있는 사실들이 밝혀진 것들이 있습니다.

1. N이 충분히 크다면 이웃한 피보나치 수 두 개의 비율은 황금비에 가까워집니다.
2. 피보나치 수는 n이 충분히 크다면 황금비의 거듭제고에 비례하여 증가합니다.
3. 그래서 황금비를 이용하면 피보나치 수열의 일반항을 계산할 수 있습니다.

피보나치 수열의 일반항을 계산하는 공식을 ‘비네의 공식’이라고 하며, 이는 다음과 같이 구합니다. (단 이 때 계산되는 수열은 1, 1을 시작으로 하기 때문에 우리가 지금까지 사용한 0, 1로 시작하는 수열과는 약간 다릅니다.)

이를 코드로 표현하면 아래와 같습니다.

sf = 5 ** 0.5
phi = (1 + sf) / 2
phi_ = (1 - sf) /2

def fib_v(k: int) -> int:
    return int((phi ** (k-1) - phi_ ** (k-1)) / sf)

print([fib_v(i+1) for i in range(40)])