[알고리즘] 피보나치 수열 - dp를 알기위한 사전단계
·
프로그래밍/algorithm
피보나치 수열의 유래? 피보나치 수열은 규칙을 발견한 수학자 레오나르도 피보나치의 이름을 따 부르게 되었다. 레오나르도 피보나치는 이탈리아 수학자로 이집트, 그리스, 시칠리아 등의 나라를 여행하며 아라비아에서 발전된 수학을 두루 섭렵하였다고한다. 그 많은 업적 중 피보나치수열은 12세기말 이탈리아에서 처음 제안한 것으로 "한 쌍의 토끼가 계속 새끼를 낳으면 몇 마리로 불어 날까?를 연구하다 새로운 수의 체계를 발견하였다고 한다. 한쌍의 토끼는 매일 암수 한쌍의 새끼를 낳으며 새로 태어난 토끼도 태어난지 두달 후 부턴 매달 한쌍씩 암수 새끼를 낳는다고 한다. 그러면 농장주는 1년이 지난후 모두 몇쌍의 토끼를 갖게 될까? 그 결과 피보나치는 매달 관찰되는 토끼의 양이 특정한 규칙을 따르고 있음을 발견..