백준 10870번 [Python] 문제풀이 (피보나치 수 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

 

 

알고리즘 분류

ㆍ없음

 

 

파이썬 코드(명령형)

a = 0
b = 1
c = 1
for _ in range(int(input())):
    a = b
    b = c
    c = a + b  
print(a)

보기에 가장 직관적인 코딩.

a, b c 를 0 1 1 로 설정하고 원하는 수가 나올 때까지 계산한다.

 

파이썬 코드(재귀형)

def pibo(n):                      # 재귀 함수
    if n < 2: return n            # 2보다 작을 때 그대로 반환
    return pibo(n-1) + pibo(n-2)  # n-1번째 수와 n-2번째 수를 더해 반환
print(pibo(int(input())))

피보나치 수열의 단짝 재귀형 함수

위 문제를 풀때는 상관없지만 위 코드에는 결함이 하나 있다.

n의 값이 클수록 연산시간 또한 기하급수적으로 올라간다.

50을 넣었을 땐 프로그램이 멈춘줄 알았다.

 

파이썬 코드(동적 프로그래밍)

n = int(input())
f = [0] * (n + 1)                       # n + 1 만큼 리스트 생성
def pibo(n):
    if(f[n]) != 0:                      # f안에 값이 존재한다면
        return f[n]                     # 재귀함수를 거치지 않고 그대로 출력

    if n < 2: 
        f[n] = n
        return f[n]
    else: f[n] = pibo(n-1) + pibo(n-2)  # f[n]에 저장
    return f[n]
print(pibo(n))

똑같은 연산을 진행할 경우 연산을 반복하지 않고

결과값이 저장된 리스트에서 출력하도록 하였다.

빠르다.