백준 1003 파이썬(DP - 피보나치함수)

피보나치 함수를 구하는 문제이다

보통 피보나치 수열은 재귀함수를 이용해서 구할 수 있다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    else:
        return fibo(x-1) + fibo(x-2)

이런 식으로 구할 수 있는데

문제는 숫자가 조금만 커지게되면 연산횟수가 급격하게 증가하고 그에 따라서 속도도 엄청 느려지게 된다.

 

이런 문제를 메모이제이션(재귀함수이용) 또는 반복문을 이용해서 해결할 수 있다.

 

메모이제이션은 이미 한번 연산을 했던 값은 따로 저장해뒀다가 필요할때마다 찾아서 쓴다는 아이디어다. 

말 그대로 따로 메모해둔다고 생각하면 된다.

 

반복문을 이용하는 방법은 작은 문제부터 하나하나씩 풀어나가는 방법이다.

결론적으로는 선형시간의 시간복잡도를 갖는다.

 

코드로 살펴보자.

• 바텀업 방식(반복문 이용)

# 1003번 피보나치 함수
# 바텀업
import sys
input = sys.stdin.readline

t = int(input())

number = [[0,0]] * (101)
def fibo(n):
    number[0] = [1,0]
    number[1] = [0,1]
    if n >= 2:
        for i in range(2,n+1):
            a = number[i-1][0] + number[i-2][0]
            b = number[i-1][1] + number[i-2][1]
            number[i] = [a,b]
    return number[n]

for _ in range(t):
    n = int(input())
    number = [[0,0]] * (101)
    f = fibo(n)
    print(f[0],f[1])

 

• 탑다운 방식(재귀 이용)

def fibo_memo(x):
    if x == 0:
        memo[x] = [1,0]
        return memo[x]
    elif x == 1:
        memo[x] = [0,1]
        return memo[x]
    elif x in memo:
        return memo[x]
    else:
        a = fibo_memo(x-1)[0] + fibo_memo(x-2)[0]
        b = fibo_memo(x-1)[1] + fibo_memo(x-2)[1]
        memo[x] = [a,b]
        return memo[x]

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    memo = {}
    f = fibo(n)
    print(f[0],f[1])

 

기본적으로 두 방법 모두 선형시간의 시간복잡도를 갖기 때문에 두가지 방법 모두 통과가 되었다.

바텀업방식은 반복문을 이용해서 작은 문제부터 풀어나가는 것이,

탑다운방식은 큰 문제에서 하나하나 쪼개면서 푸는데 분할한 작은 문제들을 어디에 따로 메모한다는 것이 핵심포인트이다.