데코레이터 + @lru_cache 데코레이터를 활용한 DP 캐싱
데코레이터 개념
Decorators provide a simple syntax for calling higher-order functions.
By definition, a decorator is a function that takes another function and extends the behavior of the latter function without explicitly modifying it.
출저 : https://realpython.com/primer-on-python-decorators/
함수 A를 실행하기 전, 앞 뒤로 time.time()을 실행해서 실행 시간을 재고 싶을 때가 있다.
이때, A를 인자로 받아서 앞 뒤로 time.time() 처리를 해주는 다른 wrapper 함수 B를 만들 수 있지 않을까?
* 함수를 인자로 받거나 함수를 리턴하는 함수 - higher-order function
파이썬은 B를 '데코레이터'라는 이름의 기능으로 지원한다!
https://bluese05.tistory.com/30
Python에서 함수의 반환값을 알아서 캐싱해주는 데코레이터가 있다는 사실을 새로 알게 됨.
바로 @lru_cache !!
Top-down DP에 @Iru_cache 데코레이터를 써서 캐싱을 적용하였고,
generator 식에 next 함수를 써서 조건을 만족하는 가장 작은 k값을 뽑아낸 모습이다.
정말 아름답다.
class Solution:
def minSkips(self, dist, S, H):
@lru_cache(None)
def dp(i, k):
if k < 0: return float("inf")
if i < 0: return 0
return dist[i] + min(dp(i-1, k-1), (dp(i-1, k) + S - 1)//S*S)
if sum(dist) > S*H: return -1
n = len(dist)
return next(k for k in range(n+1) if dp(n - 1, k) <= H*S)
@Iru_cache는 간단한 DP에 충분히 써먹을 수 있을 것 같다.
Memo 체크하는 코드를 줄여서 훨씬 깔끔해질 것 같고.
공식 reference도 있다.
https://docs.python.org/ko/3/library/functools.html
단점 : 캐시 사이즈가 좀 커지면 속도가 매우매우 느려지는 듯 하다 (Cache hit? miss? 원리를 한번 봐야할 것 같은데)
N = 1000, O(N^2) 수준의 memoization도 엄청 오래 걸리는 듯. 참고하기
(LeetCode 26 M-1690. Stone Game VII)