피보나치 수열
점화식 F(n) = F(n-2) + F(n-1) 을 재귀호출 방법이라고 한다.
이런 방법을 사용하게 되면 n이 50 이상일 때
→ 시간 초과가 나거나
→ Python 이나 JavaScript 등 일부 언어에서는 런타임 에러가 난다.
런타임 에서가 나는 이유 : 일부 언어는 재귀 호출을 할 수 있는 횟수가 정해져 있고, 횟수를 넘어 재귀 호출을 하면 런타임 에러를 내도록 설계되어 있다.
이런 이유로 재귀 호출 대신 for 문을 사용해서 첫 번째, 두 번째, 세 번째, ....., n번째 피보나치 수를 순서대로 구해보는것이 효율적이다
이러한 풀이 방식을 동적 계획법(Dynamic Programming)이라고 한다.
프로그래머스에서 풀다가 이런 힌트를 보게되었는데, 피보나치 수가 뭔지 몰라서 나중을 위해서 구글링을 해보았다.
피보나치 수열(Fibonacci Sequence)의 유래
피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방 쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 가설들도 있긴 하나 공식적인 연관성은 아직 불분명하다. 물론 피보나치가 중세 중동 지역의 수학 서적들을 대거 번역하여 유럽 문명에 소개했던 주인공이었으므로, 인도와 중동에서 발전한 체계적이고 심도있는 수학적 지식을 깊이 공부하던 도중에 피보나치 수열의 아이디어를 차용했을 가능성은 충분히 있다. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에, 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치수열이란 이름은 19세기가 되어서야 붙여졌다
(출처는 나무위키)
수열(Sequence) 이란?
수열은 계속 이어지는 수들의 열이다. 수열에서 포인트는 수열의 규칙이다. 어떤 규칙이냐에 따라서 수열이 달라진다.
피보나치 수열은 그 독특한 규칙 때문에 유명해졌다.
피보나치 수열을 쉽게 이해하기 위한 토끼문제가 있다.
토끼 한 쌍이 있다. 한 쌍의 토끼는 한달이 지나면 성장을 하고, 그 다음 달 부터 매달 암수 한 쌍의 새끼를 낳는다. 태어난 모든 토끼에게 적용. 한 달 동안 성장하고, 그다음 한 달이 지나면 매달 한쌍의 토끼를 낳는다. 1 년이 지나면 몇쌍의 토끼가 있을까?
*조건*
→ 첫 달에는 토끼 한 쌍만이 존재한다.
→ 두 달 이상이 된 토끼는 번식 가능하다.
→ 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
→ 토끼는 죽지 않는다.
이 문제는 어떤 규칙이 있는가를 파악해, 그 규칙으로 답을 알아내야 한다.
첫 달에 태어난 토끼 한 쌍이 어른 토끼가 되어서 두 달 후에 토끼 한 쌍을 낳는다. 이후 어른 토끼는 매달 토끼를 한 쌍씩 낳고, 새끼 토끼는 어른 토끼가 되어서 두 달 후부터 토끼 한 쌍씩 낳는다. f(n)=f(n-1)+f(n-2)가 된다. 그결과 매달 토끼의 쌍을 세어 보면 1,1,2,3,5,8,13,21,34,55, ... 가 된다. 이 수의 배열은 앞의 두 수의 합이 바로 뒤의 수가 되는데, 이렇게 나열되는 수의 배열을 피보나치 수열이라고 한다.
