오일러 프로젝트의 두 번째 문제는 4백만 이하의 피보나치 수열 중에서 짝수인 항을 모두 더한 합을 구하는 문제이다.
피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다
. (1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...)
짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?
접근
피보나치 수열은 직전 두 항의 합이 바로 그 다음 항이 되는 수열이며, 독특한 성질을 많이 가지고 있기 때문에 교과 과정 내에서도 몇 번 언급된다. 두 개의 항이 계산에 사용되기 때문에 첫 두 항의 값은 고정되어야 한다.
a_n = a_{n-2} + a_{n-1} (a_1 = 1, a_2 = 2) 피보나치 수열은 문제마다 시작행이 약간 달라지기도 한다. 0, 1 로 시작하거나 1, 1로 시작할 수도 있다. 어쨌든 피보나치 수열의 일반항은 이 점화식으로부터 재귀 함수 형태의 꼴로 간단하게 구현할 수 있다.
def fib(n:int) -> int:
if n < 3:
return n
return fib(n - 2) + fib(n - 1)
for i in range(40):
print(fib(i + 1))문제는 구현은 간단하지만, 이 함수의 시간복잡도는 지수적이기 때문에, n이 커질수록 급격하게 느려진다는 문제가 있다. 위 예제에서 40번째까지의 항을 출력하게 했지만, 갈수록 느려지면서 35번째 이상부터는 아주 느리게 값을 출력하게 된다. 그러므로 메모이제이션이나 다른 구현을 사용해서 계산하도록 하는 것이 맞다.
다른 구현
피보나치 수열의 일반항을 구하기 위해서는 이전 두 항의 값을 알고 있어야 한다. 점화식의 정의에서도 첫 두 항이 정의된다. 즉, 연속한 두 개의 항을 하나의 순서쌍(tuple)으로 표현한다면, 다음 순서쌍을 계속 계산해낼 수 있다. 예를 들어 피보나치 수열의 연속된 두 항이 a, b 일 때 이를 (a, b) 라고 표현한다면, 다음 항과 그 다음항의 정보는 (b, a + b)로 표현할 수 있을 것이다. 이렇게 현재항과 다음항의 값을 두 개의 변수로 두고 이를 앞에서부터 누적해서 쌓아나가면 빠르게 n 번째 항을 계산할 수 있다.
def fib(n: int) -> int:
a, b = 1, 2
for _ in range(n):
a, b = b, a + b
return a제너레이터
위 예제 함수 fib(n)은 n 번째 피보나치 수열의 항을 찾는 함수인데, 이 문제에서는 피보나치 수열의 항을 앞에서부터 얻으면 된다. 이렇게 특정한 규칙에 의해 생성되는 원소들은 제너레이터를 사용하는 것이 일반적이다. 제너레이터는 보통함수와 달리 실행 흐름을 중간에 멈출 수 있는 함수라고 생각하면 된다. (다른 언어에서는 ‘코루틴(coroutine)’이라고 표현하기도 한다) 피보나치 수열은 제너레이터를 사용하기에 딱 좋은 예라 할 수 있다.
제너레이터를 만드는 함수를 제너레이터 함수라 하는데, 제너레이터 함수는 return 대신에 yield 구문을 사용하는 것으로 간단하게 작성할 수 있다. 하나의 함수가 한 번만 리턴하는 것이 아니라 yield 구문에서마다 값을 리턴하고 일시정지한다고 이해하면 된다.
def fibs():
a, b = 1, 2
while True:
yield a
a, b = b, a + b
# !!! 아래 코드는 무한루프입니다.
for x in fibs():
print(x)이 제너레이터를 약간 변형하여 4백만 이하인 경우까지만 루프를 돌도록 하고, 만들어진 값 중에서 짝수만 골라내어 합산하면 된다.
def fibs():
a, b = 1, 2
while a <= 400_0000:
if a % 2 == 0:
yield a
a, b = b, a + b
print(sum(fibs()))피보나치 수열에 대한 생각
피보나치 수열은 아주 간단한 공식만 가지고, 극도로 성능이 딸리는 함수를 만들어낼 수 있는 좋은 예시이다. 게다가 수열이 급격히 증가하는 특징 때문에 실제로 간단한 덧셈이지만, 손으로 계산하는 것은 물론 컴퓨터를 계산하는 방법에서도 금방 한계에 부딪히기 쉬워서 코딩 관련된 문제에 단골로 등장하는 소재이다.
피보나치 수열은 오래전부터 많은 수학자들이 연구하기 좋아하는 주제였다. 그래서 몇 가지 흥미로운 사실들이 알려져 있다
- 피보나치 수열의 이웃한 두 항의 비율은 황금비 ( 1 + √5 ) / 2 에 수렴한다.
- 그리고 이 성질을 이용해서 일반항을 계산할 수 있는 생성함수가 밝혀져 있다.
- 연속한 피보나치 수열의 두 개의 항은 서로 소이다.
- n 번째 항까지의 피보나치 수열의 합은 n + 2 번째의 피보나치 수열의 항 – 1 과 같다.
- 두 항의 값을 증가시켜서 계산을 반복하는 방식은 행렬로 표현하면 매우 빠르게 큰 n 번째 피보나치 수열을 계산하는 방법으로 활용할 수 있다.
황금비를 ɸ, 1-ɸ를 ɸ’ 이라 하면, 피보나치 수열의 일반항은 다음과 같이 계산된다.
F_n = \frac{(\phi^{n} - \phi^{\prime n})}{\phi - \phi^{\prime}}