안녕하세요? 사이냅소프트입니다.

이번 포스팅에서는 "피보나치 수"에 관한 Project Euler 문제를 풀어보려고 합니다.


> 프로젝트오일러 x 줄리아

> 피보나치 (#2, #25)

> 약수

> 직각삼각형

> 맺으며


피보나치 수에 대해서는 많은 분들이 알고 계실텐데요, 먼저 2번 문제를 한번 보겠습니다.


프로젝트오일러 [문제 2]


피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.


1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...


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


중세 시대의 수학자인 피보나치가 원래 고민한 문제는 이런 것이었다고 합니다.

  • 처음에 한 쌍의 토끼가 있으면, 1년 뒤에는 몇 마리로 불어나 있을까?
  • 여기서 토끼 한 쌍은 1달 걸려 한 쌍의 새끼를 낳고,
  • 새끼들은 1달 있으면 번식 가능하게 된다고 가정.


토끼 우리의 처음 몇 달을 그려보면 이렇습니다. (♣는 번식 가능, 는 아직 불가능)

세어 보면 전체 토끼 수가 정말 1, 2, 3, 5, 8... 처럼 늘어나고 있네요.



또, 가만히 보면 각 단계에서 번식 가능한 토끼의 수() 역시 1, 1, 2, 3, 5 처럼 늘어나고.

새로 태어난 토끼()는 0, 1, 1, 2, 3 처럼 늘어납니다.

저번 달의 번식 가능한 토끼 숫자만큼 이번 달에 새로운 토끼가 더 태어나게 되니, 앞 항을 지금 항에 더해서 다음 항이 만들어지는 셈이지요.


위 문제에서는 1, 2, 3, 5, ... 로 시작하고 있지만, 이 수열은 1, 1, 2, 3, ... 또는 0, 1, 1, 2, 3, ... 처럼 쓰기도 합니다. 어떻게 시작하든지 별 차이는 없고, "바로 앞의 항 두 개를 더한 것이 다음 항"이라는 원칙은 유지됩니다.

이제 이 수열의 n번째 항을 F(n)으로 표시하면, 2번 문제에 대해서는 다음과 같이 쓸 수 있습니다.

  • F(1) = 1
  • F(2) = 2
  • F(n) = F(n-1) + F(n-2)     ... n>2일 때


문제를 풀려면 F(n) 값을 4백만이 될 때까지 구해 가면서 짝수인 경우를 모두 더하면 되겠네요.

이건 너무 쉬워 보입니다. 그대로 코드로 옮겨도 될 듯합니다. (예외처리는 편의상 생략합니다)


function F(n)

    if n == 1

        return 1

    elseif n == 2

        return 2

    else

        return F(n-1) + F(n-2)

    end

end


function prob2()

    i = 1

    s = 0

    while true

        f = F(i)

        if f > 4000000

            return s

        end

        if f % 2 == 0

            s += f

        end

        i += 1

    end

end

 

왼쪽의 F(n) 함수는 피보나치 수열의 정의를 그대로 옮겨놓은 것입니다.


n이 1, 2일 때는 정해진 값을 돌려주고, 그 외의 경우에는 앞의 두 항을 더해서 돌려줍니다.


그리고 prob2 함수는 F(n)을 이용해서 2번 문제를 계산합니다.


i = 1로 시작해서 F(i)를 계속 구해가며, 짝수인 F(i) 값들을 4백만 이하일 동안 s 값에다 쌓아갑니다.

 

  << 잠깐! Julia 문법 >>

  • 함수는 function ... end 로 만듭니다.
  • if 문은 if ... elseif ... else ... end 
  • while 문은 while ... end 꼴입니다.
  • if 나 while 의 조건절에 괄호는 없어도 됩니다.
  • Python처럼 들여쓰기가 의미를 가지지는 않습니다.

이제 이 코드를 fib1.jl 이라는 파일로 저장하고 Julia에서 실행... 4613732 라는 값이 찍힙니다. 정답~


julia> include("fib1.jl")
prob2 (generic function with 1 method)

julia> prob2()
4613732


곧이곧대로 F(n)함수를 만들었긴 하지만 피보나치 수를 아주 간단히 구할 수 있습니다.

이제 피보나치 관련 문제는 다 풀 수 있게 된 것일까요?

 . . .

혹시 모르니까 속도 체크를 한번 해보기로 합니다.

F(5)를 해보니 8이 잘 나옵니다. F(12)는 233이군요.  F(50)은 ... 어라??


julia> F(5)

8


julia> F(12)

233


julia> F(50)

^CERROR: InterruptException:

 in F at fib1.jl:9 (repeats 37 times)


아무리 기다려도 답이 나오질 않습니다. 할 수 없이 Ctrl-C로 중단시킵니다.

왜 답이 나오지 않는 것일까요? 50이 너무 숫자가 커서? 겨우 50인데?


Julia에서 제공하는 @time 매크로를 가지고, n 값을 바꿔가면서 함수 호출 시간을 재어 봅니다.


julia> @time F(12)

  0.000007 seconds (4 allocations: 160 bytes)

233


julia> @time F(30)

  0.005971 seconds (5 allocations: 176 bytes)

1346269


julia> @time F(40)

  0.719258 seconds (5 allocations: 176 bytes)

165580141


julia> @time F(45)

  7.905292 seconds (5 allocations: 176 bytes)

1836311903


이런, n 값이 커지면서 뭔가 시간이 급격히 증가하기 시작했습니다. 이 지경이니 50까지 갈 수도 없었던 모양이네요. 뭐가 잘못됐을까요?


F(7)을 위와 같은 방법으로 계산할 때, 어떤 식으로 호출이 일어나는지 한번 보겠습니다.


F(7) = F(6) + F(5)

      = (F(5) + F(4)) + (F(4) + F(3))

      = ((F(4) + F(3)) + (F(3) + F(2))) + ((F(3) + F(2)) + (F(2) + F(1)))

      = ... 이하 생략 ...


가만 보면 F(4), F(3) 같은 함수의 호출이 계속 반복되는 것을 알 수 있습니다.

사실 이런 값들은 한번만 계산해두면 되는데, 재귀 호출이 일어날 때마다 늘 다시 계산을 하니 n 값이 커지면서 아랫 단계의 함수 호출도 무지막지하게 늘어나고... 속도도 급격히 떨어지게 되는 거죠.


이 속도 문제를 어떻게 풀까요?

한번 계산해둔 값은 어딘가 저장해두면 되지 않을까요?


자, 그럼 memo 라는 이름의 Dict (저번 포스팅에 나왔죠) 를 하나 만들고,

거기에 한번 계산한 F(n) 값들을 기억시켜두기로 합니다. 초기값으로 F(1)과 F(2)를 넣어두고요.


코드에서는 F(n) 함수만 바뀌면 됩니다.

haskey(memo, n) 는 memo라는 Dict에 n이라는 키 값이 들어있는지 - 즉 F(n)을 이전에 한번 계산했었는지 알기 위함입니다. 만약 그렇지 않다면 memo[n] 에다가 새로운 값을 계산해서 기억해두는거죠.

이제 실행시켜 보겠습니다.


memo = Dict( 1=>1, 2=>2 )


function F(n)

    if haskey(memo, n) == false

        memo[n] = F(n-1) + F(n-2)

    end

    return memo[n]

end


function prob2()

    i = 1

    s = 0

    while true

        f = F(i)

        if f > 4000000

            return s

        end

        if f % 2 == 0

            s += f

        end

        i += 1

    end

end

 

julia> prob2()

4613732

julia> @time F(30)
  0.000008 seconds (5 allocations: 176 bytes)
1346269

julia> @time F(40)
  0.000013 seconds (26 allocations: 512 bytes)
165580141

julia> @time F(45)
  0.000050 seconds (26 allocations: 5.016 KB)
1836311903

julia> @time F(50)
  0.000013 seconds (20 allocations: 416 bytes)
20365011074

julia> @time F(100)
  0.000031 seconds (155 allocations: 2.516 KB)
1298777728820984005

오호.. F(50)은 물론 F(100)까지도 순식간에 계산되어 나옵니다.
중간 계산값을 기억해뒀을 뿐인데 엄청난 차이가 나네요.
이런 기법을 memoization 또는 dynamic programming이라 부른다고 합니다. 관심있는 분은 인터넷에 자료가 많으니 한번 검색해보세요.

이제 실행 시간이 아주 향상되긴 했지만, 문제의 간단함에 비해 코드가 여전히 좀 길어 보인다는 느낌적인 느낌이 드는 것은 왜일까요? ...


사실, 피보나치 수를 꼭 F(n)의 형태로 구할 필요는 없습니다.

앞의 두 수를 더한다는 원칙만 지켜진다면 말이죠.

변수 두 개를 써서 피보나치 수를 계산해가는 방법이 아래 그림에 있습니다.

F(n) 대신에 a, b 변수에다가 중간 값을 기억해두면서 전진해가는 모양새입니다.


처음에 a, b는 각각 1, 2라는 초기값을 가지고 있습니다.

이제 다음 항의 값인 a+b 를 b에 넣습니다. 그리고 원래 b의 값은 다음번의 a가 됩니다.


Python이나 Julia처럼 임시 변수를 쓰지 않아도 되는 경우라면, 간단히

  a, b = b, a+b 

처럼 해서 새로운 변수 값을 설정할 수 있습니다.

그럼 이 방법으로 2번 문제를 다시 풀어볼까요.


function prob2()

    a, b, s = 1, 2, 0

    while b <= 4000000

        iseven(b) && (s += b)

        a, b = b, a+b

    end

    return s

end

 

 << 잠깐! Julia 문법 >>


Julia에서는 조건문 대신에 X && Y 형태를 사용하는 경우가 종종 있습니다. (short-circuit evaluation)


X && Y 앞의 조건 X가 참일 때만 뒤의 Y값이 계산되므로,

iseven(b) && (s += b) 처럼 쓴 부분은


if iseven(b)

    s += b

end

와 같습니다. 이 때 += 보다 &&가 우선순위가 높으므로, 대입문은 괄호로 한번 싸줍니다.


코드가 많이 짧아지긴 했지만, 별로 어려운 부분은 없습니다.

우선 a, b에다가 1, 2의 초기값을 주고,

s는 구할 값을 더해가는 용도이므로 0으로 둡니다.

수열의 "현재 항"은 b가 가지고 있으므로, b <= 400만일 동안 반복합니다.


반복문 내의 iseven() 함수는 짝수인지 판별하는 내장함수입니다. (modulo 연산 (%) 대신에 써봤습니다)

b가 짝수이면 우리가 찾는 항이므로 결과값 s에다가 b값을 더합니다.

그리고 다음 항으로 전진... 위에서 설명한대로 a, b 값을 재조정합니다.

어떤가요? 그런대로 괜찮아 보이죠.


2번 문제는 이 정도로 충분한 것 같습니다. 이제 25번 문제를 풀어보고 포스팅을 마무리하겠습니다.


프로젝트오일러 [문제 25]


피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

Fn = Fn-1 + Fn-2  (단, F1 = 1, F2 = 1).

이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
. . .
F11 = 89
F12 = 144

수열의 값은 F12에서 처음으로 3자리가 됩니다.

피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?


이번에는 좀 많이 큰 값을 다루어야 하는 모양입니다. 1000자리 숫자라니...

게다가 아까 재귀호출 방식으로 F(n)을 구할 때 memoization을 적용했던 것이 여기서는 필수적이 되어 버렸습니다.


32비트나 64비트 범위를 넘어서는 큰 수를 다루는 방법은 몇 가지가 있겠지만, 뭐니뭐니해도 Python처럼 언어 자체에서 큰 수의 연산 기능을 제공해주면 제일 편하겠죠. 그리고 Java라면 BigInteger, C언어는 GNU MP라이브러리 같은 방법을 쓸 수 있습니다.


Julia에서도 BigInt라는 자료형이 있어서 큰 정수의 연산을 쉽게 할 수 있습니다. 위에서 만든 코드 중 F(n) 값에 해당하는 부분만 그 타입으로 바꾸면 문제 없습니다. 아, 그리고 초기값이 1, 2가 아니라 1, 1로 바뀌어야 하겠군요.


아래에 두 가지 방법으로 25번 문제를 풀어보았습니다.

여기서 ndigits() 는 어떤 수의 자리수를 돌려주는 Julia 내장함수입니다.

log 함수 등으로 직접 계산할 수도 있겠지만, 기본 제공이 아무래도 편하지요.


memo = Dict( 1=>BigInt(1), 2=>BigInt(1) )


function F(n)

    if haskey(memo, n) == false

        memo[n] = F(n-1) + F(n-2)

    end

    return memo[n]

end


function prob25()

    i = 1

    while ndigits(F(i)) < 1000

        i += 1

    end

    return i

end

 

function prob25()

    a, b, n = BigInt(1), BigInt(1), 2

    while ndigits(b) < 1000

        a, b = b, a+b

        n += 1

    end

    return n

end


소요 시간은 두 프로그램 모두 0.01초 이내입니다. 속도는 항상 중요하니까요...


자, 그럼 다음 시간에는 약수(factor)에 관련된 내용으로 찾아뵙겠습니다.

즐거운 문제 풀이 되세요 !~


사이냅소프트 2016 경력직 공채

www.synapsoft.co.kr/jsp/recruit/16.html


Posted by Synapsoft