[파이썬 코딩 - Chap.11] 실습 피보나치 수열 문제 풀어보기

파이썬 예제 : 피보나치 수열

예제를 풀면서 파이썬(Python)을 익혀 보도록 하겠습니다.

- 오늘 풀어볼 문제는 피보나치 수열에 관련된 문제입니다.

- 이론은 아래 링크를 참고하세요.

 

📌 피보나치 수열

피보나치 수 - 위키백과, 우리 모두의 백과사전

📌 참고 영상 추천

[고급 무료 강연 : TED] 아서 벤자민 - 피보나치 수의 마법

 

문제

피보나치 수열(Fibonacci Sequence)라고 들어 보셨나요?

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
1,1,2,3,5,8,13,21,34,55,...

우선 피보나치 수열의 1번 항과 2번 항은 각각 1입니다. 3번 항부터는 바로 앞 두 항의 합으로 계산됩니다. 예를 들어서 3번 항은 1번 항(1)과 2번 항(1)을 더한 2이며, 4번 항은 2번 항(1)과 3번 항(2)을 더한 3입니다.

피보나치 수열의 첫 50개 항을 차례대로 출력하는 프로그램을 작성해 보세요.

 

출력 예시

1
1
2
3
5
8
13
21
.
.
.
4807526976
7778742049
12586269025

 

힌트

1. 일단 50개의 항이 조금 부담될 수 있으니, 10개의 항만 출력하는 걸 목표로 합시다. 어차피 10개를 제대로 출력할 수 있으면, 50개도 아무런 문제 없이 출력할 수 있을 테니까요.

10개의 항을 출력하기 위해서는 반복문을 열 번 돌아야겠죠? 열 번 도는 반복문부터 작성해 봅시다.

 

i = 1
# 추가적으로 필요한 변수가 몇 개 더 있습니다.

while i <= 10:
    # 우리가 반복적으로 무엇을 해야 할까요?
    i += 1

 

이제 여기서 발전시켜 보세요.

 

2. 피보나치 수열의 항은 앞선 두 항의 합으로 계산되는데요. 따라서 피보나치 수열의 항들을 순서대로 출력하기 위해서는 늘 마지막 두 항을 변수에 보관해야 합니다.

'현재 항'은 변수 current에, 그리고 '직전 항'은 변수 previous에 저장을 하겠습니다. 처음에는 current를 1로 설정하고 previous를 0으로 설정하면 되겠죠?

 

previous = 0
current = 1
i = 1

while i <= 10:
    # 우리가 반복적으로 무엇을 해야 할까요?
    i += 1

 

이제 while 반복문의 수행 부분만 채워 넣으면 됩니다.

 

3. 수행 부분에서 해야 할 일은 크게 두 가지입니다.
current를 출력
previous와 current를 적절히 수정
1번은 그냥 print(current)를 하면 되는 거고, 2번이 조금 어려울 수 있는데요. 한 번 고민해 보세요!

 

previous = 0
current = 1
i = 1

while i <= 10:
    print(current)
    # previous와 current를 적절히 수정
    i += 1

 

4. 수행 부분에서 previous와 current를 어떻게 수정할 수 있을까요? 이렇게 하면 됩니다.

previous ← current
current ← current + previous
코드로 나타내면 그냥 이렇게 하면 되겠죠?

 

previous = current
current = current + previous

 

그런데 사실 위 코드처럼 하면 문제가 생깁니다. 잘 생각해 보세요. previous = current를 하면, previous와 current가 같은 값을 저장하게 됩니다. 그리고 기존의 previous 값은 잃어버리게 되죠. 그래서 current = current + previous를 하면 current = current + current를 하는 것과 같게 됩니다.

이 문제는 어떻게 해결할 수 있을까요?

 

5. 힌트 4에서 이야기한 문제점은 기존 previous의 값을 잃어버린다는 것인데요. 이 문제를 해결하기 위해서 임시 보관소 역할을 할 변수를 만들면 됩니다.

 

temp = previous  # previous를 임시 보관소 temp에 저장
previous = current
current = current + temp  # temp에는 기존 previous 값이 저장돼 있음

 

이렇게 하면 문제 없이 previous와 current를 수정할 수 있습니다.

 

정답

main.py
previous = 0
current = 1
temp = 0
i = 1

while i <= 50:
    print(current)
    temp = previous
    previous = current
    current = current + temp
    i += 1

 

Related References

코딩이 처음이라면, 코드잇

PYTHON 프로그래핑

요약 : sparta coding club, 스파르타 코딩, 코드잇, 노마드 코더, 프로그래밍, 직장인 코딩, 내일 배움 카드 코딩, 밀크티 코딩, 초등 코딩, 아이스크림 코딩, 코딩 소프트웨어, 파이썬 국비 지원, 파이썬 교육