피보나치 (Programmers 12945)
🧑💻 피보나치 수
- 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
- 예시
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
- 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 사항
- n은 1이상, 100000이하인 자연수입니다.
입출력 예
n return 3 2 5 5
🧑💻 해결방법
- 간단하게 recurvise하게 풀었지만 시간복잡도 O(n^2)로 런타임에러
- iterative하게 풀면 깔끔하게 해결 시간복잡도 O(n)
🧑💻 코드
def fibo_recursive(n) : if n == 0 : return 0 elif n == 1 : return 1 elif n >= 2 : return fibo_recursive(n-1) + fibo_recursive(n-2) def fibo_iterative(n) : if n < 2 : return n a, b = 0, 1 for i in range(n - 1) : a, b = b, a + b return b def solution(n): answer = fibo_iterative(n) answer %= 1234567 return answer
🧑💻 총평
- 좀 더 구현에 대한 사고를 길러야겠다.
- 단 번에 iterative한 방법이 떠오르지 않았다
Author And Source
이 문제에 관하여(피보나치 (Programmers 12945)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@moonpiderman/피보나치-Programmers-12945저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)