오일러 프로젝트의 두 번째 문제는 4백만 이하의 피보나치 수열 중에서 짝수인 항을 모두 더한 합을 구하는 문제이다.
피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다
. (1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...)
짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?
접근
피보나치 수열은 직전 두 항의 합이 바로 그 다음 항이 되는 수열이며, 독특한 성질을 많이 가지고 있기 때문에 교과 과정 내에서도 몇 번 언급된다. 두 개의 항이 계산에 사용되기 때문에 첫 두 항의 값은 고정되어야 한다.
문제에서는 1, 2, 3, 5, ... 와 같이 첫 두 항이 1, 2 인 형태를 사용했다. 문제에서 몇 번째 항을 구하라던지 항 번호에 관계된 문제를 다루게 되는 경우에는 첫 두 항이 어떻게 되는지에 대해서 잘 알아둘 필요가 있다.
간단한 로직
이전 항 2개를 저장하는 변수 2개만 있으면 피보나치 수열의 N 항은 1항부터 세어서 찾을 수 있다. 피보나치 수열을 무한 출력하는 코드는 파이썬으로는 다음과 같이 작성된다. 특히 파이썬의 튜플 언패킹을 이용하면 두 변수의 값을 교환하는 등의 코드가 매우 간단해지므로 교환을 위한 중간 변수가 필요없다.
a, b = 0, 1
while True:
a, b = b, a + 1
print(a)따라서 종료 조건 (a 가 4백만 보다 커짐)을 추가하여 짝수인 피보나치 항을 합산해나가면 간단히 풀리는 문제. 4백만번째 항이 아닌 4백만 이하의 항에 대해서만 계산하므로 생각보다 짧게 끝난다.
def p002():
a, b, s = 0, 1, 0
while a <= 400_0000:
if a % 2 is 0:
s += a
a, b = b, a + b
print(a)
%time p002()제너레이터
피보나치 수열을 반복문으로 계산하는 것외에 처리할 수 있는 다른 방법으로는 제너레이터를 들 수 있다. 특히 점화식을 알고 있는 수열이라면 제너레이터를 활용하기에 좋은 예가 될 수 있다. 특히 파이썬에서는 제너레이터가 for ... in 구문에 사용될 수 있으므로 (혹은 리스트 축약) 다음과 같이 풀 수 있다.
def fib():
a, b = 0, 1
while a <= 400_0000:
yield a
a, b = b, a + b
print(sum(x for x in fib() if x % 2 is 0)놀랍게도 루프를 도는 것보다 제너레이터를 사용하는 방식이 좀 더 빠르기까지 하다.
Swift의 제너레이터
Swift에도 제너레이터가 있다. 파이썬의 시퀀스와 비슷하게, Sequence 타입은 generate() 라는 메소드를 가지고 있는데, 이 메소드는 제너레이터 타입의 객체를 리턴한다. 제너레이터는 IteratorProtocol 이라는 프로토콜을 따르는데 (원래는 GeneratorType 이었다가, Swift3에서 이름이 바뀌었다.) 이는 next() -> T? 라는 메소드를 정의해야 한다. 참고로 Swift의 시퀀스는 그 자체가 제너레이터 일 수 있다. 역시 파이썬의 제너레이터와 같은 기법으로 다음과 같이 코드를 작성할 수 있다.
struct Fibonacci : Sequence, IteratorType {
// 그 자신이 IteratorType이 되는 것 만으로 Sequence 타입이 될 수 있다.
var a = 0
var b = 1
mutating func next() -> Int? {
guard a <= 400_0000 else { return nil }
(a, b) = (b, a + b)
return a
}
}
print(Fibonacci().filter{ $0 % 2 == 0 }.reduce(0, +))좀 더 다른 접근법
피보나치 수열의 첫 두 항을 1, 2 이라고 하자. 이는 홀수와 짝수로 구성되어 있다. 이후 항들은 다음 중 하나의 경우에 해당될 것이다.
- 홀수 + 짝수 = 홀수
- 짝수 + 홀수 = 홀수
- 홀수 + 홀수 = 짝수
그리고 위 3가지 패턴이 계속해서 반복된다. 따라서, 0, 1, 1, 2, 3, 5, 8, … 등으로 이어지며 3번마다 한 번씩 짝수가 된다. 첫 두 항을 a, b 라 하고 (이 때 a는짝수이고 b는 홀수) 피보나치 수열의 값을 찾아보면
(a, b) # (0, 1) 피보나치 수열의 1항은 1번 튜플의 첫째 요소이다. (b, a+b) # (1, 1) (a+b, a+b+b) (1, 2) (a+b+b, a+a+b+b+b) (2, 3) ...
(a, b) 가 다음 번 짝수항이 되려면 (a+2b, 2a + 3b) 가 되는 시점이다. 따라서 중간에 홀수인 항을 제외하고 짝수인 항만 찾고자 한다면 이를 점화식으로 사용하면 된다.
def fast_fib():
a, b = 0, 1
while a <= 400_0000:
yield a
a, b = (a+b+b, a+a+b+b+b)
print(sum(fast_fib()))근데 막상 이렇게 해봐도 원래 했던 로직보다 특별히 빨라지지는 않는 것 같다.
그 외
어떤 수열의 점화식으로 해당 수열의 일반항을 구하려는 경우에, 점화식을 그대로 써서 재귀함수를 작성하게 되는 경우가 많다. 피보나치 수열의 일반항은 2개의 앞 항을 참조하고 있기 때문에 재귀 함수 형태로 일반항을 구하려는 경우에 쓸데없는 중복계산을 너무 많이해서 매우 비효율적인 동작을 하게되기 때문에 메모이제이션이나 동적 계획법과 같은 테크닉을 적용한다.
참고 글