LRU 연습 문제

네 문제는 기본 LRU 캐시를 면접과 실무에서 자주 나오는 방향으로 넓힙니다. 접근 방법을 읽기 전에 먼저 풀어 보세요. 아이디어에 집중하도록 풀이는 OrderedDict를 쓰며, 구현 장에서 직접 만든 연결 리스트로 바꿔도 됩니다.

문제 1: 실패 횟수 세기

프로그램이 페이지 요청을 차례로 보내고, 메모리는 LRU로 관리하는 페이지 k개를 담습니다. 실패(페이지 폴트) 횟수를 구하세요. 이어서 실패 횟수가 주어진 한도 이하가 되는 가장 작은 k를 구하세요.

접근: 용량마다 캐시를 한 번 시뮬레이션합니다. LRU는 스택 알고리즘이라 k가 커져도 실패가 늘지 않으므로, 가장 작은 k는 1..서로 다른 페이지 수 범위에서 이분 탐색으로 찾을 수 있습니다.

from collections import OrderedDict

def lru_misses(requests, k):
    cache, misses = OrderedDict(), 0
    for page in requests:
        if page in cache:
            cache.move_to_end(page)
        else:
            misses += 1
            cache[page] = True
            if len(cache) > k:
                cache.popitem(last=False)
    return misses

def smallest_capacity(requests, limit):
    lo, hi = 1, max(1, len(set(requests)))
    while lo < hi:
        mid = (lo + hi) // 2
        if lru_misses(requests, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo

reqs = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4]
print(lru_misses(reqs, 3))         # 8
print(smallest_capacity(reqs, 7))  # 4

문제 2: 만료 시간이 있는 LRU

모든 항목이 저장된 뒤 ttl초가 지나면 만료되도록 캐시를 확장하세요. 만료된 항목은 없는 항목처럼 동작해야 합니다. 잠들지 않고도 테스트할 수 있도록 시계를 바꿔 끼울 수 있어야 합니다.

접근: (값, 만료 시각)을 저장합니다. get에서 만료 여부를 확인하고 낡은 항목은 그때 지웁니다(게으른 만료). 용량 초과 시 제거는 여전히 LRU 순서를 따릅니다. 게으른 만료는 두 연산을 O(1)로 유지하는 대신, 만료된 항목이 읽히거나 제거될 때까지 자리를 차지할 수 있습니다. Redis도 주기적인 능동 만료와 함께 같은 절충을 씁니다.

import time
from collections import OrderedDict

class TTLLRUCache:
    def __init__(self, capacity, ttl, clock=time.monotonic):
        self.capacity, self.ttl, self.clock = capacity, ttl, clock
        self.data = OrderedDict()            # 키 -> (값, 만료 시각)

    def get(self, key, default=None):
        item = self.data.get(key)
        if item is None:
            return default
        value, expires_at = item
        if self.clock() >= expires_at:
            del self.data[key]               # 게으른 만료
            return default
        self.data.move_to_end(key)
        return value

    def put(self, key, value):
        self.data[key] = (value, self.clock() + self.ttl)
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

now = [0.0]
c = TTLLRUCache(2, ttl=10, clock=lambda: now[0])
c.put("a", 1)
now[0] = 5;  print(c.get("a"))   # 1
now[0] = 11; print(c.get("a"))   # None (만료)

문제 3: 바이트 한도 캐시

항목마다 크기가 다르고, 캐시에는 항목 수 대신 바이트 예산이 있습니다. 값을 넣을 때 새 값이 들어갈 때까지 가장 오래전에 쓴 항목부터 제거해야 합니다. 예산 전체보다 큰 값은 아예 캐시하지 않습니다.

접근: 사용 중인 바이트 합계를 유지합니다. 삽입이나 갱신 뒤 합계가 예산을 넘는 동안 가장 오래전 쪽에서 꺼냅니다. 각 항목은 들어온 뒤 많아야 한 번 제거되므로 연산당 분할 상환 O(1)입니다.

from collections import OrderedDict

class ByteLRU:
    def __init__(self, max_bytes):
        self.max_bytes, self.used = max_bytes, 0
        self.data = OrderedDict()            # 키 -> 바이트열

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, blob):
        if len(blob) > self.max_bytes:
            return False
        if key in self.data:
            self.used -= len(self.data.pop(key))
        self.data[key] = blob
        self.used += len(blob)
        while self.used > self.max_bytes:
            _, old = self.data.popitem(last=False)
            self.used -= len(old)
        return True

b = ByteLRU(10)
b.put("x", b"12345"); b.put("y", b"1234"); b.get("x")
b.put("z", b"123")              # 12바이트: "y" 제거
print(list(b.data), b.used)     # ['x', 'z'] 8

문제 4: 크기 제한이 있는 메모이제이션

막힌 칸이 있는 격자에서 경로 수를 세는 재귀 함수가 있습니다. 크기 제한이 있는 LRU 캐시로 메모이제이션하고 적중률을 보고하세요. 그리고 maxsize가 너무 작으면 왜 함수가 느려지는지 설명하세요.

접근: 함수에 functools.lru_cache(maxsize=...)를 붙이고 cache_info()를 읽습니다. 재귀는 최근에 푼 부분 문제를 다시 찾으므로 작은 캐시도 도움이 되지만, maxsize가 동시에 살아 있어야 하는 부분 문제 수보다 작으면 캐시가 항목을 계속 밀어내(스래싱) 대부분의 호출이 실패합니다.

from functools import lru_cache

BLOCKED = {(1, 1), (2, 3)}
ROWS, COLS = 6, 6

@lru_cache(maxsize=64)
def paths(r, c):
    if (r, c) in BLOCKED or r >= ROWS or c >= COLS:
        return 0
    if (r, c) == (ROWS - 1, COLS - 1):
        return 1
    return paths(r + 1, c) + paths(r, c + 1)

print(paths(0, 0))
info = paths.cache_info()
print(f"hit ratio {info.hits / (info.hits + info.misses):.2f}")

정리

• 시뮬레이션과 LRU의 스택 성질을 이용하면 용량 계획을 이분 탐색으로 풀 수 있습니다.
• TTL, 바이트 예산, 메모이제이션은 모두 같은 순서 있는 맵을 조금씩 확장한 것입니다.
• 갱신, 너무 큰 값, 아주 작은 용량이 들어올 때 어떻게 되는지 항상 따져 봅니다.