피보나치 수를 구하는 다양한 방법

알고리즘 문제를 풀다 보니 피보나치 수를 구하는 방법이 상당히 많다. 따라서 이 피보나치 수로 배울 수 있는 알고리즘이 다양하기에 한번 정리를 해보려고 한다. 피보나치 수열이란? 기원전 5세기 인도의 수학자 핑갈라가 쓴 책에서 처음 언급 됐으며 유럽에서 레오나르도 피보나치가 토끼 수의 증가에 대해서 이야기 하면서 유명해졌다. 해당 내용은 n번째 달의 토끼 쌍의 수는 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다. 두 달 이상이 된 토끼는 번식이 가능하다. 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다. 토끼는 죽지 않는다 이 문제를 통해서 나온 것이 바로 피보나치 수열이다. 첫 번째 달, 두 번째 달 까지는 1쌍이 존재할 것이다. 세 번째 달이 되면서 토끼가 번식이 가능해지면서 2쌍이 되고 3번..

원문링크 : 피보나치 수를 구하는 다양한 방법