백준 2748. 피보나치 수 2 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이

🔔 문제 설명은 백준 문제 링크로 대신합니다

2748번: 피보나치 수 2

 

피보나치 수열의 n번째 원소를 출력하는 문제이다. 이번 주 학습 주제인 동적프로그래밍과 그리디에 대해서 먼저 이론을 공부하고 문제를 풀었는데, 피보나치 수열은 동적프로그래밍의 너무나도 대표적인 예시라서 공부를 하는 과정 중에 먼저 코드를 이해할 수 있었고 문제를 금방 풀 수 있었다. 동적프로그래밍의 두 방식 메모이제이션(memoization)과 바텀업(bottom-up) 방식 모두로 풀어보았고, 예제의 수 범위가 크지 않아서 인지 두 방식 모두 동일한 메모리(30840kb)를 사용하고, 동일한 시간(68ms)이 소요되었다.

위가 바텀업, 아래가 메모이제이션 방식

 

1. 바텀업 | 상향식 접근 방식

N = int(input())

def fibonacci(n) :
    if n == 0 :
        return n
    a, b = 0, 1 # 초깃값 두 수 
    for i in range (1, N) :
        temp= a
        a = b
        b= temp+a
    return b

print(fibonacci(N))

상향식 접근 방식이란, 정말로 밑에서부터 하나씩 계산해서 올라가는 식이다. 0과 1을 더해서 1을, 다시 1과 1을 더해서 2를, 다시 1과 2를 더해서 3을 ... 이렇게 N-1번 반복하면서 피보나치 수열의 N 번째 값을 찾아가는 것이다. 

 

fibonacci 함수를 좀 더 풀어서 보자면

    if n == 0  :
        return n

인수가 0인 경우 ( 피보나치 수열의 0번째 값을 묻는 경우) 인수로 받은 n 값 0을 그대로 반환하면 된다. 

 

n이 0이 아니라면 피보나치를 계산할 두 수의 초깃값을 저장한다.

   a, b = 0, 1   # 초깃값 두 수

 

그리고 N-1번 반복문을 돌린다. range(1,N)이기 때문에 i는 1~N-1 까지이다. 굳이 range(N-2)가 아니라 range(1,N)으로 한 이유는 피보나치 수열의 1번째 값부터 반복문을 시작해서 N-1번째값까지 계산해서 N을 구해낸다는 게 드러나면 좀 더 직관적일 것 같아서! 
    for i in range (1, N) :
        temp= a
        a = b
        b= temp+a
    return b

a값인 0은 temp에 저장해두고, b의 값은 a에 저장한다. 이제 temp는 0, a는 1이다. 이 둘을 더한 값을 b에 저장하면, b는 피보나치 수열의 세번째 원소의 값을 갖게 된다. 이런 방식으로 새로운 원소를 N-1번 계산해 낸 뒤의 b값이 바로 피보나치 수열의 N번째 값이다. 

 

+ ) 이 문제를 푼 후에 DP를 좀 더 공부하다가, 상향식접근 방식을 좀더 DP스럽게(?) 푼 코드를 봐서 추가해놓는다! (출처)

d = [0]* (n+1) # DP 테이블 초기화 
d[1] = 1 # 피보나치 수열 1번 원소의 초깃값 저장 
d[2] = 1 # 피보나치 수열 2번 원소의 초깃값 저장 

for i in range(3, n+1):
     d[i] = d[i-1]+ d[i-2]

print(d[n])

 

2. 메모이제이션 방식

N = int(input())

def fibonacci(n, memo={}) :
    if n == 0 or n==1 :
        return n
    if not memo.get(n) : # memo 에 n 값이 없으면 
        memo[n] = fibonacci(n-2) + fibonacci(n-1) #재귀 후 해시테이블에 저장
    return memo[n]

print(fibonacci(N))

메모이제이션 방식은 재귀 호출을 통해 피보나치 수열의 값을 계산하고, 이때 memo라는 딕셔너리 자료형 변수에 계산값을 저장해두고 재귀 호출 전에 값을 먼저 확인하는 방식으로 불필요한 재귀호출을 줄이는 방식이다. 함수를 좀 더 풀어서 정리해보겠다. 

 

if n == 0 or n==1 :
        return n

인수가 0또는 1인 경우 ( 피보나치 수열의 0번째 또는 1번째 값을 묻는 경우) 인수로 받은 n 값을 그대로 반환하면 된다. 

    if not memo.get(n) :   # memo 에 n 값이 없으면 
        memo[n] = fibonacci(n-2) + fibonacci(n-1)  # 재귀 후 해시테이블에 저장 
    return memo[n]

딕셔너리 자료형의 .get(인수)은 딕셔너리에서 인수로 받은 키가 있는지 확인하고 키가 있으면 값을, 없으면 None을 반환한다. 따라서 not memo.get(n)을 통해 memo에 n값이 없으면 (not None은 True) 재귀 함수를 돌린 후, 이를 memo에 저장한다. memo에 n값이 있으면 재귀를 호출하지 않고 바로 값을 반환한다. 

 

한줄소감 : 동적프로그래밍 문제 중 처음 풀어 본 문제였는데, 생각보다 문제 없이 깔끔하게 풀 수 있어서 시작이 좋은 느낌이다! 

 

끝.