LRU를 사용하여 LFU 구현

I’m happy to help translate the article, but I’ll need the full text you’d like translated. Could you please paste the content (excluding the source line you already provided) here? Once I have the article, I’ll translate it into Korean while preserving the original formatting, markdown, and any code blocks or URLs.

📌 Core Idea

LFU (Least Frequently Used) means:

• Remove the least frequently used key.
• If multiple keys have the same frequency → remove the least recently used (LRU) among them.

📦 사용된 데이터 구조

• key → node (O(1) 접근을 위해)
• freq → doubly linked list (노드를 빈도별로 그룹화)
• minFreq (캐시에서 최소 빈도를 추적)

🧱 구조 시각화

Freq = 1 → [ most recent … least recent ]
Freq = 2 → [ most recent … least recent ]
Freq = 3 → [ most recent … least recent ]

각 주파수는 자체 LRU 리스트를 가집니다.

🚀 예시 진행 과정

용량 = 2

1. put(1,10)

   • Freq 1: [1]
   • minFreq = 1

2. put(2,20)

3. get(1) → 키 1에 접근

   • 빈도 증가: 1 → 2
   • Freq 1: [2] Freq 2: [1]
   • minFreq = 1

4. put(3,30) (캐시 가득)

   • minFreq = 1 → freq 1에서 LRU(2)를 제거
   • 삽입 후:
     • Freq 1: [3] Freq 2: [1]
     • minFreq = 1

5. get(3) → 3을 freq 1에서 freq 2로 이동

   • Freq 1: [] Freq 2: [3, 1]
   • minFreq = 2 (freq 1이 비어 있음)

6. put(4,40) (캐시 가득)

   • minFreq = 2 → freq 2에서 LRU(1)를 제거
   • 삽입 후:
     • Freq 1: [4] Freq 2: [3]
     • minFreq = 1

🔥 주요 관찰

1. 왜 여러 개의 리스트가 필요한가?
   서로 다른 빈도는 하나의 리스트에 저장할 수 없으며, 각 빈도마다 자체적인 LRU 순서를 유지합니다.

2. 왜 minFreq인가?
   이를 통해 O(1) 시간에 제거할 리스트를 찾을 수 있습니다.

3. 왜 이중 연결 리스트인가?
   동일한 빈도 내에서 LRU 순서를 유지하면서 O(1) 시간에 삭제할 수 있게 해줍니다.

🧠 정신 모델

LFU를 책이 놓인 선반에 비유해 보세요:

• 선반 1 → 가장 적게 사용된 책
• 선반 2 → 적당히 사용된 책
• 선반 3 → 가장 많이 사용된 책

제거할 때는 가장 적게 사용된 선반을 선택하고, 해당 선반에서 가장 오래된 책을 버립니다.

🧩 Mapping to Code

🚨 일반적인 실수

빈도 리스트가 비게 되면 minFreq를 업데이트해야 합니다:

if (freq == minFreq && list->size == 0)
    minFreq++;

minFreq를 업데이트하지 않으면 교체(eviction)가 정상적으로 동작하지 않습니다.

코드

class LFUCache {
public:
    class Node {
    public:
        int key, val, freq;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), freq(1), prev(nullptr), next(nullptr) {}
    };

    class List {
    public:
        Node* head;
        Node* tail;
        int size;
        List() : size(0) {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head->next = tail;
            tail->prev = head;
        }
        void addFront(Node* node) {
            Node* nxt = head->next;
            node->next = nxt;
            node->prev = head;
            head->next = node;
            nxt->prev = node;
            ++size;
        }
        void removeNode(Node* node) {
            Node* prv = node->prev;
            Node* nxt = node->next;
            prv->next = nxt;
            nxt->prev = prv;
            --size;
        }
    };

    int cap;
    int minFreq;
    unordered_map keyNode;   // key → node
    unordered_map freqList;  // freq → DLL

    LFUCache(int capacity) : cap(capacity), minFreq(0) {}

    void updateFreq(Node* node) {
        int f = node->freq;
        freqList[f]->removeNode(node);
        if (f == minFreq && freqList[f]->size == 0)
            ++minFreq;

        ++node->freq;
        if (!freqList.count(node->freq))
            freqList[node->freq] = new List();
        freqList[node->freq]->addFront(node);
    }

    int get(int key) {
        if (!keyNode.count(key)) return -1;
        Node* node = keyNode[key];
        updateFreq(node);
        return node->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (keyNode.count(key)) {
            Node* node = keyNode[key];
            node->val = value;
            updateFreq(node);
            return;
        }
        if (keyNode.size() == cap) {
            List* list = freqList[minFreq];
            Node* evict = list->tail->prev;
            keyNode.erase(evict->key);
            list->removeNode(evict);
        }
        Node* newNode = new Node(key, value);
        minFreq = 1;
        if (!freqList.count(1))
            freqList[1] = new List();
        freqList[1]->addFront(newNode);
        keyNode[key] = newNode;
    }
};