이전 두 개의 수를 더해서 새로운 수를 하나 만들어 수열을 이루면 그것을 피보나치 수열이라 한다.

4백만을 넘지 않는 피보나치 수열 중 짝수들의 합을 구하면?

풀이 #1

#!/usr/bin/env python3

MAX=4000000

fibonacci = [1, 1]

while True:
    result = fibonacci[-1] + fibonacci[-2]
    if result > MAX: break
    fibonacci.append(result)

r = [x for x in fibonacci if x % 2 == 0]
print(sum(r))

기본적으로 결과가 4백만을 넘지 않을때까지 피보나치 수열을 만들고, 이를 다시 리스트 표현식을 사용해 짝수로 필터링한다. 그리고 합을 구한다.

fibonacci[-1], fibonacci[-2]를 더한 결과를 fibonacci에 append하면, fibonacci를 매번 새로 계산할 필요도 없다. 그저 마지막 요소 두 개를 더하기만 하면 된다. 특히 파이썬에서는 음수 인덱스를 통해 리스트의 “마지막 요소"에 접근할 수 있으므로, 매우 간단하게 피보나치 수열을 계산할 수 있다.

최대한 저장해놓고 계산을 피하면서 문제를 해결하는 방식을 Dynamic Programming, 동적 계획법이라고 부른다. 사실 매우 간단해서 거창하게 무슨 동적 계획이니 이럴거까지는 아니지만.

풀이 #2

#!/usr/bin/env python3

MAX=4000000

even_sum = 0
x, y = 1, 1

def sumof(x, y):
    return (x + y, y) if x <= y else (x, x + y)

def is_even(n):
    return n % 2 == 0

while True:
    x, y = sumof(x, y)
    if max(x, y) > MAX: break
    if is_even(max(x, y)): even_sum = even_sum + max(x, y)

리스트와 리스트 표현식을 쓰지 않고서는 이렇게 만들 수 있다. 두 수의 합으로 만드는 새로운 피보나치 값이 짝수라면 바로 even_sum에 계속 더해나가는 식으로 계산하면 된다.

어쨌든 필요한 결과는 “짝수 피보나치의 합"이고, 이는 피보나치 수가 짝수일 때 더해서 만드는 수다. 따라서 임시 변수 x, y를 지정해서 피보나치 수를 저장하고 이게 짝수일 때만 even_sum에 계속 더해나간다.

간략한 코드를 위해 Conditional Expression을 사용하였다.