[구현] 프로그래머스 level 2 피보나치 수 (Python 파이썬)

💡문제 링크

프로그래머스

 

 

💡문제 분석 요약

피보나치 수열을 구현하는 문제

 

💡알고리즘 설계

반복문을 이용해서 푼다

% 1234567을 까먹지 않는다

 

💡코드

def solution(n):
    a, b = 0, 1
    if n == 0: return 0
    elif n == 1: return 1
    else:
        for i in range(2, n+1):
            c = (a + b) % 1234567
            if i % 2 == 0: a = c
            else: b = c 
        return c

 

💡 오답 풀이

초반에 런타임 에러가 계속 났는데 그 이유는 재귀함수로 풀었기 때문

def solution(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return solution(n-1) + solution(n-2)

파이썬은 재귀 호출을 할 수 있는 횟수가 정해져 있고,

횟수를 넘어 재귀 호출을 하면 런타임 에러를 내도록 설계되어 있다.

그래서 재귀 호출 대신 for문을 사용해서 첫 번째, 두 번째, 세 번째, ..., n번째 피보나치 수를 순서대로 구했다.

이러한 풀이 방식을 동적 계획법(Dynamic Programming)이라고 한다.

 

 

💡 다른 풀이

def fibonacci(num):
    a, b = 0, 1
    for i in range(num):
        a, b = b, a+b
    return a

나랑 비슷하지만 다른 풀이

나는 num이 0, 1일 때를 다른 경우로 생각했는데

이거는 num 크기에 관계없이 모두 사용할 수 있는 코드 a, b = b, a+b를 만들었다.

 

💡 느낀점 or 기억할정보

재귀함수는 큰 숫자를 감당 못 한다

최대한 반복문으로 풀려고 노력하자!