Programmers / 피보나치 수 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 피보나치 수 (2단계)

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/12945

---

나의 풀이 1 - 재귀함수 이용 (오답 + 런타임에러)

def fibo(n):
    if n <=1 :
        return n
    return solution(n-1) + solution(n-2)

def solution(x):
    return fibo(x) % 1234567

재귀함수를 이용하여 풀었다. 

런타임 에러로 실패...

 

나의 풀이 2 - for문 이용

def fibo(n):
    fibonacci = [0,1]
    for i in range(2,n + 1):
        num = fibonacci[i-1] + fibonacci[i-2]
        fibonacci.append(num)
    return max(fibonacci)

def solution(x):
    return fibo(x) % 1234567

 

재귀함수는 아무래도 자기자신을 계속해서 호출하기때문에 런타임에러가 나는 것 같다.

 

fibo 함수에서 for문으로 반복하면서 피보나치 수열 알고리즘에 맞게 fibonacci 리스트에 저장하고,

for문을 다 돌았으면 fibonacci 수열에서 가장 큰 값을 반환한다.

 

그 다음 solution 함수에서 fibo함수에서 나온 값 (max(fibonacci))를 1234567로 나눈 나머지를 반환한다.(문제 조건)

---

※ 알아야 할 것

피보나치 수열

: 재귀함수의 시간복잡도가 더 나쁘다.

(이유: 재귀함수는 다른 함수 호출 할 때마다 2 갈래로 나뉨O(2^N).
반면, 반복문은 기존값에 누적해서 반복적으로 더하기 때문에 O(N))

 

- 출처 https://velog.io/@tiana/%EB%B0%98%EB%B3%B5%EB%AC%B8-vs-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98