피보나치 수의 행렬 접근

피보나치 수는 0, 1로 시작하고 i번째 피보나치 수가 바로 앞 두 수의 합이 되는 수열이다.

 

이를 식으로 써보면

 Fn = Fn-1 + Fn-2 (n ≥ 2)

이렇게 나타낼 수 있다.

 

n이 작을때, 피보나치수는 간단한 연산으로 구할 수 있지만 n이 굉장히 커지면 이를 구하는 데 시간이 많이 든다.

이때 행렬로 피보나치 수를 나타내는 방식은 도움이 된다.

 

위의 식을 행렬로 나타낸 것이다.

 

오른쪽 항의 뒤쪽 행렬과 비슷한 꼴로 맞춰주기 위해 조금 변형을 해보자.

 

0번째 피보나치수는 0, 1번째 피보나치수는 1이므로 위 식을 재귀적으로 연산하게되면 다음과 같은 결과를 얻을 수 있다.

 

n + 2번째 피보나치 수를 구하는 문제는 행렬을 n + 1번 제곱하는 문제로 바뀌었다.

 

위 식의 오른쪽 항의 앞쪽 행렬을 A라고 하자.

이때 A의 n + 1제곱은 다음과 같이 구할 수 있다.

 

n + 1이 짝수라면,

n + 1이 홀수라면, 

재귀적으로 위의 방법으로 제곱을 반으로 쪼개가며 계산할 수 있다.

 

 

 

처음 이런 접근을 봤을때도 엄청 흥미로웠는데 이 글을 쓰려고 다시 계산해볼때도 재밌다.

또 어떤 것에 적용을 할 수 있을까?