Algorithm/프로그래머스

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

떵호 2022. 7. 23. 16:03
728x90

🔗 문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

📂 분류

DP

💡 풀이

피보나치 수는 DP의 대표적인 문제이다.

피보나치 수는 DP를 사용하지 않고 재귀 함수로 풀 경우 이미 계산된 값을 또 계산하기 때문에 스택 버퍼오버플로우가 발생할 수 있다. 때문에 DP를 사용하여 값을 구한다.

 

점화식은 다음과 같다

  • f[i] = f[i - 1] + f[i - 2]

위 점화식을 이용해 구현하면 문제를 해결할 수 있다.

💻 코드

MOD = 1234567


def solution(n):
    global MOD

    fibo = [0] * (n + 1)
    fibo[1] = 1

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

    return fibo[n]
728x90