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