PostsSeriesLabsAlgo

DP

메모이제이션

같은 걸 두 번 세지 않기

fib(n) 은 바로 앞 두 값을 더한 수입니다. fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2 …

목표 fib(6) 의 값 구하기

먼저 맞혀 보세요. 값을 적어 두는 수첩을 쓰면 값을 계산하는 일은 몇 번일까요? (나무의 호출은 모두 25번입니다)

계산한 횟수 0 · 꺼내 쓴 횟수 0

내 예상 · 실제 7번 → 달랐어요

나무의 호출은 25번이었습니다. 수첩을 쓰니 호출은 11번으로 줄었습니다. 그중 계산은 0번, 수첩에서 꺼내 쓴 것은 0번이었습니다.

호출 25번 → 수첩에 적은 값 7개 → 계산 7번같은 값은 한 번만 계산했습니다. 두 번째부터는 수첩에서 꺼내 썼습니다.

  • 처음 나오는 값 — 계산해서 수첩에 적는다
  • 이미 적힌 값 — 다시 계산하지 않고 꺼내 쓴다. 그 아래 가지는 부르지도 않는다
  • 그래서 — 서로 다른 값의 개수만큼만 계산한다

한 번 구한 값을 적어 두었다가 다시 쓰는 방법 = 메모이제이션(memoization)

수첩 없이 fib(30)2,692,537번
수첩을 쓰면59번
호출 횟수. 수첩에는 값이 31개만 적힙니다.

수첩을 써도 되는 때

  • 같은 입력이면 같은 값 — 수첩에 적은 fib(2) = 1 은 언제 꺼내도 같았다. 값이 달라질 수 있으면 적어 둘 수 없다
  • 같은 계산이 되풀이된다 — 나무에서 fib(2) 가 5번 나왔다. 겹치지 않는 문제는 적어 둬도 꺼내 쓸 일이 없다
  • 입력으로 값을 찾는다 — 수첩은 입력(n)을 칸 이름 삼아 값을 찾는다. 앞서 본 해시가 이 일을 한다

코드는 수첩을 하나 더 들고 다니는 것뿐이다

fib(6, {}) 로 부르면 수첩은 빈 딕셔너리로 시작합니다. 다음을 눌러 한 줄씩 넘기며 층이 쌓이고 수첩이 채워지는 걸 보세요. 중간에 한 번 물어봅니다.

다음을 눌러 한 줄씩 넘겨 보세요

n = 6 len(memo) = 0

fib.py
  1. 1def fib(n, memo):
  2. 2 if n in memo:
  3. 3 return memo[n]
  4. 4 if n < 2:
  5. 5 memo[n] = n
  6. 6 return n
  7. 7 memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  8. 8 return memo[n]
0 / 27
  • if n in memo — 수첩에 있으면 여기서 끝난다. 아래 가지를 부르지 않는다
  • memo[n] = … — 구한 값을 돌려주기 전에 수첩에 적는다
  • 끝나면 — 호출 11번, 수첩에는 0 부터 6 까지 값이 하나씩 적혔다

코딩테스트에서는 한 줄이면 된다

  • @lru_cache(maxsize=None) — from functools import lru_cache 한 뒤 함수 위에 붙인다. 수첩은 파이썬이 대신 만들어 준다
  • 같은 결과 — fib(6) 은 8 이다. fib.cache_info() 로 보면 계산 7번, 꺼내 쓰기 4번으로 ① 에서 센 값과 같다

같은 방법으로 fib(7) 을 구하면 값을 계산하는 일은 몇 번일까요?

수첩을 써도 틀리거나 느려지는 자리

  • memo = {} 를 함수 안에 쓰면 — 부를 때마다 빈 수첩이 새로 생긴다. fib(20) 의 호출이 21,891번으로 수첩이 없을 때와 같다. 함수 밖에서 만들어 건네면 39번이다
  • 깊이는 그대로 — 수첩을 써도 재귀라서 fib(5000, {}) 는 RecursionError 를 낸다. 기본 한도가 1,000이다
  • lru_cache 는 인자가 해시 가능해야 한다 — 리스트를 넘기면 TypeError: unhashable type: 'list'. 튜플로 바꿔서 넘긴다
  • 값이 바뀌는 함수에는 쓰지 않는다 — 부를 때마다 1, 2, 3 을 세어 주는 함수를 캐시했더니 세 번 불러도 1, 1, 1 이었다. 함수는 1번만 돌았다

직접 재 보니 수첩 없이 fib(32) 에 약 0.182초, 수첩을 쓰면 약 0.000007초였습니다. 컴퓨터마다 다르니 비율만 보세요.

문제에서 이 말이 보이면

같은 계산이 반복된다부분 문제로 쪼개진다경우의 수·최댓값을 재귀로 쓴다

다음 장에서는 이 수첩을 위에서가 아니라 아래에서부터 채우는 1차원 DP 를 봅니다.