[C++로 풀이] 캐시 (std::list, 연결리스트, LRU 알고리즘)⭐⭐

Date: 2021.02.01 Updated: 2021.02.01

카테고리: Programmers

태그: Coding Test Algorithm

📌 캐시

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

✈ LRU 캐싱 알고리즘

가장 오랫동안 사용 안한 것이 캐싱 큐의 가장 앞에 있어야 한다.
가장 최근에 사용한 것이 캐싱 큐의 가장 뒤에 있어야 한다.
사용하려는 대상이 💜캐싱 큐에 존재한다면 (즉, 캐시가 있다면) 새롭게 로드할 필요 없이 이 캐싱 큐에 있는 것을 재활용하면 된다. 오브젝트 풀링처럼!
- 💜캐싱 큐에서 해당 캐시를 빼내온다. (중간 삭제)
- 뺴내와서 사용 후
- 💜가상 최근에 사용한 것이므로 캐싱 큐의 가장 뒤에 다시 추가한다. (뒤에 추가)
사용하려는 대상이 💛캐싱 큐에 존재하지 않는다면 캐싱해놓은 것이 없다는 의미이다. 재활용하지 않고 새롭게 로드해 사용 후 나중에 또 사용될지 모르니 캐싱 큐에 넣는다.
캐싱 큐가 꽉 차있다면
- 💛캐싱 큐에서 가장 오래된 것을 빼내온다. (맨 앞 삭제)
- 즉, 가장 오래된 캐시를 삭제한다.
- 💛현재 사용한 것을 캐싱 큐에서 집어넣어 캐시로 만든다. (맨 뒤 추가)
캐싱 큐가 꽉 차있는게 아니라면
- 💛현재 사용한 것을 캐싱 큐에서 집어넣어 캐시로 만든다. (맨 뒤 추가)
- 가장 오래된 것을 삭제할 필요는 없다.

개념은 완전 ‘큐’인데.. 큐에 있는 것들 중 캐시해둔게 있는지 검사를 해야 하고 중간 삭제 과정도 있기 때문에 큐를 사용하기엔 애로사항이 있을 것 같다고 생각했다. 중간 삭제, 맨 앞 삭제 연산이 잦으므로 연결리스트를 사용하기로 하였다.

✈ 직접 구현한 연결리스트

연습삼아.. 복습삼아..^ _^⭐

#include <string>
#include <vector>

using namespace std;

class Node
{
public:
    string city;
    Node* nextNode = NULL;
    Node* prevNode = NULL;
};

class LinkedList
{
public:
    Node* head = NULL;
    Node* tail = NULL;
    int size = 0;

    void AddLast(string _city)
    {
        size++;

        Node* newNode = new Node;
        newNode->city = _city;
        
        if (head == NULL) 
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->nextNode = newNode;
            newNode->prevNode = tail;

            tail = newNode;
        }
    }

    void Remove(Node* node)
    {
        size--;

        if (node == head)
            head = node->nextNode;
        if (node == tail)
            tail = node->prevNode;
        if (node->prevNode != NULL)
            node->prevNode->nextNode = node->nextNode;
        if (node->nextNode != NULL)
            node->nextNode->prevNode = node->prevNode;
        
        delete node;
    }

    Node* Search(string _city)
    {
        Node* ptr = head;
        while (ptr != NULL)
        {
            if (isEqual(ptr->city, _city)) return ptr;
            ptr = ptr->nextNode;
        }
        return NULL;
    }
    
    bool isEqual(string a, string b)
    {
        if (a.length() != b.length()) return false;
        
        for(int i = 0; i < a.length(); i++)
        {
            if (a[i] == b[i]) continue;
            else if (a[i] - b[i] == -32 || a[i] - b[i] == 32) continue;
            
            return false;
        }
        
        return true;
    }
};

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;

    LinkedList cache;
    for (int i = 0; i < cities.size(); i++)
    {
        Node* cityInCache = cache.Search(cities[i]);

        if (cityInCache == NULL)
        {
            answer += 5;
            if (cache.size < cacheSize)
                cache.AddLast(cities[i]);
            else if (cache.size == cacheSize && cacheSize > 0)
            {
                cache.Remove(cache.head);
                cache.AddLast(cities[i]);
            }
        }
        else
        {
            answer += 1;
            cache.Remove(cityInCache);
            cache.AddLast(cities[i]);
        }
    }

    return answer;
}

cities 길이가 100,000 이하인 것을 보고 지레 겁먹고 연결리스트를 사용한 것도 있는데.. 생각해보니 추가/삭제를 행하는 대상은 캐시이고 캐시 사이즈는 30이하라고 문제에서 주어졌으니 vector를 사용하여도 전혀 시간초과가 나지 않을 문제였다. 30 크기 컨테이너에서 중간 삭제 해봤자 뭐… ⭐

그리고 대소문자를 구분하지 않으므로 일치하는 것을 찾을 때 대문자와 소문자 다른 것 정도는 같다고 인식하도록 하는 기능도 넣어주어야 한다. (위에 작성한 isEqual 함수)

이미 캐시된 것이 있는지 캐싱리스트(cache) 순회하며 찾기!
- 캐시된게 없을 때 👉 cache miss이므로 answer += 5;
  - 캐싱 리스트가 꽉 차있는게 아니라면
    - 새로운 캐시로서 뒤에 추가
  - 캐싱 리스트가 꽉 차있다면
    - 사용된지 가장 오래된 캐시 삭제 (맨앞 삭제)
    - 새로운 캐시로서 뒤에 추가
- 캐시된게 있을 때 👉 cache hit이므로 answer += 1;
  - 해당 캐시 삭제 (중간 삭제)
  - 가장 최근에 사용된 캐시로서 뒤로 가야하므로 이를 다시 뒤에 추가

✈ STL의 std::list 사용

#include <string>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    for(int i = 0; i < cities.size(); i++)
        for(int j = 0; j < cities[i].length(); j++)
            cities[i][j] = tolower(cities[i][j]);

    list<string> cache;
    for (int i = 0; i < cities.size(); i++)
    {
        list<string>::iterator itr = find(cache.begin(), cache.end(), cities[i]);
        if (itr == cache.end())
        {
            answer += 5;
            if (cache.size() < cacheSize)
                cache.push_back(cities[i]);
            else if (cache.size() == cacheSize && cacheSize > 0)
            {
                cache.erase(cache.begin());
                cache.push_back(cities[i]);
            }
        }
        else
        {
            answer += 1;
            cache.erase(itr);
            cache.push_back(cities[i]);
        }
    }

    return answer;
}

list
- #include <list> 연결리스트인 STL이다. 사용법은 다른 STL과 비슷한듯 하다!
tolower
- C++에 기본으로 있는, char를 소문자로 변환해주는 함수
find
- #include <algorithm>
  - 첫번째 인수 ~ 두번쨰 인수에 해당하는 범위 내에서 세번째 인수에 일치하는 것을 찾아준다. 없다면 end() 반복자 리턴.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️