Project Euler #2

Project Euler #2

---

• 문제
  
  • 풀이 1
  • 풀이 2
  • 번외
• 후기

문제

---

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.

피보나치 수열은 직전 두 항의 합이 된다. 1과 2로 시작하는 경우 최초 10항까지는 아래와 같다.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
피보나치 수열에서 4백만 이하의 짝수인 항의 총합은?

풀이 1

---

• while로는 루핑시켜서 값을 구했다.(노가다)

#-*- coding: utf-8 -*-
import time
i = j = 1 #최초 시작 항을 초기화 한다.
total = 0 #총 합은 0으로 초기화 한다.
fibon = [] #짝수인 수열의 항을 저장할 리스트 자료형.
stime = time.time()

while j < 4000000:
    i, j = j, i+j
    if j % 2 == 0:
        total += j
        fibon.append(j)

print(total, fibon)
print(time.time() - stime)

풀이 2

---

• Generator(생성기)를 이용한 풀이도 있다.

def fibo_gen(max):
    i, j = 1, 1
    while j < max:
        yield j
        i,j = j, i + j

stime = time.time()
print(sum(x for x in fibo_gen(4000000) if x % 2 == 0))
print(time.time() - stime)

번외

---

• 피보나치 수열은 아래와 같이 정의 된다.
  $$F_{n} = \begin{cases} n, & \text{if }n < 2 \\ F_{n-1} + F_{n-2}, & \text{if }n \geqq 2 \end{cases}$$
• 해당을 함수로 구현하면 아래와 같다.(재귀함수로 구현된다.)

def fibo_sq(n):
    if n < 2:
        return n
    return fibo_sq(n-1) + fibo_sq(n-2) #재귀함수로 수행된다.(위의 식을 구현한 부분)

• 풀이 2처럼 생성기를 이용한 구현도 가능하다.
• 생성기라 해당 n번째까지의 수열을 모두 출력한다.

def fibo_gen(terms):
    i, j = 1, 1
    term = 1
    while term <= terms:
        term += 1
        yield i
        i,j = j, i + j

후기

2번 문제 역시 난도가 높지는 않다. 특별히 설명할 부분이 없는 것 같다.
생성기를 이용한 풀이는 앞으로도 유용하게 사용할 수 있을 것으로 보인다.