백준 1003 피보나치 함수 파이썬 풀이

 

 

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

문제 이해

피보나치 함수 문제는 피보나치를 재귀함수로 풀었을 때, 0과 1이 각각 몇 번씩 등장하게 되는지에 대한 문제이다. 문제에서는 코드 예시를 C언어로 해두었다.

문제에 들어가기 전에 파이썬은 재귀함수를 사용할때 늘 깊이에 대한 생각을 하지 않을 수 없다. 왜냐하면 파이썬 언어 내부적으로 재귀함수의 깊이를 1000회로 제한을 두었기 때문이다.

 

https://url.kr/s72w3t

백준 1676 팩토리얼 0의 개수 파이썬 풀이 - recursionError

 이전에 팩토리얼 문제 풀면서 파이썬에서의 재귀 깊이를 다룬 내용이다. 심심하면 참고하면 좋을듯하다!

 

기본적으로 파이썬은 재귀의 깊이를 1000회로 걸어두었고 그 제한을 풀 수 있지만 권장되는 방법은 아니다. 정도만 짚고 문제로 다시 돌아가보도록 하자.

 

접근법

재귀함수를 돌리면서 0 또는 1이 등장할때마다 count += 1 하는 식으로 접근하면 좋을 듯 하지만 앞서 말했듯이 파이썬은 재귀로 돌리려고 했다간 에러를 마주하게 될 테니 강제로 다른 알고리즘을 선택해야 한다(거의 반 강제다). 대표적인 방법은 DP(Dynamic Programming)가 있다. 값을 저장하여 계산의 횟수를 줄이는 방법이다.

 

입력받은 숫자 n에 대하여 각각 0,1이 몇번 등장하는지 값을 저장해 두면 메모리를 사용하는 대신 연산량을 줄일 수 있다.

 

 

코드

import sys
t = int(sys.stdin.readline().strip())

memo = {0:[1, 0], 1:[0,1]}   # key-val의 val은 [0의 개수, 1의 개수]

def fibonacci(n:int) -> int:
    for i in range(2, n + 1) :
        if i not in memo :
            memo[i] = [memo[i - 1][0] + memo[i - 2][0] , memo[i - 1][1] + memo[i - 2][1]]
    return memo[n]

for _ in range(t) :
    n = int(sys.stdin.readline().strip())
    answer = fibonacci(n) 
    print(answer[0], answer[1])

 

 

시간복잡도

dp를 사용하지 않고 재귀로 풀게 되면 fibonacci(n), fibonacci(n - 1), fibonacci(n - 2)...... n이 0 혹은 1이 될때까지 이어나가게 된다. 시간복잡도는 O(2^n)가 된다. 반면 dp를 사용하여 풀게 되면 입력받게 되는 t와 입력받는 숫자 n으로 O(t * n)가 된다. 문제에서 T의 범위는 주어지지 않았지만 N은 40보다 작거나 같은 자연수라 하였기에 O(T)의 시간복잡도라고 할 수 있다. 코딩테스트에서 보통 시간복잡도가 10^8승을 넘지 않으면 풀 수 있기 때문에 적당한 알고리즘을 택해 풀었다고 생각할 수 있겠다.

 

이 문제는 DP문제가 낯선 사람들에게 다이나믹 프로그래밍에 적응할 수 있는 문제라고 생각됐다. 처음 DP문제를 접하면 어떤 식으로 접근해야 할지 매우 난감한데 팁은 손으로 직접 몇 가지 경우의 수를 노트에 쓰거나 그려보는 걸 추천한다. dp는 결국 점화식을 구하는 것이 중요하기 때문이다.