LRU Cache

Q: 순서가 있는 딕셔너리로 LRU 캐시를 만들 수 있나요?

네. Python의 OrderedDict 나 Java의 LinkedHashMap 처럼 삽입 순서를 유지하는 맵으로 리스트를 대체할 수 있습니다. 사용할 때마다 키를 끝으로 옮기고 앞에서 제거하면 여전히 O(1)입니다. 면접관은 보통 리스트를 직접 구현하기를 원합니다.

보통해싱 연결 리스트

+10

최대 capacity개의 키를 저장하는 캐시를 만드세요. get key는 해당 키의 값을 반환하고, 캐시에 없으면 -1을 반환합니다. put key value는 값을 저장하며, 기존 값이 있으면 바꿉니다. 키가 새 키이고 캐시가 가득 찬 경우, 가장 오랫동안 사용되지 않은 키를 먼저 제거합니다. 키를 찾은 get과 모든 put은 사용으로 간주합니다.

연산 i는 키 keys[i]에 대한 ops[i]("get" 또는 "put")이며, 값은 values[i]입니다(get의 경우 0). 빈 캐시에서 연산을 순서대로 실행하고, 각 연산마다 문자열 하나를 반환하세요. put의 경우 "null"을, get의 경우 값 또는 "-1"을 반환합니다.

함수

lruCacheOps(capacity: integer, ops: string-array, keys: integer-array, values: integer-array) → string-array

capacityinteger: 캐시가 한 번에 보유할 수 있는 최대 키 개수
opsstring-array: 연산이 실행되는 순서
keysinteger-array: 각 연산이 작동하는 키
valuesinteger-array: 각 put의 값, 각 get의 경우 0
반환값string-array: 연산마다 답 하나를 텍스트로

제약 조건

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
모든 ops[i]는 get 또는 put입니다.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹는 put의 경우이고, get의 경우에는 values[i] == 0입니다.

예제

입력: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
출력: ["null", "null", "10", "null", "-1", "30"]
설명: get으로 인해 키 1이 가장 최근에 사용된 키가 되므로, put 3은 키 2를 제거합니다. get 2는 "-1"을 반환하고 get 3은 "30"을 반환합니다.

입력: capacity = 2ops = ["put", "put", "put", "put", "get", "get", "get"]keys = [5, 6, 5, 7, 5, 6, 7]values = [1, 2, 3, 4, 0, 0, 0]
출력: ["null", "null", "null", "null", "3", "-1", "4"]
설명: 세 번째 put은 이미 캐시된 키 5를 업데이트합니다. 아무것도 제거되지 않고 키 5가 가장 최근에 사용된 항목이 됩니다. 따라서 put 7은 키 5가 아니라 키 6을 제거합니다.

입력: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
출력: ["-1", "null", "0", "null", "-1", "8"]
설명: 키를 하나만 저장할 수 있으므로, 새 키가 들어올 때마다 이전 키가 밀려납니다. 빈 캐시에서 첫 번째 get은 캐시 미스가 발생하고, 그다음 키 0은 put 8이 해당 키를 밀어낼 때까지 실제 값 0을 저장합니다.

후속 질문

캐시가 가장 적게 사용된 키를 대신 제거하도록 어떻게 바꾸고, 사용 빈도가 같으면 가장 오랫동안 사용되지 않은 키를 제거하면서 각 작업을 O(1)에 수행할 수 있을까요?

풀이

get은 키를 빠르게 찾아야 하고, 퇴거는 가장 최근에 사용되지 않은 키를 빠르게 찾아야 합니다. 해시 맵은 첫 번째를, 사용 순서대로 정렬된 리스트는 두 번째를 처리합니다. 둘 다 사용하세요. 각 키를 사용 순서대로 정렬된 이중 연결 리스트의 노드에 매핑하면 됩니다.

마지막으로 사용된 시간을 기준으로 항목 테이블을 스캔합니다

핵심 아이디어

배열에 최대 capacity개의 항목을 저장합니다. 항목은 키, 값, 그리고 모든 작업마다 증가하는 카운터에서 가져온 마지막 사용 시각 스탬프입니다. 캐시가 꽉 찬 상태에서 새 키가 들어오면 스탬프가 가장 작은 항목, 즉 가장 오랫동안 사용되지 않은 키를 덮어씁니다. 첫 번째 예시에서 put 3 시점에 키 1의 스탬프는 3이고 키 2의 스탬프는 2이므로 키 2가 제거됩니다.

모든 작업은 최대 capacity개의 항목을 검색합니다. 작업이 n개라면 O(n × capacity)이며, 키가 1,500개인 캐시에서 작업이 3,000번이면 수백만 번 비교하게 됩니다.

알고리즘

