[백준] B2. 피보나치 수 5 (Python)

❓ 문제

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

💡 해결하기

피보나치 수는 다음과 같은 시퀀스가 성립한다.

➡️ 0번째 피보나치 수는 0, 1번째 피보나치 수는 1로 정의한다.

➡️ n번째 피보나치 수는(n >= 2) n - 1 번째의 피보나치 수와 n - 2번째의 피보나치 수의 합이 된다.

예를 들어, 3번째 피보나치 수를 구한다고 하면 다음과 같은 과정을 통해 구해야 한다.

F3 = F2 + F1 = (F1 + F0) + 1 = (1 + 0) + 1 = 2

즉, n번째 피보나치 수를 구하는 과정에는 n - 1, n - 2, ... , 0번째 피보나치 수를 구하는 과정이 포함되어 있는 것이다.

따라서 피보나치 수를 구하는 과정은 n을 1씩 줄여가며 재귀적으로 구현할 수 있고, 종료 조건은 n이 1이나 0이 되었을 때가 된다.

💻 Python으로 코드 작성하기

# 정수 입력받기
n = int(input())

# 피보나치 수 구하는 과정 구현
def fibonacci(n):
    if n == 0:     # n이 0일 경우
        return 0     # 정의에 따라 0 반환
    elif n == 1:     # n이 1일 경우
    	return 1     # 정의에 따라 1 반환
    else:     # n이 2 이상일 경우
    	return fibonacci(n - 1) + fibonacci(n - 2)     # fibonacci 함수에 n-1과 n-2의 값을 전달하며 재귀 호출
        
print(fibonacci(n))

위의 경우에는 fibonacci 함수가 2번씩 재귀 호출되므로 fibonacci(n-1)이 먼저 실행된 다음에 fibonacci(n)이 그 다음으로 실행된다.

n으로 5를 입력받았을 때를 살펴보면 다음과 같은 순서로 fibonacci 함수 호출이 된다.

위 코드가 잘 실행되기는 하지만 효율성이 떨어지는 면이 있다.

위 실행 과정을 보면 7번 과정을 통해 f(3)에서 사용될 f(2)(n - 1)를 이미 구해놓았는데 13번 과정에서 f(4)에 사용될 f(2)(n - 2)를 또 구하고 있다. 두 경우에 사용될 f(2)의 값은 동일한데 말이다.

입력 숫자의 크기가 커질수록 위와 같이 이미 구한 적이 있는 값을 또 구하는 과정이 더 많이 반복될 것이고 이는 곧 시간 초과로 이어질 수 있다.

따라서 이미 구해놓은 값은 기록하는 방식을 사용하여 또 구하지 않게 하는 코드로 개선할 필요가 있다.

그려려면 다음과 같이 딕셔너리를 이용해 구한 값을 기록하여 현재 n값이 딕셔너리의 key로 존재하는지 매번 확인하는 코드를 작성하면 된다.

👩‍🔧 코드 개선하기

n = int(input())

record = {0: 0, 1: 1}     # 이미 정의되어 있는 0번째, 1번째 피보나치 수는 미리 기록해 놓기

def fibonacci(n):
	if n in record:     # 현재 n이 record에 key로 존재하면
        return record[n]     # 그 value를 반환
    else:     # 현재 n이 record에 key로 존재하지 않는다면
    	record[n] = fibonacci(n - 1) + fibonacci(n - 2)     # n번째 피보나치 수에 대한 정보를 record 딕셔너리에 기록
     	return record[n]     # record[n]의 값이 곧 fibonacci(n - 1) + fibonacci(n - 2)의 값이므로 결국 위의 코드와 동일

print(fibonacci(n))

위와 같이 작성하면 시간이 많이 줄긴 하지만 큰 숫자를 입력하였을 때 recursion 횟수를 초과했다는 RecursionError를 만나게 될 수 있다.

따라서 완전히 오류 없이 풀어내기 위해서는 재귀가 아닌 반복문을 이용하여 코드를 작성해야 한다.

바로 위의 코드에서 딕셔너리를 리스트로, 재귀 함수를 반복문으로 바꾸어 작성하기만 하면 된다.

👩‍🔧 코드 개선하기

n = int(input())     

record = [0, 1]     # 0번째, 1번째 피보나치 수는 정의대로 먼저 기록, 후의 피보나치 수들을 계속 누적할 리스트

if n == 0 or n == 1:     # 입력된 숫자가 0 또는 1이면
    print(record[n])     # 바로 record에서 찾아 반환
else:     # 입력된 숫자가 2 이상이면
    for i in range(2, n + 1):     # 2부터 n까지 단계를 거치면서 n번째 피보나치 수 찾기
        record.append(record[-1] + record[-2])     # i번째 피보나치 수는 i-1번째(record[-1])와 i-2(record[-2])번째 피보나치 수의 합, 그것을 record의 마지막 요소로 기록
    print(record[-1])     # 기록이 모두 끝난 후 record의 제일 마지막 요소가 n번째 피보나치 수