TIL - DP 동적 프로그래밍 하향식, 피보나치 수열

문제

- 메모이제이션(Memoization)을 사용한 하향식 DP로 피보나치 수를 계산합니다.
- 이미 계산한 값을 저장하여 중복 계산을 방지합니다.

 

문제풀이

def fibonacci_memo(n, memo=None):
    """
    메모이제이션을 사용한 피보나치 (하향식 DP)
    
    Args:
        n: 피보나치 인덱스
        memo: 계산 결과를 저장할 딕셔너리
    
    Returns:
        n번째 피보나치 수
    """
    if memo is None:
        memo = {}
    
    if n < 2:
        return n
    
    if n in memo:
        return memo[n]
    
    else:
        val = fibonacci_memo(n - 1,memo) + fibonacci_memo(n - 2, memo)
        memo[n] = val
    
    return memo[n]

 

 

동적 프로그래밍에 대한 개념은 여기에 정리하였다.

다이나믹 프로그래밍 (DP) 정리

 

 

 

 

어려웠던 점

1. dict 자료형인 memo 의 사용
   • memo[n] 은 키가 딕셔너리에 없으면 KeyError 예외가 발생한다. 
   • memo.get[n] 은 키가 없으면 예외 대신 None 을 반환한다. 
   • dictionary .get(key, 기본값=None) 에서 key, 없을 때 기본값 지정할 수 있다.
   • 다 딕셔너티 조회라 시간복잡도는 O(1) 이다.

Python 에서 딕셔너리 dict 구현하기

if n in memo:
	return memo[n]
    
if memo.get(n) is not None:
	return memo[n]