프로젝트 오일러: 짝수 피보나치 수열의 합
이전 두 개의 수를 더해서 새로운 수를 하나 만들어 수열을 이루면 그것을 피보나치 수열이라 한다.
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을 사용하였다.