[프로그래머스] 피보나치 수 Python 풀이

프로그래머스(Programmers) 피보나치 수 문제

난이도 : Level 2 

<문제 링크>

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

<처음 코드>

def fibo(n):

    if n<=1:

        return n

    else:

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

def solution(n):

    answer = fibo(n) % 1234567

    return answer

 

처음엔 피보나치 수 구하는 법을 재귀적인 방법으로 정의한 후 계산해 줬는데욥

 재귀법을 사용해서 그런지 시간초과가 나오드라구요,,,, 

아무래도 재귀법은 같은 값을 여러번 호출하다보니..... 효율성이 많이 떨어집니다

-> 같은 계산을 여러 번 반복 -> 시간 복잡도가 지수적(O(2^n))으로 증가

 

 

시간복잡도를 줄여서 더 효율적인 for문을 사용해서 구현해 보았습니다!

<수정된 코드>

def fibo(n):

    a, b = 0, 1

    for i in range(n):

        a, b = b, a + b

    return a

def solution(n):

    answer = fibo(n) % 1234567

    return answer

 

-> 시간 복잡도 O(n)

 

혹은 다이나믹 프로그래밍(Dynamic Programming) 방법을 통해 값들을 저장해주면서 풀이 가능

def solution(n):

    # 피보나치 수 저장할 리스트 생성(0부터 n까지이므로 n+1개 생성필요 )

    fibo = [0]*(n+1)

    fibo[0] = 0

    fibo[1] = 1

    # 반복문을 통해 리스트에 값 담아줌

    for i in range(2,n+1):

        fibo[i] = fibo[i-2] + fibo[i-1]

    # 최종 값 도출, 나눠줘야함

    answer = fibo[n] % 1234567

    return answer