[컴퓨팅 사고력] 피보나치 수열

피보나치 수열이란?

피보나치 수열의 유래는 피사의 레오나르도로 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대해 연구하기 시작되었으며 다음과 같은 수열을 피보나치 수열이라고 합니다.

1항	2항	3항	4항	5항	6항	7항	8항	9항	10항
1	1	2	3	5	8	13	21	34	55

이 수열의 규칙은 1항과 2항은 각각 1이고 3항 부터는 전항과 전전항의 값을 더한 값이 됩니다.

 

 

피보나치 수열에 관한 문제유형

일반적으로 피보나치 수열을 응용한 문제가 정보올림피아드 수학에서 종종 나오고 있으며 특히 알고리즘 분야에서는 동적알고리즘을 배울때 처음 만나게 되는 수열중에 하나 입니다.

그렇다면 정보올림피아드에서 나왔던 기출문제를 풀어 보겠습니다.

 

 

정보올림피아드 2003년 초등부 10번 문제

암컷과 수컷 한쌍의 토끼가 2003년 1월 말에 태어났다. 토끼의 생태를 다음과 같이 가정했을 때 2003년 8월 초에 살아 있는 토끼는 총 몇쌍인가? (1) 토끼는 태어난 달의 다다음 달 초가 되어야 성숙하게 된다. 예를 들어 1월 말에 태어난 토끼는 3월 초가 되어야 성숙하게 된다. (2) 한 쌍의 성숙한 토끼는 매달 말에 암컷과 수컷 한쌍의 새끼를 낳는다. (3) 이 기간 동안 죽는 토끼는 없다.

문제풀이)

정답) 13쌍

문제풀이) 각 태어나는 쌍과 살아 있는 쌍을 테이블을 그려 보면 다음과 같다.

	1월	2월	3월	4월	5월	6월	7월	8월
태어난쌍	1		1	1	2	3	5	8
성숙한쌍			1	1	2	3	5	8
살아있는쌍	1	1	2	3	5	8	13	21

 위의 표에서 1월에 태어난 쌍은 3월에 성숙한쌍이 되어 3월 말에 새끼를 낳는다.

4월이 되었을때 3월에 성숙한 쌍이 새끼를 낳을 수 있지만 2월에 태어난 쌍은 없기 때문에 성숙한 쌍은 1쌍이다.

5월은 기존에 있던 성숙한 쌍에 3월에 태어난 쌍이 성숙한 쌍이 된다.

이것을 표로 그려보면 위와 같이 그려 볼 수 있다.

여기서 8월 초에 살아 있는 쌍을 구하라고 했으니 새끼는 8월 말에 태어나므로 8월초에는 7월 말에 새끼를 낳은 것까지 계산해서 13쌍이 된다.

살아 있는 쌍을 확인해 보면 피보나치 수열임을 알 수 있다.

 

 

 

정보올림피아드 2016년 초등부 12번 문제

1월 1일에 방큼 태어난 암컷과 수컷 토끼 한쌍을 원래 토끼가 없던 아름다운 섬에 풀어 주었다. 암수 한쌍은 태어난지 2달 후 부터 매월 1일에 암컷 1마리, 수컷 1마리 쌍을 새끼로 낳는다. 11월 2일에 토끼섬에 있는 토끼의 수는?

문제풀이)

정답) 178 마리

문제풀이)

새끼를 낳을 수 있는 성체는 2개월 전에 태어난 새끼 입니다.(빨간색선)

따라서 3월에 성체가 되는 쌍은 1월에 태어난 1쌍이 성체가 되어 새끼를 새로 낳게 됩니다.(파랑색선)

따라서 살아있는 쌍은 기존에 있던 쌍에 새로 태어난 쌍을 더해 주게 됩니다.(녹색선)


11월에 89쌍이 되는데 여기에 2를 곱해주어야 합니다. 1쌍은 2마리

살아있는 쌍의 규칙은 피보나치 수열의 규칙입니다.

 

 

 

정보올림피아드 2019년 초등부 10번

어린 토끼 한 쌍을 집으로 데려왔다.마법의 벨을 한번 울리면, 어린 토끼 쌍은 어른 토끼 상이 되고, 각 어른 토끼 쌍은 어린 토끼 한 쌍을 낳는다. 어떤 토끼도 영원히 죽지 않는다고 하면, 토끼 쌍이 50쌍 이상이 되려면 최소 몇번의 벨을 울려야 할까?

문제풀이)

정답) 9번

문제풀이)

벨 횟수별로 아기는 성체가 되고 그 다음 벨이 울리는 시점에 그 전의 성체가 아기를 낳는다.
살아있는 수는 그 전의 성체 + 태어난 쌍이다.
결국은 살아있는 수는 피보나치 수열이다

 

 

 

정보올림피아드 2004년 중등부 7번,고등부 5번

유전자조작을 통해 만들어 낸 토끼는 다음과 같은 특성을 가지고 있다. 특성1. 모든 토끼는 태어나서 성장하는데 1달이 걸린다. 특성2. 성장을 마친 후 1달이 된 한쌍의 토끼는 매달 2쌍의 토끼를 낳는다. 특성3. 토끼는 1년 이내에 죽지 않는다. 막 성장을 마친 토끼 한쌍을 토끼장에 넣었다. 5달 후의 토끼는 몇쌍이 될까?

문제풀이)

정답) 43쌍

문제풀이)

1개월 후 어른토끼가 2쌍의 새끼를 낳고 

성장을 마친 토끼 한쌍은 1개월후 새끼를 낳을수 있는 어른 토끼쌍이 된다.

어른토끼쌍은 2쌍의 토끼를 낳기 때문에 1개월 후 3쌍의 토끼가 살아 있게 된다.

태어난 2쌍은 성장하는데 1개월이 걸리지만 새끼를 낳을수 있는 어른토끼는 2개월 후에 낳을 수 있다.

이 문제는 피보나치 수열은 아니지만 토끼를 이용하는 문제를 응용한 문제이다.

피보나치 수열이 나온 원리를 응용한 문제

 

 

오늘은 피보나치 수열의 원리를 가지고 나온 정보올림피아드 기출문제 유형을 풀어 보았습니다.

이러한 유형의 문제들을 풀어 보면서 수열의 원리를 재미있게 풀어 볼수 있는 시간이 되었는데요~

이 수열의 원리는 수학과 과학의 많은 분야에서 실제로 적용되고 있다고 합니다.^^

이렇게 다양한 유형의 문제들을 접하면서 수학의 원리를 깨닫고 새로운 재미의 세계에 푹 빠져 보시길 바랍니다.^^

 

 

오늘 하루도 최선을 다하는 우리 학생들을 응원합니다.^^

 

인천 서구 검단신도시 원당컴퓨터학원