[기획 연재] 수학과 프로그래밍 – 피보나치 수
안녕하세요? 사이냅소프트입니다.
이번 포스팅에서는 “피보나치 수”에 관한 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 문법 >>
|
이제 이 코드를 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)은 … 어라??
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(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 경력직 공채
