2. Even Fibonacci numbers

https://projecteuler.net/problem=2

Problem 2 - Project Euler

 

문제는 다음과 같습니다.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 

피보나치 수열의 숫자 중, 4백만을 넘지않는 짝수의 합을 구하라는 문제입니다. 대학교의 어느 과목에서 배웠는지는 잘 기억나않습니다만(알고리즘이었던가, 자료구조였던가...) 재귀함수를 배울때에 팩토리얼과 같이 예시로 자주 쓰이는 문제입니다. 그 당시에는 순열의 길이가 길지 않아서 재귀함수로 구현을 하여도 괜찮았을 것입니다.

 

 

하지만, 재귀함수의 특성상, 하나의 재귀함수를 호출하였을 경우, 그 안에서 재귀함수를 호출하는 횟수가 많아질수록 메모리를 많이 잡아먹고, 일반적인 반복문보다 성능이 떨어집니다. 이유는 OS의 함수 호출 과정을 따로 공부해 보는 것으로 확인할 수 있을 것입니다. (물론 단점만 있다는 것은 아닙니다. 일반적인 반복문보다 코드 길이가 짧아질 경우가 많은것 등등이 있습니다.)

 

저는 brute force 방식으로 구현을 하였었습니다. 두 개의 변수를 이용하여 피보나치 순열을 계산합니다. 하나의 변수의 값이 짝수인지를 확인하며, 짝수일 경우, 그 숫자를 더해나가는 방식입니다. 코드는 다음과 같습니다.

# num1 : fib(n-2)
# num2 : fib(n-1)
# temp : use for swap
# pSum : sum of even fib num
num1=1
num2=2
temp=0
pSum=0

while (num1 < 4000000 and num2 < 40000000) :
    if num2 % 2 == 0 :
        pSum += num2
    temp=num1
    num1=num2
    num2+=temp

print(pSum)

 

피보나치 수열의 공식은 다음과 같습니다.

    fib(n) = fib(n-1) + fib(n-2)

그러므로 fib(n-2)를 나타내는 num2에 fib(n-1)을 나타내는 num1을 더한 값은 fib(n)이 됩니다. 그리고, fib(n-2) = num1, fib(n-1) = num2를 유지하기 위하여 temp변수를 이용합니다.

 

위의 코드에서 약간이나마 코드 길이를 조금 더 줄이려면 다음과 같이 할 수 있습니다.

num = [1, 1]
pSum = 0;
i = 0

while num[i] < 4000000 :
    i = (i + 1) % 2
    num[i] += num[(i+1) % 2]
    if num[i] % 2 == 0 :
        pSum += num[i]

print(pSum)

projecteuler, Python, 알고리즘