[level 2] 피보나치 수(피보나나치 수열 구현 복습하기!)

문제

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.

 

문제 풀이 접근법1

1) fib함수를 선언한다.

2) n= 0이면 0을, 1이나 2면 1을 반환하고, 0,1, 2가 아니라면 fib(n-1)+fib(n-2)를 반환한다.(재귀함수 사용)

3) solution함수에서 fib()함수에 n을 넣은 값과 1234567을 나눈 나머지를 반환한다. 

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

def solution(n):

    return fib(n) % 1234567

테스트 케이스 7, 10, 13, 14에서 런타임 에러

테스트 케이스 8, 9, 11, 12에서 시간 초과가 발생했다. 

 

13, 14의 런타임 에러는 재귀함수가 깊어지면서 발생하는 에러라고 하길래 피보나치 수열을 재귀함수가 아닌 방법으로 구현해보았다. 

 

 

문제 풀이 접근법2

1) a와 b를 각각 1로 설정한다.

2) 만약 n이 1이거나 2라면 answer를 1로 설정한다. 

3) 1부터 n까지 반복문을 돌면서 a에는 b값을 넣고, b에는 b+a값을 넣는다

• n이 5이라면 
  • i=1, a=1, b=2
  • i=2, a= 2, b=3
  • i=3, a=3, b=5
  • i=4, a=5, b=8

이 되고 n-1번 반복하므로 a=5가 된다. 

4) answer변수에 a를 넣고

5) a와 1234567을 나눈 나머지를 반환한다. 

def solution(n):
    answer = 0 
    a, b = 1, 1
    
    if n == 1 or n == 2:
        answer = 1
    
    for i in range(1, n):
        a, b = b, b+a
    
    answer = a
    

    return answer % 1234567

 

 

분명...알고리즘할때 피보나치 수열 배웠는데...

다까먹었다....ㅎ

복습해야지...!!!!

 

---

참고: https://velog.io/@cha-suyeon/python-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0-%EC%A0%90%ED%94%84%ED%88%AC%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A2%85%ED%95%A9%EB%AC%B8%EC%A0%9C-5%EB%B2%88

[python] 피보나치 수열 만들기 (점프투파이썬 종합문제 5번)

 

제너레이터로 피보나치 함수 구현하는 것도 있던데 그것도 해봐야지 

https://hongl.tistory.com/229

제너레이터와 yield (1)