keys, values, used 배열과 채워진 항목 수, 그리고 0으로 설정된 시계를 유지합니다.
각 작업은 시계에 1을 더하고, 키가 있는지 채워진 항목을 검색합니다.
get: 찾지 못하면 -1을 반환하고, 찾으면 used를 시계 값으로 설정한 뒤 값을 반환합니다.
put: 찾으면 값을 저장하고 시계 값도 저장합니다. 찾지 못하면 빈 항목이나 used가 가장 작은 항목에 키, 값, 시계 값을 기록합니다.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        # Entry i holds keys[i] -> values[i] and was last used at time used[i].
        self.keys = [0] * capacity
        self.values = [0] * capacity
        self.used = [0] * capacity
        self.size = 0
        self.time = 0

    def _find(self, key):
        for i in range(self.size):
            if self.keys[i] == key:
                return i
        return -1

    def get(self, key):
        self.time += 1
        i = self._find(key)
        if i == -1:
            return -1
        self.used[i] = self.time
        return self.values[i]

    def put(self, key, value):
        self.time += 1
        i = self._find(key)
        if i == -1:
            if self.size < self.capacity:
                i = self.size
                self.size += 1
            else:
                # Full: scan for the entry used longest ago and take its place.
                i = 0
                for j in range(1, self.capacity):
                    if self.used[j] < self.used[i]:
                        i = j
            self.keys[i] = key
        self.values[i] = value
        self.used[i] = self.time

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

해시 맵과 이중 연결 리스트

핵심 아이디어

각 리스트 노드는 양쪽 이웃을 모두 가리키므로, 노드를 가지고 있으면 링크 네 개를 변경해 노드를 연결 해제하거나 맨 앞에 삽입할 수 있습니다. 맵이 노드를 찾아 주므로 어떤 연산도 리스트를 순회하지 않습니다.

get이 캐시에 적중하거나 캐시된 키를 put하면 노드가 맨 앞으로 이동합니다. 캐시가 가득 찬 상태에서 새 키가 추가되면 맨 뒤 노드를 제거하고 해당 키를 맵에서 삭제합니다. 그래서 각 노드는 자신의 키를 저장합니다. 센티널 노드 head와 tail은 양 끝에 그대로 있으므로, 연결을 해제하거나 삽입할 때 이웃 노드가 없는지 확인할 필요가 없습니다. 각 연산은 조회 한 번과 몇 번의 링크 변경으로 이루어집니다: O(1).

알고리즘

센티널 head와 tail을 연결하고, 키에서 노드로 매핑하는 빈 맵을 시작합니다.
get key: 키가 맵에 없으면 -1을 반환합니다. 그렇지 않으면 해당 노드를 head 다음으로 옮기고 값을 반환합니다.
캐시된 키의 put: 값을 저장하고 노드를 head 다음으로 옮깁니다.
새 키의 put: 맵에 capacity개의 키가 있으면 tail 앞의 노드를 연결 해제하고 맵에서 해당 키를 삭제합니다. 새 노드를 head 다음에 삽입하고 키를 해당 노드에 매핑합니다.

class ListNode:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}            # key -> its node in the list
        # Sentinels: head.next is the most recently used node,
        # tail.prev the least recently used one.
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                # Full: drop the least recently used node.
                oldest = self.tail.prev
                self._unlink(oldest)
                del self.nodes[oldest.key]
            node = ListNode(key, value)
            self.nodes[key] = node
        self._push_front(node)

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

함정과 경계 사례

get 적중 시 키를 맨 앞으로 이동하지 않는 경우. 첫 번째 예시에서는 put 3이 키 2가 아니라 키 1을 제거하게 됩니다.
키가 캐시되어 있는지 확인하기 전에 제거하는 경우. 용량이 2일 때 put 1, put 2, put 2를 실행하면 키 1이 제거됩니다.
노드의 연결을 해제했지만 맵에는 해당 키를 남겨 두거나, 그 반대로 하는 경우. 그러면 맵이 분리된 노드를 반환하고, 그 노드를 이동하면 이전 이웃 노드들의 연결이 손상됩니다.
저장된 0을 캐시 미스로 취급하는 경우. 세 번째 예시에서 get 0은 "0"을 반환해야 합니다.

자주 묻는 질문3

LRU 캐시의 시간 복잡도는 얼마인가요?

해시 맵과 이중 연결 리스트를 사용하면 조회와 삽입 모두 O(1)에 실행됩니다. 조회 한 번과 몇 번의 링크 변경만 필요합니다. 공간 복잡도는 O(capacity)이며, 키마다 노드 하나와 맵 항목 하나가 필요합니다.

LRU 캐시는 왜 이중 연결 리스트를 사용하나요?

캐시는 순서의 어느 위치에 있는 키든 맨 앞으로 옮기고 맨 뒤에 있는 키를 제거합니다. 이중 연결 리스트는 각 노드가 이전 노드를 알고 있으므로 링크 몇 개만 변경하면 두 작업을 모두 수행합니다. 단일 연결 리스트에서는 해당 노드를 찾으려면 헤드부터 순회해야 하며, 이는 O(capacity)입니다.

순서가 있는 딕셔너리로 LRU 캐시를 만들 수 있나요?

네. Python의 OrderedDict나 Java의 LinkedHashMap처럼 삽입 순서를 유지하는 맵으로 리스트를 대체할 수 있습니다. 사용할 때마다 키를 끝으로 옮기고 앞에서 제거하면 여전히 O(1)입니다. 면접관은 보통 리스트를 직접 구현하기를 원합니다.

def lruCacheOps(capacity, ops, keys, values):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

capacity = 2
ops = ["put", "put", "get", "put", "get", "get"]
keys = [1, 2, 1, 3, 2, 3]
values = [10, 20, 0, 30, 0, 0]

예상 출력

["null", "null", "10", "null", "-1", "30"]