LRU 캐시 알고리즘 구현하기

LRU(Least Recently Used) 알고리즘은 가장 최근에 사용되지 않은 페이지를 교체하는 알고리즘입니다. 아래는 C++로 구현한 LRU 알고리즘 예시입니다.

 

 

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cacheList;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }
        auto it = cacheMap[key];
        cacheList.splice(cacheList.begin(), cacheList, it);
        return it->second;
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            auto it = cacheMap[key];
            it->second = value;
            cacheList.splice(cacheList.begin(), cacheList, it);
            return;
        }
        if (cacheMap.size() == capacity) {
            auto last = cacheList.back();
            cacheMap.erase(last.first);
            cacheList.pop_back();
        }
        cacheList.push_front(make_pair(key, value));
        cacheMap[key] = cacheList.begin();
    }
};

 

위의 구현에서, unordered_map은 각 키와 해당 키의 값이 저장된 캐시 요소를 가리키는 반면, list는 캐시 요소의 순서를 유지합니다. get() 함수는 해당 키를 찾아 캐시에서 가져오고, put() 함수는 캐시에 키와 값을 추가하며, 캐시의 크기가 초과되는 경우 가장 오래된 항목을 제거합니다.

이 구현을 사용하기 위해서는 LRUCache 클래스의 객체를 만들고 get() 및 put() 함수를 호출하면 됩니다. 예를 들어, 다음과 같이 사용할 수 있습니다.

 

위의 코드에서는 LRU 캐시의 용량이 2로 설정되어 있으며, 캐시에 각각 (1, 1), (2, 2) 값이 추가됩니다. 그런 다음 get(1) 함수를 호출하면 1을 반환하고, 이후 (3, 3)이 추가되며 캐시 용량이 초과되므로 (1, 1)이 캐시에서 제거됩니다. 그런 다음 get(2) 함수를 호출하면 -1을 반환합니다. 

 

그 이후 (4, 4)가 캐시에 추가되며, get(1) 함수를 호출하면 -1을 반환하고, get(3) 함수를 호출하면 3을 반환하며, 마지막으로 get(4) 함수를 호출하면 4를 반환합니다. 이렇게 LRU 알고리즘을 구현할 수 있습니다.

참고로, 위의 구현은 C++11 이상의 버전이 필요합니다. 만약 C++11 미만의 버전을 사용하고 있다면, auto 키워드 대신 list<pair<int, int> >::iterator와 같이 반복자 타입을 명시적으로 지정해주어야 합니다.