프로젝트 오일러 2번 (Julia)

프로젝트 오일러 2번 풀이

피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?

피보나치 수열을 구현하기 위한 방법은 많이 있다. 흔히 재귀적으로 특정항을 구하는 방법이 있지만, 이는 지수적인 시간복잡도를 갖기 때문에 이 문제에는 적용할 수 없다. 다행히 '바로 앞 항 두개를 더한다'는 계산으로 피보나치 수열을 앞에서부터 계산하는 것은 간단하다. A, A+1 항의 값을 가지고 있을 때, A+1, A+2 항의 값을 계산하는 것은 (A+1항, A항 + A+1항)으로 계산되기 때문에 단순한 반복문으로 계산할 수 있다.

참고로 계산된 항이 짝수인 경우, if 문을 사용해서 결과값에 더해야하기 때문에 다음과 같은 코드를 쓸 것이다.

if a % 2 == 0
    s += a
end

if 문의 블럭에 단순한 표현식만 들어간다면, 이는 short circuit을 사용할 수 있다. 대입문의 경우에 괄호로 감싸면 그 자체로 표현식으로 간주되므로, 다음과 같이 줄여 쓸 수 있다.

a % 2 == 0 && (s += a)

즉 && 의 좌변을 평가하여 참이라면 우변의 표현식이 평가되면서 합산이 일어난다. 참고로 함수의 호출이나, break, return 과 같은 흐름제어 키워드들도 줄리아에서는 표현식으로 간주된다.

최종 코드는 다음과 같이 만들어진다.

let (a, b) = (1, 1)
    s = 0
    while a <= 400_0000
        a % 2 == 0 && (s += a)
        a, b = b, a + b
    end
    println(s)
end

피보나치 수열과 같이 점화식으로 생성되는 수열을 앞에서부터 만들때에는 코루틴(제너레이터)을 사용하는 방식을 고려할 수 있다. 코루틴은 채널(Channel)이라는 객체를 통해서 다른 코루틴과 통신한다. 즉 외부로부터 다음 피보나치 항을 요청받을 때 마다 계산해서 만들어주는 방식으로 동작한다고 생각하면 된다.

코루틴은 통신을 위한 Channel 객체의 생성자에, 제너레이터 함수를 넣어주면 된다. 제너레이터 함수는 return 대신에 put!(채널, 값) 함수를 사용하여 외부의 요청에 응답할 수 있다.

fibs = Channel() do c
    a, b = 1, 1
    while true
        a, b = b, a+b
        put!(c, a)
    end
end

let s = 0
    while true
        f = take!(fibs)
        f > 400_0000 && break
        f % 2 == 0 && (s += f)
    end
    println(s)
end

흥미로운 점은 이렇게 코루틴을 이용한 풀이가 while 루프만 사용했을때보다 훨씬 빠르게 동작한다는 점이다.