[알고리즘] Dynamic Programming : 피보나치 수열(Memoization vs Tabulation)

다이나믹 프로그래밍 필요조건

1. 최적 부분구조 : 부분문제들의 최적의 답을 이용해서 기존문제의 최적의 답을 구할 수 있다는 것

-> 기존 문제를 부분 문제로 나눠서 풀수 있다. -> 중복되는 부분 문제들이 있을 수 있다.

2. 중복되는 부분 문제

 

다이나믹 프로그래밍 : 한 번 계산한 결과를 재활용 하는 방식

 

구현방법

1. Memoization : 중복되는 계산은 한 번만 계산 후 "메모" (Cache) / 재귀

 

실습설명

n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요.

fib_memo는 꼭 memoization 방식으로 구현하여야 합니다.

 

힌트1

Memoization 방식으로 문제를 풀면 재귀 함수를 사용하는데, 제귀 함수를 작성할 때 가장 먼저 생각해야 하는 두가지가 무엇인지 기억하나요?

 

힌트2

재귀 함수를 작성할 때에는 base case와 recursive case에 대해 생각해야 합니다.

recursive case : 현 문제가 너무 커서 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

base case : 이미 문제가 충분히 작아서 더 작은 부분 문제로 나누지않고도 바로 답을 알 수 있는 경우

 

힌트3

base case는 n이1이거나 2일 때입니다. 피보나치수열의 첫 번째 수와 두 번째 수는 그냥 1로 정해져 있습니다.

 

힌트4

def fib_memo(n, cache):   
    # base case
    if n < 3:
        return 1

힌트5

recursive case 에는 두가지 경우가 있습니다.

fib_memo(n, cache)를 호출했다고 가정했을때.

- 이미 n번째 피보나치 수를 계산한 경우, 즉 cache[n]이 존재하는 경우

- 이미 n번째 피보나치 수를 계산하지 않은 경우, 즉 cache[n]이 존재하지 않는 경우

 

답안

def fib_memo(n, cache):
    # base case
    if n < 3:
        return 1
        
    # 이미 n번째 피보나치를 계산했으면:
    # 저장된 값을 바로 리턴한다
    if n in cache:
        return cache[n]
    
    # 아직 n번째 피보나치 수를 계산하지 않았으면:
    # 계산을 한 후 cache에 저장
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)

    # 계산한 값을 리턴한다
    return cache[n]

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)

# 테스트 코드
print(fib(10))
print(fib(50))
print(fib(100))

 

 

 

 

2. Tabulation : table 방식으로 (반복문사용)

 

실습설명

n번째 피보나치 수를 찾아주는 fib_tab을 작성해보세요.

fib_tab는 꼭 tabulation 방식으로 구현하셔야 합니다!

 

힌트1

계산된 피보나치 수를 저장시켜 놓을 표가 필요합니다. 우리는 리스트를 표처럼 사용할 수 있겠죠. 그 리스트를 fib_table이라고 하겠습니다.

 

1번 피보나치 수는 1이고, 2번 피보나치 수도 1입니다. 0 번 피보나치 수는 그냥 0 이라고 합시다. 그러면 fib_table은 처음에 이렇게 정의 할 수 있습니다.

fib_table = [0, 1, 1]

이제 fib_table을 인덱스 3부터 인덱스 n까지 채워 나간 후에 리스트의 n번째 항목을 리턴하면 되겠죠?

 

힌트2

i가 2보다 큰경우, fib_table[i]에는 fib_table[i-1] + fib_table[i-2]가 들어갑니다.

 

답안

def fib_tab(n):
    # 이미 계산된 피보나치 수를 담는 리스트
    fib_table = [0, 1, 1]

    # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
    for i in range(3, n + 1):
        fib_table.append(fib_table[i - 1] + fib_table[i - 2])

    # 피보나치 n번째 수를 리턴한다
    return fib_table[n]

# 테스트 코드
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

 

Memoization vs Tabulation

공통점 : 중복되는 부분 문제의 비효율을 해결

차이점 : 재귀함수 사용과 반복문의 사용

Tabulation은 상향식 접근 법으로 필요없는 값까지 계산

Memoization 는 필요없는 값은 계산하지 않아도 됨