백준 2747 - 피보나치 수 (파이썬)

www.acmicpc.net/problem/2747

2747번: 피보나치 수

오늘은 DP의 기본인 피보나치 수를 풀어봤다.

전에 풀어봤던 건데 top-down, bottom-up의 두가지 방식으로 다시 풀어봤다.

 

Top Down

# TOP DOWN
memo = {0:0, 1:1}

def fibo(n):
    if n in memo:
        return memo[n]
    else:
        memo[n] = fibo(n-1) + fibo(n-2)
        return memo[n]
print(fibo(int(input())))

 

먼저, top-down 방식은 딕셔너리로 초기 값을 저장해놓는다.

그리고 딕셔너리에 내가 찾는 값이 있는지 확인한 후

없다면 재귀함수를 통해 딕셔너리에 그 값을 저장한다.

 

 

 

Bottom Up

#BOTTOM UP
memo = {0:0, 1:1}

def fibo(n):
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]
    
print(fibo(int(input())))

 

bottom-up 방식도 마찬가지로 딕셔너리에 초기 값을 저장한다.

그리고 for문을 돌려서, 딕셔너리에 없는 가장 작은 값부터 그 값들을 쌓아나간다.

그러나 bottom-up 방식은 재귀함수를 쓰지 않는다.

오직 딕셔너리 값들에 의존하여 내가 원하는 값을 찾아나간다.