Python 예제 - 프로젝트 오일러 2번 문제 (피보나치 수열)

이번 포스팅에서는 프로젝트 오일러 2번 문제를 코드로 구현해보겠다.

 

문제는 아래와 같다.

 

Q. 400만 이하의 피보나치 수열에서 짝수들의 합을 구하시오.

 

먼저, 저번 포스팅에서 구현해 본 'n번째 피보나치 숫자 구하기' 코드를 사용하여 이 문제를 구현해보자.

 

코드는 아래와 같다.

 

def func(n):
    if n==0:
        result = 1
    elif n==1:
        result = 1
    else:
        result = func(n-1) + func(n-2)
    return result

i = 0
sum = 0

while(1):
    if func(i)<=4000000:
        if func(i)%2==0:
            sum+=func(i)
    else:
        break
    i += 1

print("Sum is ",sum)

먼저 저번 포스팅에서 구현했던 func() 함수를 사용하였다.

 

while 문을 사용하여 피보나치 숫자를 처음부터 400만 미만의 숫자까지 모두 구한 뒤, 짝수인 경우에만 sum이라는 변수에 더해가는 방식이다.

 

위 코드의 경우 제대로 실행은 되지만 한가지 큰 문제점이 있다.

 

매 단계 (i가 1씩 증가하는 단계) 마다 func() 함수를 실행하기 때문에 피보나치 수열을 처음부터 계산한다.

 

따라서 위 코드를 직접 실행해보면 마치 컴퓨터가 멈춘게 아닌가 싶을 정도로 반응이 없을 것이다.

 

(하지만 오랜 시간 뒤에 결과는 나오게 된다.)

 

결과적으로 위 코드는 결코 좋은 코드라고 볼 수 없다.

 

우리가 원하는 건 400만 이하의 피보나치 숫자들 중 짝수인 숫자들이기 때문에, 위와 같이 매 단계마다 피보나치 수열을 일일이 구할 필요가 없다.

 

아래와 같은 새 코드를 작성해보았다.

 

a = 1
b = 1
c = a + b
sum = 0

while (c<4000000):
    if c%2==0:
        sum+=c
    a = b
    b = c
    c = a+b

print("Sum is ",sum)

위 코드에서는 우선 피보나치 수열을 구하는 함수가 삭제되었다.

 

a와 b 변수에 피보나치 수열의 초기 2개 값을 저장하고, c 변수에는 3번째 피보나치 숫자를 초기 값으로 저장하였다.

 

각 변수들은 매 단계마다 한 스텝 다음의 피보나치 숫자를 저장하는 방식이다.

 

매 루프마다 계산된 c 값이 짝수인 경우에만 sum 변수에 더하도록 구현하였다.

 

이렇게 작성하게 되면 짝수가 아닌 경우는 지나치고 다음 단계로 넘어가기 때문에 훨씬 더 효율적으로 답을 구할 수 있게 된다.

 

결과는 아래와 같이 나온다.

 

이처럼 하나의 문제를 해결하는 데에는 다양한 방식으로 코드를 구현할 수 있다.

 

다만 여러 방식들 중 가장 효율적인 코드를 구현하는 것을 최종 목표로 하는 것이 좋다.