피보나치 수열 심화과정2 - 자연수 n이 피보나치 수인지 바로 알 수 있을까? -

1. 주어진 수가 피보나치 수인지 바로 알 수 있을까? 피보나치 수는 $F_{1} = F_{2} = 1$이고 $F_{i} = F_{i-1} + F_{i-2}$을 만족하는 $F_{i}$이다. 반대로 어떤 자연수 n이 주어질때 그 수가 피보나치 수열 $F_{i}$의 하나인지 바로 판단할 수 있을까? 2. 행렬을 이용해 피보나치 수를 만드는 방법 일반적으로는 $F_{1} = F_{2} = 1$부터 차근차근 만들어나가는 것이다. 그러면 언젠가 주어진 자연수 n 근처에 도달할 것이고, n에 정확히 도달하면 n은 피보나치 수이고 n을 넘어가면 n은 피보나치 수가 아니다. 행렬을 이용한 피보나치 수 생성하는 방법이 O(logN)으로 가장 빠르면서 유의미한데, 이정도만 해도 사실 상당히 빠르다 https://deepd..