99클럽 TIL (240811)

> [Middler] 피보나치 수

 

걸린시간 : 48분

 

문제 풀이 과정

 

피보나치 수는 다음과 같은 형태의 수열입니다.

• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

이처럼 3번째 항부터 n번째 수가 n-1번째 수와 n-2번째 수의 합으로 나타낼 수 있는 수열입니다. 이는 점화식으로 표현할 수 있습니다. 

 

그렇기 때문에 해당 문제는 다이나믹 프로그래밍으로 분류되어 해당 점화식을 재귀적으로 수행하면 결과를 얻을 수 있다고 판단했습니다.

그렇게 작성한 저의 첫 코드는 아래와 같습니다.

 

[처음 문제 풀이 : 재귀함수] 실패

def solution(n):
    d = [0] * n
    
    d[0] = 0
    d[1] = 1
    
    def fibonacci(i) :
        if i < 2 :
            return d[i]
        return (fibonacci(i-1) + fibonacci(i-2)) % 1234567
    
    return fibonacci(n)

 

그러나 이처럼 테케 7번부터 14번까지 실패하였습니다...ㅎㅎ 이유가 뭘까 고민해보다가 아직 짧은 지식으로는 알수가 없어 질문하기 탭을 참조하여 힌트를 얻을 수 있었습니다. 

 

💡 시간초과 및 런타임 에러 이유

• 재귀의 성능은 반복문에 비해 느리다 => 시간 초과
• 파이썬의 재귀 호출 스택 깊이는 최대 1000이다. 재귀를 통한 반복은 스택의 깊이를 초과할 수 있다. => 런타임 에러
  • 참고) 함수는 스택에 추가되어 호출된다!

 

문제 풀이

1. python

def solution(n):
    fibonacci = [0, 1]
    
    for i in range(2, n+1) :
        fibonacci.append((fibonacci[i-1] + fibonacci[i-2]) % 1234567)
    
    return fibonacci[n]

 

반복문으로 수정했다! 

 

시간복잡도 O(N)

n번 길이만큼 반복하니까

 

오늘의 회고 및 느낀점

DP니까 재귀로 풀어야겠다!라고 생각했으나, 재귀의 단점이 있음을 깨달을 수 있었다. 사실 재귀를 호출하면서도 시간이 어느정도 소요될지 정확히 예상이 잘 안가긴 했어서 나 자신을 반성하게 되었음. 그리고 컴퓨터 관련 지식을 더 공부해야겠다고 생각하게 되었다. 아자아자