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

문제 후기

처음 피보나치 수라는 것을 보자마자 재귀를 생각해서 풀었습니다.

1차로 재귀만 사용하였을때 시간초과가 발생하여 2차로 재귀 + DP로 이전에 나온 값이 있는 경우 반복하지 않고 바로 사용하게 했습니다. 제출 결과로 다시 시간초과와 런타임에러가 발생했고 최대 입력값인 100,000을 입력해보니 maximum recursion depth exceeded 에러가 발생했습니다.

알고리즘을 다시 생각해보니 단순 O(n)으로 해결가능한 문제였습니다....😢

처음 문제 파악을 할 때 확실히 파악하는 것이 중요할꺼 같습니다. 문제파악을 더 잘해야겠습니다😂😂

문제 설명

피보나치 수는 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

---

def solution(n):

    chk = 0     # 피보나치 홀수, 짝수 판별
    fibonacci_num1 = 1  # 피보나치 홀수 번째 값(1)
    fibonacci_num2 = 1  # 피보나치 짝수 번째 값(2)

    idx = 3     # 피보나치 3부터 시작
    
    # n 번째 까지 진행
    while idx < n+1:
        if idx % 2 == 1:    # 홀수 경우
            fibonacci_num1 += fibonacci_num2    # F(n) = F(n-1) + F(n-2)
            chk = 1     # 홀수 체크
        else:               # 짝수 경우
            fibonacci_num2 += fibonacci_num1    # F(n) = F(n-1) + F(n-2)
            chk = 0     # 짝수 체크
        idx += 1    # 숫자 증가


    if chk == 1:    # 홀수면 홀수 F(n)값 리턴
        return fibonacci_num1 % 1234567
    else:           # 짝수면 짝수 F(n)값 리턴
        return fibonacci_num2 % 1234567 
        
   
   
   
   # def fibonacci(num, num_dict):
#     if num in num_dict:
#         return num_dict[num], num_dict
#     # elif num < 2:

#     #     return num
#     else:
#         res2, num_dict = fibonacci(num - 2, num_dict)
#         num_dict[num - 2] = res2
#         res1, num_dict = fibonacci(num - 1, num_dict)
#         num_dict[num - 1] = res1
#
#
#         return res1 + res2, num_dict
#
# def solution(n):
#     num_dict = {0:0,1:1}
#     result, _ = fibonacci(n, num_dict)

#     return result % 1234567