피보나치 수열의 일반항 구하기
피보나치 수열은 다음과 같이 이루어집니다.
n = 1 : 0 n = 2 : 1 n = 3... : f(n) = f(n-2) + f(n-1)
이 때 n을 입력받아 피보나치 수열의 일반항을 출력하는 프로그램을 작성하세요.
접근
곧이 곧대로 코드를 짤 수도 있을 것이다.
fib :: Int -> Int
fib n = case n of 1 -> 0
2 -> 1
_ -> (fib (n-2)) + (fib (n-1))
main :: IO ()
main = do
n <- readLn :: IO Int
print . fib $ n
문제는 성능이다. 60만 들어가도 하세월이 걸린다. 여기서 생각이 나는 것은 "메모이제이션"인데 일단 하스켈은 mutable한 딕셔너리가 없기 때문에 이 부분은 좀 더 자세히 공부해봐야할 분야이고, 여기서는 좀 더 다른 접근을 취해야 겠다.
무한리스트
하스켈의 리스트는 다른 언어의 배열과 달리, "재귀적"으로 구성되는 일종의 트리이다. (각 노드가 값과 자신의 뒤에 이어질 리스트를 가짐) 이러한 재귀적 구조가 하스켈의 '느긋한 평가'와 맞물리면서 "무한한 크기의 리스트"를 얼마든지 다룰 수 있다는 장점을 갖는다.
또한 리스트는 (x:xs)의 포맷에서 볼 수 있듯이 "어떤 리스트앞에 새 원소가 붙어있다"는 꼴로 환원된다. 따라서 피보나치 수열의 리스트를 이렇게 정의할 수 있다.
fibo a b = a:(fibo b (a+b))
이 무한 리스트에서 n-1개 만큼을 떼어낸 첫번째 원소가 n 번째 원소가 되고, 우리가 원하는 것은 이것이다. 따라서 개선된 fib 함수는 다음과 같이 구현한다. 참고로 피보나치 수열은 매우 눈깜짝할 사이에 엄청 큰 수로 뻗어나가기 때문에 리턴타입이 Integer여야 한다. 따라서 리턴 타입에 유의하자.
fib :: (Integral a) => Int -> a
fib n = head . drop (n - 1) $ fibo 0 1
where fibo :: (Integral a) => a -> a -> [a]
fibo a b = a:(fibo b (a+b))
얼마든지 큰수도 거뜬!
8473
1562439449070278125700317857862702611061663855800759431406237444882548159785230575965641480609469924772719645484601955967500060489573499237343510800495808016133168195822370556309050361587277430996219655721520171213683863083370116063093864586083379818245794071246089504173050649391761441392385646456223247185545591563316047191115062472421668479595469684741022408629028851320749747159471284198956911862317488276616303104316938222489197937199860412534502503991921093397458665351703683501477718020140813347201451289631294038174889714825783771166651043177449099798138424885427107589512936656440879371289363005499835716590294308426479700016552257846095334398968913304465462613617224208986666501826192360875981465310985689554103361980047514497652260651265448975587284112776691616381737612657536423103036764382309140872113032437253608037203044781907566426075286435805284865854621327297416429661766004538758662907873176815706559079232573440263597127260251846490307570104887741925014181591976015655310055278439487634439295194021999774659171432461608719255164541078160567921791271157769112894190213499818088524822629492314342418684339393862283737933674791003999994029688310662285757968894653726812870577459261217453424885034464260535904648659299360344618512073480428969494758681920177640068284427284749367397069249159785434485342874787188868137008173161178457138907328980625261878652103946620312395912692743645523572574047059110735320476739999941447824817628496696743108678755682344594704258558991833183498398463937621829927875483183501348556421857365296189623155139378580708572321655534538315171744028493078727937156732955722123734211844289676374937133584910463361360622542350347179583556156793347558069344744172978990797393956333988226110851297633182301051748808418245365681996064