피보나치수열 따라하기 (Coding Fibonacci Sequence)

피보나치수열 따라하기 (Coding Fibonacci Sequence)

 

 

오늘은 피보나치수열의 코드를 따라 해 보겠습니다.

피보나치는 중고교 시절 학교에서 꼭 집고 넘어가는 역사적인 수열입니다.

 

먼저 피보나치수열을 살펴보겠습니다.

 

 

1, 1, 2, 3, 5, 8, 13, 21, ···

 

f(n) = 1 (n＜=2 일 때)

f(n) = f(n-2)+f(n-1) (n＞2 일 때)

 

출처: [네이버 지식백과] 피보나치 수열 [Fibonacci Sequence] (컴퓨터 개론, 2013. 3. 10., 김종훈, 김종진),

https://terms.naver.com/entry.nhn?docId=2270442&cid=51173&categoryId=51173

 

네이버 지식백과의 설명을 참조했습니다.

즉, 피보나치라는 것은 앞 두 항의 합이 다음 항이 되는 것입니다.

공식은 두 번째 값부터 성립됩니다. f(n) 값이 완성되기 위해서는 f(n-2)와 f(n-1) 값이 존재해야 하기 때문입니다.

따라서 피보나치수열은 'n>2 일 때' 성립됩니다.

 

1, 1, 2, 3, 5, 8, 13, 21

a, b, c, d, e, f, g, h

 

실제 숫자를 넣어서 피보나치를 체크해보겠습니다.

a+b= c, b+c= d, c+d= e가 되는 형태입니다.

숫자를 넣으면 1+1= 2, 1+2= 3, 2+3= 5가 됩니다.

 

이 형태를 식으로 만들면 f(n) = f(n-2)+f(n-1) (n＞2 일 때) 이렇게 됩니다.

 

 

이제 개념을 정리했으니 코드를 따라 해 보겠습니다.

파일은 Fibonacci.py로 만들어봤습니다.

 

 

 

def fibo(n):

if n <= 1:

return n

else:

return(fibo(n-1) + fibo(n-2))

 

for n in range(1,11):

print(fibo(n))

 

 

1행의 def은 define의 약자로 함수를 정의하는데 쓰입니다.

다음 코드를 fibo(n) 함수로 정의해 봤습니다.

 

2행은 n이 1보다 작거나 같다면 3행에서 그대로 n값을 반환하라는 뜻입니다.

 

4행은 만약 n이 1보다 크다면 5행에서 (n-1)항과 (n-2)항이 더해져서 값이 반환됩니다.

 

6행은 range() 함수를 써서 for문으로 1에서 10까지 반복합니다.

range(1,11) 함수는 1부터 10까지 숫자를 생성한다는 의미입니다. range(1,10)으로 헷갈리시면 안 됩니다.

 

마지막행은 피보나치 값을 출력합니다.

 

 

그럼 피보나치수열 출력 값을 하나하나 살펴보겠습니다.

 

n=1인 경우 2행에서 'n<=1' 조건을 주었기 때문에, 3행에서 그대로 1이 반환됩니다.

 

n=2인 경우 5행에서 f(1)+f(0)이 됩니다. 하지만 2행에서 'n<=1' 조건이 되면 3행에서 그대로 n이 반환되기로 약속했습니다.

따라서 f(1)은 1이 되며, f(0)은 0이 됩니다. 따라서 f(1)+f(0)= 1이 됩니다.

 

n=3인 경우 5행에서 f(2)+f(1)이 되기 때문에 2가 됩니다.

n=4인 경우 5행에서 f(3)+f(2)이 되기 때문에 3이 됩니다.

n=5인 경우 5행에서 f(4)+f(3)이 되기 때문에 5가 됩니다.

n=6인 경우 5행에서 f(5)+f(4)이 되기 때문에 8이 됩니다.

n=7인 경우 5행에서 f(6)+f(5)이 되기 때문에 13이 됩니다.

n=8인 경우 5행에서 f(7)+f(6)이 되기 때문에 21이 됩니다.

n=9인 경우 5행에서 f(8)+f(7)이 되기 때문에 34가 됩니다.

n=10인 경우 5행에서 f(9)+f(8)이 되기 때문에 55가 됩니다.

 

 

 

오늘도 VSCode의 TERMINAL을 사용해 보겠습니다.

C:\Users\ATIV\Downloads\myworks>python .\Fibonacci.py을 칩니다.

 

 

 

C:\Users\ATIV\Downloads\myworks>python .\Fibonacci.py

1

1

2

3

5

8

13

21

34

55

 

이번 코드를 따라 해 보면서 f(1)과 f(0)을 어떻게 처리해야 할지 막막했습니다.

이 코드의 핵심 포인트는 2행과 3행입니다.

2행에서 만약 'n <= 1'라면 3행 'return n'이 됩니다. 따라서 f(1)은 1이 되고 f(0)은 0이 되는 겁니다.

이 포인트만 집고 넘어가신다면 피보나치수열 코드를 이해하시는 일이 훨씬 수월해집니다.