[백준 알고리즘]피보나치 수열(1003)

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

문제에 제시된 재귀함수를 수정하여 파이썬코드로 간단하게 해결해봤습니다.

zero = 0
one = 0

def fibonacci(n):
    if n == 0:
        global zero
        zero += 1
        return 0
    elif n == 1:
        global one
        one += 1
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

T = int(input())
for i in range(T):
    n = int(input())
    fibonacci(n)
    print(zero, " ", one)
    zero = 0
    one = 0

다만 이 코드로 제출했을 때 시간초과가 났습니다.

그래서 입력값이 40까지밖에 되지 않아서 시간을 단축시킬 수 있는 메모이제이션을 이용했습니다.

class FiboNum:
    def __init__(self):
        self.zero = -1
        self.one = 0

    def show(self):
        print(self.zero, self.one)

fibonacci(0)과 fibonacci(1)이 호출되는 횟수를 저장하도록 클래스를 만들었습니다.

처음에는 zero의 값을 -1로 초기화하여 이용할 수 없는 값임을 의미합니다.

show()함수는 객체의 필드값들을 출력하는 간단한 함수입니다.

fibo = [FiboNum() for i in range(41)]
fibo[0].zero = 1
fibo[1].one = 1
fibo[1].zero = 0

for i in range(2, 41):
    if fibo[i].zero != -1:
        continue
    else:
        fibo[i].zero = fibo[i-1].zero + fibo[i-2].zero
        fibo[i].one = fibo[i - 1].one + fibo[i - 2].one

0부터 40까지의 0과 1의 총 호출 횟수를 fibo리스트에 저장합니다.

메모이제이션을 이용하면 큰 메모리가 필요하지만 시간을 굉장히 단축시킬 수 있습니다.

예를 들어 

fibonacci(4)  = fibonacci(3) + fibonacci(2)

= [fibonacci(2) + fibonacci(1)] + [fibonacci(1) + fibonacci(0)]

= [{fibonacci(1) + fibonacci(0)} + fibonacci(1)] + [fibonacci(1) + fibonacci(0)]

를 계산한 후 fibonacci(5)를 구할경우

fibonacci(5)  = fibonacci(4) + fibonacci(3)

= [fibonacci(3) + fibonacci(2)] + [fibonacci(2) + fibonacci(1)]

= [{fibonacci(2) + fibonacci(1)} + {fibonacci(1) + fibonacci(0)] + [{fibonacci(1) + fibonacci(0)} + fibonacci(1)]

처럼 이미 구한 fibonacci(4)와 fibonacci(3)을 처음부터 다시 구하게 됩니다.

하지만 메모이제이션을 이용할 경우

fibonacci(5)  = fibonacci(4) + fibonacci(3) = (2, 3) + (1, 2) [편의상 (0횟수, 1횟수)로 표기했습니다.]

으로 앞에서 구했던 값들을 그대로 다시 이용하여 빠르게 값을 얻을 수 있습니다.

T = int(input())
for i in range(T):
    n = int(input())
    fibo[n].show()

이후 테스트케이스 갯수 T를 입력받고 입력값에 맞는 결과값을 출력합니다.

이미 메모이제이션을 이용하여 모든 값들을 구해놓은 것이므로 이 코드는 처음 실행했을 때 약간의 시간을 필요로 합니다.

그 이후에는 이미 있는 값들을 출력만 하는 것이므로 시간복잡도 O(1)임을 알 수 있습니다.

class FiboNum:
    def __init__(self):
        self.zero = -1
        self.one = 0

    def show(self):
        print(self.zero, self.one)

fibo = [FiboNum() for i in range(41)]
fibo[0].zero = 1
fibo[1].one = 1
fibo[1].zero = 0

for i in range(2, 41):
    if fibo[i].zero != -1:
        continue
    else:
        fibo[i].zero = fibo[i-1].zero + fibo[i-2].zero
        fibo[i].one = fibo[i - 1].one + fibo[i - 2].one

T = int(input())
for i in range(T):
    n = int(input())
    fibo[n].show()