[알고리즘] 문제5 - Dynamic Programming

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.

 

Dynamic Programming

- 한 번 계산한 결과를 재활용하는 방식

- 최적 부분 구조가 있고, 중복되는 부분 문제들이 있다면 이 방식으로 해결

 

방식 1.  Memoization

- 한 번 계산한 결과를 저장해 놓았다가 사용하는 방식

- 하향식 접근

- 재귀 사용

방식 2. Tabulation

- 테이블(표)을 채워나가는 식으로 사용하는 방식

-상향식 접근

- 반복문 사용

---

 

 1. 피보나치 (Memoization)

 

 조건 

- 함수명 : fib_memo

- 매개변수명 : 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)

 

 조건 

- 함수명 : fib_tab

- 매개변수명 : n(구하고 싶은 수), cache(저장 값)

- n번째 피보나치 반환

---

풀이1 (공간최적화 X)

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))

 

풀이2 (공간최적화 O)

def fib_optimized(n):
    current = 1
    previous = 0

    for i in range(1, n):
        current, previous = current + previous, current

    return current


# 테스트
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))