WEEK04 - TIL DP 구현 / defaultdict

피보나치 수열 문제를 예시로,

def fibo(s):

    if s ==1 or s == 2:

        return 1

    if dp[s] != 0:

        return dp[s]

    dp[s] = fibo(s-1)+fibo(s-2)

    return dp[s]

print(fibo(n))

아래와 같이.

from collections import defaultdict
import sys

input = sys.stdin.readline

n = int(input())

dp = defaultdict(int)

def fibo(n):
    if n<=1:
        return n
    if dp[n]:
        return dp[n]
    dp[n] = fibo(n-1)+fibo(n-2)
    return dp[n]

print(fibo(n))

 

 

---

from collections import defaultdict

 

defaultdict는 이름 그대로 기본값을 지정한 딕셔너리

 

일반 딕셔너리는 key값을 미리 삽입하지 않으면 에러가 난다. 이땐 setdefault를 사용해 호출과 동시에 선언도 가능하다. 그치만 key를 넣을때마다 setdefault 함수를 써줘야 한다.

 

setdefault를 사용하지 않고, 호출과 동시에 미리 지정한 기본값이 할당되도록 선언할 수 있는 방법이 바로

defaultdict 함수

dp = defaultdict(int)

dp['c']+=1
# defaultdict(<class 'int'>, {'c': 1})

'c'는 존재하지 않았던 키라 원래의 딕셔너리라면 keyerror가 발생하지만, defaultdict 객체는 에러없이 바로 +1 연산이 가능하고 이 경우 디폴트인 0을 기준으로 자동으로 생성한 후 여기에 1을 더해 최종적으로 1이 만들어진다.