[백준 10870번] '케이원' 파이썬(python) 재귀 I 피보나치 수 5

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1 

10

예제 출력 1 

55

 

처음 내가 푼 풀이

n = int(input())

def fibo(n):
    result = 0
    if n == 0:
        return result
    elif n <= 2:
        return 1
    return fibo(n - 2) + fibo(n - 1)

print(fibo(n))

좀더 줄인 코드

n = int(input())

def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 2) + fibo(n - 1)

print(fibo(n))

포문을 활용해서 구한 값

n = int(input())

fibo = [0, 1]
for i in range(2, n + 1):
    num = fibo[i - 1] + fibo[i - 2]
    fibo.append(num)
print(fibo[n])

 

알았던 내용

재귀함수에 대한 전반적인 이해가 있었다.

 

몰랐던 내용

함수 안에 쓴 가정문으로 범위를 <= 1 로 지정한 뒤 리턴으로 그 수 그대로를 받으면 0, 1, 2까지 0 1 1 로 출력받을 수 있었다.

 

배운 내용

재귀함수를 배움으로써 반복되는 동작의 프로그램을 더욱 쉽고 효율적이게 만들 수 있게되었다.