LRU
-
Programmers Lv2) 캐시Algorithm/Programmers 2020. 8. 24. 19:57
출처: programmers.co.kr/learn/courses/30/lessons/17680 분류: Lv2 접근방식 LRU(Least Recently Used)의 개념을 알면 쉽게 풀 수 있는 문제입니다. LRU란 캐시를 관리하는 방법인데요, 캐시를 비울 때 가장 오래 사용되지 않은 녀석을 지우는 방식입니다. 만약 캐시의 크기가 4이고, [1, 2, 3, 4] 가 들어있을 때, 2가 추가로 들어온다면 2가 가장 최신에 사용된 것이 되므로 캐시는 [1, 3, 4, 2]로 변하게 됩니다. 만약 도시가 이미 캐시에 들어있다면 cache hit 이 되어 시간 1이 추가되고, 캐시에 없다면 chache miss가 되어 5가 추가됩니다. 저는 처음에 시간 복잡도를 생각해서 링크드 리스트와 딕셔너리를 섞어서 굉장히..