10870번: 피보나치 수 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번째 피보나치 수를 출력한다.
예시:
입력: 10
출력: 55

요구사항

• 피보나치 수는 0번째는 0, 1번째는 1로 시작
• 피보나치 함수는 f(n) = f(n-1) + f(n-2)
• 피보나치의 n번째 수를 출력함

정답 코드

# 10870번 문제
def fibonacci5(n):
    # 0과 1은 주어진 조건이기 때문에 재귀함수 탈출 조건으로 0, 1를 줌
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 0, 1이 아닐 경우 fibonacci5(n-1), fibonacci5(n-2)를 실행하여 자신을 부름
    else:
        return fibonacci5(n-1) + fibonacci5(n-2)

n = int(input())
print(fibonacci5(n))

함수 실행 설명

n=4일 경우, 해당 재귀 함수는 검은색 화살표가 실행된 뒤, 빨간색 화살표가 실행되는 순서로 이루어진다.

추가 설명

이 문제는 n이 20 이하로 제한되어 있어 메모이제이션(memoization)의 효과가 크지 않다. 그러나 입력 값이 커질 경우 성능 향상을 기대할 수 있으므로, 메모이제이션을 적용한 코드를 살펴보자

메모이제이션 적용 코드

# 10870번 문제 메모이제이션 적용
memo = {}

def fibonacci5(n):
    if n == 0:
        memo[0] = 0
        return memo[0]
    elif n == 1:
        memo[1] = 1
        return memo[1]
    else:
        if n-1 not in memo:
            memo[n-1] = fibonacci5(n-1)
        if n-2 not in memo:
            memo[n-2] = fibonacci5(n-2)
        return memo[n-1] + memo[n-2]

n = int(input())
print(fibonacci5(n))

채점 결과