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, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
피보나치 수열 구하는 문제입니다. 4백만 이하의 짝수인 피보나치 수열을 더해라는 거죠. 피보나치 수열만 구한다면야 쉽게 할 수 있을 것 같습니다. 고등학교 수학 시간에 수열을 배우면서 가장 까다로운 수열 중 하나로 피보나치 수열을 배웠던 것 같습니다. 일반항이 좀 복잡했었죠. 하지만, 그렇게까지 할 필요는 없을테고, 루프를 돌면서 수열을 구하면 될 것 같습니다.
생각해보니 recursion을 배울 때도, dynamic programming을 배울 때도, 피보나치 수열을 구하는 것을 예제로 했었네요.
아래 코드는 recursion을 쓰는 방법입니다만, 두 가지 이유에서 사용할 수 없습니다. 첫번째 문제는 Stack Overflow가 있겠고, 두번째 문제는 비효율적이라는 거죠.
def f( n: Int ): Int = {
if (n == 0) 0
else if (n == 1) 1
else f(n-1) + f(n-2)
}
그렇다면 dynamic programming 단원에서 배운 방법으로 약간 최적화 해보는 건 어떨까요?
val fibonacciNumbers = new scala.collection.mutable.HashMap[Int,Long]
fibonacciNumbers(1) = 1
fibonacciNumbers(2) = 2
def f( n: Int ): Long = {
fibonacciNumbers.get(n) match {
case None => {
val fv = f(n-1) + f(n-2)
fibonacciNumbers(n) = fv
fv
}
case x => x.get
}
}
하지만, 이 경우에도 Stack Overflow가 발생하는 문제는 어쩔 수 없습니다. 자꾸 Stack Overflow라고 하니까 tail call 최적화가 생각이 나네요. 그런데, 재귀 호출을 한 번만 하면 괜찮겠는데, 두 번 해서 합을 구해야 하니까, 얼핏 생각해보면 잘 안될 것 같습니다. 하지만, 손으로 풀어보면 이런 식으로 변형이 되는데요. 이걸 보니까 아이디어가 떠오릅니다.
f(n) = f(n-1) + f(n-2) = (f(n-2) + f(n-3)) + f(n-2) = 2*f(n-2) + f(n-3)
a*f(n) + b*f(n-1) = a*(f(n-1)+f(n-2)) + b*f(n-1) = (a+b)*f(n-1) + a*f(n-2)
프로그램으로 짜보면
def sumOfTwoFn( n: Int, a: Long, b: Long ): Long = {
if (n == 3) {
2 * a + 1 * b
} else {
sumOfTwoFn( n-1, a + b, a)
}
}
def f( n: Int ): Long = {
n match {
case 1 => 1
case 2 => 2
case _ => sumOfTwoFn( n, 1, 1)
}
}
빠르고 좋긴 한데, 문제를 다시 한 번 읽어보면, 범위 내에 있는 수열 중에서 조건을 만족하는 놈들의 합을 구해야 하니까, 범위 내의 모든 피보나치 수열을 구해야 합니다. 그럼 위의 방법은 비효율적이죠.
그냥 이전 것과 이전 이전 것만 알면, 현재 값을 구할 수 있다는 수열의 성질을 이용하면, 효율적으로 범위 내의 피보나치 수열을 구할 수 있겠습니다. generator를 한 번 만들어보죠.
class FibonacciIterator extends Iterator[Int] {
var a = 0
var b = 1
def hasNext: Boolean = true
def next: Int = {
val c = a + b
a = b
b = c
c
}
}
이 피보나치 수열 생성기를 이용하면, 문제는 다음과 같이 간단히 해결됩니다.
val f1 = new FibonacciIterator
val ans1 = f1.takeWhile( _ < 4000000).filter( _ % 2 == 0).reduceLeft[Int](_+_)
println(ans1)
