[알고리즘] 피보나치 수열의 항 찾기 (Fibonacci number) - 재귀, 메모이제이션, 변수 두 개를 이용한 최적화 방법

앞 글들에서 피보나치 수열의 문제를 풀어봤었습니다.

 

1. 재귀를 이용한 피보나치 수열

 

이렇게 재귀를 이용해서 풀면 너무 많은 중복 계산이 일어나서 성능이 안 좋습니다.

따라서 이미 해결한 문제는 메모리에 저장해서 나중에 필요할 때 뽑아서 쓰기로 했었습니다.

---

 

2. 반복문을 이용한 피보나치 수열

 

반복문을 이용하여 재귀를 쓰지 않고, 이미 계산한 값에 대해서 리스트에 저장했습니다.

이를 메모이제이션 기법이라고 합니다.

 

아래는 1번과 2번의 코드입니다.

 

n = int(input())    

def fib1(n):
    if n <= 1:
        return n
    else:
        return fib1(n-1) + fib1(n-2)


def fib2(n):
    if n <= 1:
        return n
    else:
        data = []
        data.append(0)
        data.append(1)
        for i in range(2, n+1):
            data.append(data[i-1] + data[i-2])
        return data[n]
    
print(fib1(n))
print(fib2(n))

 

 

2번을 쓰니 1번 보다 시간 복잡도는 줄어들었지만, 이 또한 메모리를 많이 잡아먹기 때문에 이제는 공간 복잡도를 줄이는 방법을 쓰겠습니다.

---

 

3. 변수 두 개를 이용한 피보나치 수열

 

제가 생각한 알고리즘은 이렇습니다.

 

1. 첫 번째 항과 두 번째 항을 더해 세 번째 항에 저장한다.

2. 네 번째 항부터 ~~ n 번째 항까지 구해야 하므로, 두 번째 항과 세 번째 항을 더해 첫 번재 항에 저장한다.

3. 그러면 첫 번째 항에 네 번째 값, 두 번째 항에 두 번째 값, 세 번째 항에 세 번째 값이 들어가 있으므로, 다섯 번째 항을 구하려면 세 번째 항과 첫 번째 항을 더한다.

4. 반복문이 끝날 때까지 무한 반복

 

이해가 되시나요? 아마 말로 쓰면 이해하기 힘들겁니다.

쉽게 설명해서 temp1, temp2를 만들고, data를 만듭니다. temp1 = 0, temp2 = 1입니다.

이때 data의 값은 항상 temp1 + temp2입니다.

그러면 이제 temp1, temp2, data에는 각각 0, 1, 1이 저장되어 있겠죠?

이때 다음 항은 '2'입니다! 

그럴려면 1+1을 해야하는데, 항상 저희가 하는 연산은 temp1 + temp2 밖에 없습니다.

그러면 어떻게 해야할까요?

 

바로 temp1 = temp2, temp2 = data를 하면 됩니다.

그러면 다음 항을 계산할 수 있겠죠. 이것이 가능한 이유는 기존의 temp1에 있던 0은 더 이상 쓸모가 없기 때문이죠.

 

그렇게 반복문들 돌다보면 결국 내가 원하는 n항의 값을 찾을 겁니다.

그때 return 하면 됩니다.

 

코드로 보여드리겠습니다.

 

n = int(input())

def fib3(n):
    if n <= 1:
        return n
    else:
        temp1 = 0
        temp2 = 1
        for i in range(2, n+1):
            data = temp1 + temp2
            temp1 = temp2
            temp2 = data
        return data

    
print(fib3(n))

간단하죠?

 

결국 시간도 빠르고, 공간도 적게 먹는 피보나치 수열이 완성 되었습니다.

 

기존의 2번과 3번을 비교하면,

 

10000
>>> 0.004057884216308594		# 2번
>>> 0.0016162395477294922		# 3번

두 배보다 더 빠른 시간 차이가 나네요

 

참고로 1번에 10,000을 넣으면 아마 평생 걸려도 못 찾으실겁니다..

---

 

4. 전체 코드

 

import time

n = int(input())    


def fib1(n):
    if n <= 1:
        return n
    else:
        return fib1(n-1) + fib1(n-2)


def fib2(n):
    if n <= 1:
        return n
    else:
        data = []
        data.append(0)
        data.append(1)
        for i in range(2, n+1):
            data.append(data[i-1] + data[i-2])
        return data[n]


def fib3(n):
    if n <= 1:
        return n
    else:
        temp1 = 0
        temp2 = 1
        for i in range(2, n+1):
            data = temp1 + temp2
            temp1 = temp2
            temp2 = data
        return data

    
print(fib1(n))
s = time.time()
print(fib2(n))
e = time.time()
print(e-s)

s = time.time()
print(fib3(n))
e = time.time()
print(e-s)

 

감사합니다.

 

지적 환영합니다.