O(1) get과 put을 갖는 LRU cache를 어떻게 설계하나요?

Question

Accepted Answer

**LRU(Least Recently Used, 최근 최소 사용) cache**는 용량에 도달하면 가장 오랫동안 접근되지 않은 항목을 축출합니다. 고전적인 설계는 **hash map**(O(1) 조회)과 **doubly linked list**(O(1) 재정렬)를 결합하여 **O(1) get과 put**을 제공합니다. ## 두 구조 설계 ```text HashMap: key -> node DLL (최근성 순서): MRU <-> ... <-> LRU get/put: map이 O(1)에 접근된 노드를 앞(MRU)으로 이동 노드를 찾음; DLL이 O(1)에 가득 차면 tail(LRU)을 축출 앞으로 splice함 ``` ## 코드 ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # 접근 순서를 보존함 def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # 가장 최근 사용으로 표시 return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # 최근 최소 사용 축출 ``` `OrderedDict`는 그 자체로 hash map에 doubly linked list를 더한 것으로, 위에서 설명한 바로 그 구조입니다. | 연산 | 시간 | |---|---| | get | O(1) | | put | O(1) | | 공간 | O(capacity) | ## 왜 doubly linked list인가 doubly linked list는 **중간에서 노드를 O(1)에 떼어낼 수 있게** 합니다(노드의 `prev`/`next`를 가지고 있으므로). 이는 singly linked list나 array에서는 O(n) 이동 없이 불가능합니다. ## 왜 중요한가 LRU cache는 데이터베이스, 웹 서버, CPU 앞에 위치하여 핫 데이터를 빠르게 유지하고 메모리를 제한합니다. 이 문제는 시니어 면접의 단골인데, 두 구조를 결합하여 *서로의 약점을 보완하게* 하는 능력을 시험하기 때문입니다. 이는 핵심 시스템 설계 기술입니다.