10-lru-cache

10. LRU 캐시 (Least Recently Used Cache)

📋 문제 정의

가장 최근에 사용되지 않은 항목을 먼저 제거하는 캐시를 구현하세요.

LRU 캐시는 제한된 용량 내에서 데이터를 캐싱하며, 용량이 가득 찼을 때 가장 오래 전에 사용된 항목을 제거합니다.

---

🎯 학습 목표

• 해시맵과 이중 연결 리스트의 조합
• O(1) 시간 복잡도의 get/put 구현
• 캐시 교체 정책 이해
• 실무에서의 캐시 활용

---

📝 요구사항

기본 연산

메서드	설명	시간복잡도
get(key)	키에 해당하는 값 반환, 없으면 -1 (또는 null)	O(1)
put(key, value)	키-값 쌍 저장, 이미 있으면 업데이트	O(1)
remove(key)	키에 해당하는 항목 제거	O(1)
size()	현재 저장된 항목 개수	O(1)
capacity()	최대 용량	O(1)
clear()	모든 항목 제거	O(1)

동작 규칙

1. get(key): 키가 존재하면 해당 항목을 가장 최근 사용으로 표시
2. put(key, value):
   • 키가 이미 존재하면 값 업데이트 + 최근 사용으로 표시
   • 새 키이고 용량이 가득 찼으면 LRU 항목 제거 후 삽입
3. 용량은 생성 시 고정

추가 기능 (선택)

메서드	설명
peek(key)	값 조회만 (사용 기록 갱신 안 함)
containsKey(key)	키 존재 여부 확인
getOldest()	가장 오래된 항목 조회
getNewest()	가장 최근 항목 조회
keys()	모든 키 반환 (최근 순서)
values()	모든 값 반환 (최근 순서)

---

📊 입출력 예시

예제 1: 기본 사용

LRUCache cache = new LRUCache(3);  // 용량 3

cache.put(1, 100);
cache.put(2, 200);
cache.put(3, 300);
// 현재 상태: [1, 2, 3] (1이 가장 오래됨)

cache.get(1);  // 100 반환, 1을 최근으로 이동
// 현재 상태: [2, 3, 1] (2가 가장 오래됨)

cache.put(4, 400);  // 용량 초과! 가장 오래된 2 제거
// 현재 상태: [3, 1, 4]

cache.get(2);  // -1 반환 (제거됨)
cache.get(3);  // 300 반환

예제 2: 값 업데이트

LRUCache cache = new LRUCache(2);

cache.put(1, 100);
cache.put(2, 200);
// 상태: [1, 2]

cache.put(1, 111);  // 기존 키 업데이트 + 최근으로 이동
// 상태: [2, 1]

cache.put(3, 300);  // 용량 초과, 2 제거
// 상태: [1, 3]

cache.get(1);  // 111 반환 (업데이트된 값)
cache.get(2);  // -1 반환 (제거됨)

예제 3: 제네릭 버전

LRUCache<String, User> userCache = new LRUCache<>(100);

userCache.put("user:123", new User("Alice"));
userCache.put("user:456", new User("Bob"));

User alice = userCache.get("user:123");  // User 객체 반환
User unknown = userCache.get("user:999");  // null 반환

---

🔍 제약 조건

• 용량은 1 이상
• 키는 null 허용하지 않음 (구현에 따라)
• 값은 null 허용 가능 (구현에 따라)
• 모든 연산은 O(1) 시간 복잡도

---

💡 힌트

자료구조 조합

해시맵 (HashMap): key → Node 빠른 조회
이중 연결 리스트 (Doubly Linked List): 순서 관리, O(1) 이동/삭제

    HashMap
    ┌───────┐
    │ 1 → ●─┼──→ [Node: key=1, val=100]
    │ 2 → ●─┼──→ [Node: key=2, val=200]
    │ 3 → ●─┼──→ [Node: key=3, val=300]
    └───────┘
    
    이중 연결 리스트 (head = 최근, tail = 오래됨)
    
    head ←→ [1,100] ←→ [2,200] ←→ [3,300] ←→ tail
    (newest)                              (oldest/LRU)

노드 구조

class Node {
    int key, value;
    Node prev, next;
}

핵심 연산

// 노드를 맨 앞(head)으로 이동
void moveToHead(Node node) {
    removeNode(node);
    addToHead(node);
}

// 노드 제거 (O(1))
void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

// 맨 앞에 추가 (O(1))
void addToHead(Node node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}

// LRU 항목 제거 (tail 바로 앞)
Node removeTail() {
    Node lru = tail.prev;
    removeNode(lru);
    return lru;
}

---

✅ 체크리스트

• 기본 get, put 구현 (O(1))
• 용량 초과 시 LRU 제거
• 값 업데이트 시 최근 사용으로 이동
• 더미 head/tail로 엣지 케이스 처리
• 제네릭 버전 구현
• Thread-safe 버전 (선택)

---

📚 참고

• LeetCode 146. LRU Cache
• Java의 LinkedHashMap의 removeEldestEntry()
• Redis의 maxmemory-policy
• CPU 캐시의 LRU 정책