[python] 1003. 피보나치 함수

• 문제

---

 

• 잘못된 풀이

import sys
T = int(input())

cnt_0 = 0; cnt_1 = 0
def fibo(n):
    global cnt_0
    global cnt_1

    if n == 0:
        cnt_0 += 1
        return 0
    elif n == 1:
        cnt_1 += 1
        return 1
    else:
        return fibo(n-1) + fibo(n-2)


for i in range(T):
    n = int(sys.stdin.readline())
    result = fibo(n)
    print(cnt_0, cnt_1)
    cnt_0 = 0; cnt_1 = 0

 

나는 피보나치를 문제의 설명처럼 재귀(recursive)로 풀고자 하였다.

0과 1을 count하는 변수를 global로 선언하고 fibo() 함수에서 구하는 로직으로 문제를 해결하려고 하였다. 

 

하지만 재귀는 O(n^2)의 시간 복잡도를 가지고 있으므로, 시간초과로 문제풀이에 실패하였다.

따라서 해당 문제는 재귀보다 시간 복잡도가 더 낮은 방법으로 풀어야 한다.

 

일반적으로 피보나치를 푸는 방법으로 재귀와 반복문(배열 사용)이 있다. 

위의 방법처럼 재귀로 푸는 방법은 O(n^2)의 시간 복잡도를 가진다.

 

반복문으로 푸는 방법은 피보나치 수를 구하면 배열에 저장하고, 필요할 때마다 배열에서 불러오는 방법이다. 

이렇게 이미 구한 값을 배열에 저장해두고 필요할 때마다 불러와 다시 사용하는 방법을 memoization이라고 한다.

반복문으로 배열을 사용해서 푸는 방법은 O(n)의 시간 복잡도를 가진다.

 

 

 

• 올바른 풀이

import sys
T = int(input())

for i in range(T): 
    cnt_0 = [1, 0] 
    cnt_1 = [0, 1]

    n = int(sys.stdin.readline())
    if n>1 :
        for i in range(n-1):
            cnt_0.append(cnt_1[-1]) # 현재 0의 갯수 = 이전 1의 갯수
            cnt_1.append(cnt_0[-2]+cnt_1[-1]) # 현재 1의 갯수 = 이전 0 + 이전 1의 갯수
    print(cnt_0[n], cnt_1[n])

 

재귀 함수로만 문제를 풀려고 하면 시간 초과로 인한 오답 처리가 된다.

때문에 해당 문제는 다이나믹 프로그래밍을 통해 피보나치에서 호출되는 0과 1을 카운팅하는 문제이다.

 

피보나치는 이전 숫자와 그 이전 숫자를 더하는 함수이다. 

예를 들면, fibo(3) = fibo(2) + fibo(1)이라는 것이다.

하지만 해당 문제는 fibo 값을 구하는 것이 아닌, 특정 값의 fibo를 구하기 위해 호출되는 fibo(0)과 fibo(1)의 횟수를 구하는 문제이다.

결국, fibo(n)을 호출하면 fibo(0)과 fibo(1)은 fibo(n-1)의 0과 1 호출 횟수 + fibo(n-2)의 0과 1 호출횟수와 동일하다는 것이다.

 

위의 코드처럼 배열을 만들어서 값을 저장하는 이유는, 위에서 언급했던 이유와 같다.

다이나믹 프로그래밍을 통해 이미 구한 숫자를 또 다시 구하는 일이 없도록 하여 시간을 단축시키기 위함이다.