행렬의 곱을 이용한 피보나치 수열 구하기

피보나치 수열은 죽지 않는 토끼에서 유래 되었는데요.

처음 태어난 토끼 한쌍은 한달이면 다 자라고 그 다음달 부터는 매달 한쌍의 새끼를 낳았을때 1년 후 혹은 2년 후에 몇쌍이 되어 있는지 궁금해서 묻는 문제에서 유래 되었는데요.

이러한 토끼가 살아 있는 쌍을 구하는 공식을 테이블을 이용해 그려 보면 다음과 같이 그려 볼 수가 있습니다.

새끼를 낳을수 있는 토끼를 성체라고 보면 다음과 같이 됩니다.

기간	1월	2월	3월	4월	5월	6월	7월	8월	9월
태어난쌍	1	0	1	1	2	3	5	8	13
성체	0	0	1	1	2	3	5	8	13
살아있는쌍	1	1	2	3	5	8	13	21	34

성체를 계산 하는 방법은 전월의 성체의 수에 전전월에 태어난 토끼의 수를 더해 주면 됩니다.

가령 3월의 성체 수는 2월의 성체수(0) + 1월에 태어난 쌍(1) = 1 이 되고

4월의 성체 수는 3월의 성체수(1) + 2월에 태어난 쌍(0) = 1 이 되는 이치입니다.

성체는 새끼를 낳을 수 있으므로 해당 월에 태어나는 토끼는 해당월의 성체수에 해당 합니다.

따라서 살아있는 쌍은 전월에 살아있는 쌍의 수 + 해당월에 태어난 수가 살아 있는 쌍이 됩니다.

이렇게 계산을 해 보면 결국은 해당월에 태어나는 수는 전전월에 살아있는 수와 동일하게 되는데요.

이러한 테이블을 이용해서 n개월 후의 토끼의 수는 n-1개월 후의 토끼 수 + n-2개월 후의 토끼 수가 되며

점화식으로는  f(1)=1,f(2)=1 이고 f(n) = f(n-1) + f(n-2) 로 표현을 할 수가 있습니다.

이 때 수열의 일반항 f(n)을 구하는데 이 수열을 행렬을 통해 An+1,An 에 관한 식으로 표현이 가능합니다.

여기서 행렬의 곱셈식을 살펴 보면 다음과 같습니다.

따라서 행렬식을 통해 An+1 = An + An-1 을 표현해 볼 수가 있는데요.

이것은 다시 다음과 같이 표현을 해 볼 수가 있습니다.

이렇게 가면 결국은 다음과 같이 표현을 해 볼 수가 있게 됩니다.

결국은 다음과 같이 표현을 할 수가 있습니다.

따라서 

이렇게 표현을 할 수가 있으며 행렬의 곱셈식을 이용해서 다음과 같이 표현이 가능합니다.

행렬의 곱셈식

행렬식을 이용한 피보나치 수열

이 행렬의 곱을 이용한 피보나치 수열을 계산하게 되면 

https://www.acmicpc.net/problem/2749의 피보나치3 과 같은 n의 값이 큰 데이터도 분할 정복 기법을 이용해서 풀이를 해 볼 수가 있습니다.

 

가령 n의 값이 10000 의 값이 들어 온다면 

위와 같이 계산을 하게 되면 10000 -> 5000 -> 2500 -> 1250 -> 625 -> 624 -> 312 -> 156 -> 78 -> 39 -> 38 -> 19 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1 (18회 의 계산으로 피보나치 수열의 값을 계산 할 수가 있게 됩니다.)

 

피보나치 수열을 계산하는 방법이 행렬식을 이용한 방법만 있는 것은 아니지만...

이렇게 행렬식을 이용해서 피보나치 수열을 풀어 나갈 수 있다는 것을 발견한 사람도 대단한것 같아요.^^

 

우리 학생들도 많은 연구를 통해서...

아직 밝혀지지 않은 많은 경우를 직접 찾아 내서 미래의 기술 발전에 큰 이바지를 할 수 있는 학생들이 되기를 기원합니다.

 

인천 서구 원당컴퓨터학원