← 전체 회차
A-043● Day 432026.06.18mediumleetcode #146neetcode150

LRU 캐시

#hash-table#linked-list#design#doubly-linked-list
↗ leetcode #146 · lru-cache
01

문제

· problem
P.043

LRU 캐시

↗ leetcode #146

Least Recently Used (LRU) 캐시의 제약을 따르는 데이터 구조를 설계하세요. LRUCache 클래스를 구현하세요: - LRUCache(int capacity): 양수 크기의 capacity로 LRU 캐시를 초기화합니다. - int get(int key): key가 존재하면 해당 값을 반환하고, 그렇지 않으면 -1을 반환합니다. - void put(int key, int value): key가 존재하면 해당 값을 업데이트합니다. 그렇지 않으면 key-value 쌍을 캐시에 추가합니다. 이 작업 후 키의 개수가 capacity를 초과하면 가장 최근에 사용되지 않은 키를 제거합니다. get과 put 함수는 각각 O(1) 평균 시간 복잡도로 실행되어야 합니다.

제약
  • · 1 ≤ capacity ≤ 3000
  • · 0 ≤ key ≤ 10^4
  • · 0 ≤ value ≤ 10^5
  • · At most 2 × 10^5 calls to get() and put()
  • · Both get() and put() must achieve O(1) time complexity
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
[null, null, null, 1, null, -1, null, -1, 3, 4]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    get() 작업이 캐시 순서를 변경해야 하는 이유는 무엇인가요?
  • ☐
    센티널 노드(left, right)를 사용하는 목적은 무엇인가요?
  • ☐
    해시맵과 이중연결리스트를 결합하는 이유는 무엇인가요?
  • ☐
    시간 스탬프 카운터만 사용하여 O(1) 성능을 얻을 수 있을까요?
  • ☐
    put()에서 기존 키를 업데이트할 때 노드를 재삽입하지 않으면 어떻게 될까요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 캐시 해시맵 초기화
○
self.cache = {}  # map key to node
○
self.cache = []
○
self.cache = None
○
self.cache = set()
step 2· 센티널 노드 생성
○
self.left, self.right = Node(0, 0), Node(0, 0)
○
self.left = self.right = None
○
self.left = Node(0, 0); self.right = self.left
step 3· 노드 연결 해제 (remove)
○
prev.next, nxt.prev = nxt, prev
○
prev.next = nxt
○
node.prev = None; node.next = None
○
nxt.prev = prev
step 4· 노드를 우측 끝에 삽입 (insert)
○
node.next, node.prev = nxt, prev
○
node.next, node.prev = self.left, self.left.next
○
node.prev = self.right; node.next = None
○
prev.next = node
step 5· Get: 노드를 제거하여 최근성 업데이트
○
self.remove(self.cache[key])
○
return self.cache[key].val
○
self.insert(self.cache[key]); return self.cache[key].val
step 6· Put: left 다음의 LRU 노드 식별
○
lru = self.left.next
○
lru = self.right.prev
○
lru = self.cache[min(self.cache.keys())]
○
lru = list(self.cache.values())[0]
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Node:
2
    def __init__(self, key, val):
3
        self.key, self.val = key, val
4
        self.prev = self.next = None
5
6
7
class LRUCache:
8
    def __init__(self, capacity: int):
9
        self.cap = capacity
10
        self.cache = {}  # map key to node
11
12
        self.left, self.right = Node(0, 0), Node(0, 0)
13
        self.left.next, self.right.prev = self.right, self.left
14
15
    # remove node from list
16
    def remove(self, node):
17
        prev, nxt = node.prev, node.next
18
        prev.next, nxt.prev = nxt, prev
19
20
    # insert node at right
21
    def insert(self, node):
22
        prev, nxt = self.right.prev, self.right
23
        prev.next = nxt.prev = node
24
        node.next, node.prev = nxt, prev
25
26
    def get(self, key: int) -> int:
27
        if key in self.cache:
28
            self.remove(self.cache[key])
29
            self.insert(self.cache[key])
30
            return self.cache[key].val
31
        return -1
32
33
    def put(self, key: int, value: int) -> None:
34
        if key in self.cache:
35
            self.remove(self.cache[key])
36
        self.cache[key] = Node(key, value)
37
        self.insert(self.cache[key])
38
39
        if len(self.cache) > self.cap:
40
            # remove from the list and delete the LRU from hashmap
41
            lru = self.left.next
42
            self.remove(lru)
43
            del self.cache[lru.key]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
→
[null, null, null, 1, null, -1, null, -1, 3, 4]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.