[프로그래머스/Lv2] 피보나치 수

문제

피보나치 수는 F(0)=0, F(1)=1 일 때, 1 이상의 n에 대하어 F(n)=F(n-1)+F(n-2)가 적용되는 수이다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567로 나눈 나머지를 반환하는 함수를 만들어야 한다.

 

 

제한조건

1. n은 2 이상 100000이하의 자연수이다.

 

 

코드

def solution(n):
    cache = [0 for _ in range(n+1)]
    cache[1] = 1

    for i in range(2, n+1):
        cache[i] = cache[i-1] + cache[i-2]

    return cache[n] % 1234567

 

 

설명

피보나치 수라고 하면 우선 떠오르는 가장 간단한 알고리즘이 이것일거다.

def fibonacci(n):
	if n == 0:
		return 0
	if n == 1:
		return 1

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

재귀함수로 구현한 피보나치 수 알고리즘으로 아주 간단하게 사용할 수 있다.

 

하지만 이 알고리즘으로 해당 문제를 풀어보면 런타임 에러와 시간초과로 문제를 틀리게 된다.

 

런타임 에러의 경우 파이썬에서는 정해진 최대 재귀 깊이가 있는데, 이것보다 깊어질 경우 RecursionError가 발생하게 된다. 프로그래머스에서는 깊이가 1000이 넘어가게 되면 오류가 발생하게 된다.

제한 조건에서 n이 상당히 큰 수도 나올 수 있다고 했고, n이 크면 재귀 깊이가 너무 깊어져 런타임 에러가 발생하는 것이다.

 

시간초과의 경우 단순히 위 재귀알고리즘이 굉장히 느린 알고리즘이기 때문이어서 그렇다.

시간복잡도는 O(2^n).

 

이 문제는 결국 재귀알고리즘을 사용하지 않고 비교적 빠른 다른 알고리즘을 사용해서 문제를 풀라는 의도를 가지고 있다고 볼 수 있다.

 

 

아래부터 코드의 설명이다.

 

cache = [0 for _ in range(n+1)]
cache[1] = 1

0부터 n까지의 길이를 가진 리스트를 만들어 0으로 채워준다. 이 리스트를 cache라고 한다.

이 cache의 인덱스는 각각 인덱스에 해당하는 피보나치 수를 저장해둘 장소이다.

cache[0]과 cache[1]은 0과 1이 되도록 설정한다.

 

for i in range(2, n+1):
	cache[i] = cache[i-1] + cache[i-2]

2부터 n+1까지 반복하여 피보나치 수를 계산, 저장한다.

 

return cache[n] % 1234567

n번째 피보나치 수에서 1234567을 나눈 나머지 값을 반환한다.