[ 프로그래머스 [1차] 캐시 (Lv2) ] (C++)

프로그래머스의 캐시(Lv2) 문제이다.

[ 문제풀이 ]

먼저 문제에서 가장 핵심적인 단어인 '캐시(Cache)'와 캐시교체알고리즘, 그리고 cache hit, miss 등과 같이 문제를 풀기 위해서 알아야 되는 정보들부터 문제를 해결하는 과정까지 순차적으로 알아보도록 하자.

#1. Cache

사실 캐시의 개념에 대해서는 이 문제를 푸는데 몰라도 상관없지만 간략하게만 이야기해보면, 컴퓨터가 실행될 때 수 많은 데이터들에 대한 연산을 진행하게 되는데, 이 때 메모리나 디스크에서 사용되었던 데이터들, 즉, 사용되었던 데이터에 대해서는 다시 사용할 수 있는 가능성이 높다라는 개념을 이용해서 한번 사용되었던 데이터들은 더 빠르게 접근 가능한 메모리 영역에 저장해놓는 것을 의미한다.

#2. Cache Hit & Cache Miss

Cache Hit라는 것은 "현재 사용하고자 하는 데이터가 Cache Memory에 존재하는 경우" 를 의미하고, Cache Miss라는 것은 "현재 사용하고자 하는 데이터가 Cache Memory에 존재하지 않는 경우"를 의미한다.

간단하게 문제와 연관지어서 예시를 한번 살펴보자.

ex) 캐시의크기 : 2 , 사용할 데이터 : [ A , B ]

가장 초기에는 캐시 메모리에는 아무런 데이터도 없을 것이다.

이 상태에서, 'A'를 실행하기 위해서 캐시 메모리를 확인해보니, 'A'가 존재하지 않는다.

따라서, 이 경우에는 Cache Miss가 발생한 것이며, 'A'가 Cache Memory에 적재될 것이다.

현재 Cache의 상태 = [ A ]

두 번째로 ,B를 실행하기 위해서 캐시 메모리를 확인해보니, 'B'가 존재하지 않는다.

따라서, 이 경우 또한 Cache Miss가 발생한 것이며, 'B'가 Cache Memory에 적재될 것이다.

현재 Cache의 상태 = [ A , B ]

세 번째로, A를 실행하기 위해서 캐시 메모리를 확인해보니, 이미 Cache Memory에 'A'가 존재한다.

즉, 이 경우에는 Cache Hit가 발생한 것이다.

문제에서 제시한 바에 의하면, Cache Hit일 경우에는 실행시간 1초, Miss일 경우에는 실행시간이 5초이다.

#3. LRU(Least Recently Used) Algorithm

문제에서 제시한 캐시 교체 알고리즘은 LRU라고 했다.

LRU(Least Recently Used)를 말 그대로 해석해보면, "가장 오래전에 사용된 = 가장 최근에 사용되지 않은 것" 으로 해석이 가능하다.

즉 ! 현재 Cache Memory에 적재되어 있는 놈들 중에서, 한 놈을 골라서 다른 데이터로 바꿔야 하는 상황이 온다면,

그 때 한 놈을 고르는 기준이 "가장 오래전에 사용된 놈"이 된다는 것이다.

ex) 캐시의 크기 : 2 , 사용할 데이터 : [ A , B , C , B , A ]

가장 처음 'A'에 의해서 Cache = [ A ]

두 번째 'B'에 의해서 Cache = [ A , B ]

세 번째 'C'에 의해서 캐시 교체 알고리즘이 필요하다. 왜냐하면, 'C'는 적재되어있는 데이터도 아니고, Cache에 들어가기 에는 이미 Cache가 꽉 찬 상태이기 때문에 이 경우 교체 알고리즘이 필요하다.

그런데 , Cache를 보게 되면, [ A , B ]가 있는데, A , B 중에서는 상대적으로 A가 가장 최근에 사용되지 않은 데이터이다.

따라서, 'A'를 빼고, C를 넣어준다는 것이다.

그럼 Cache = [ C , B ] 가 될 것이다.

네 번째 'B'에 의해서는 캐시 교체 알고리즘이 필요하지 않다. 왜냐하면, 이미 'B'는 적재되어 있는 데이터 이기 때문이다.

마지막 'A'에 의해서 캐시 교체 알고리즘이 필요하다. 그럼 , [ C , B ] 중 어떤 놈을 골라야 할까 ??

'B'는 두 번째 부터 있었고, 'C는 세 번째 부터 있었으니, B가 더 오래전에 사용된 놈일까 ?? 아니다. 'B'는 네번째에 의해서 사용된 놈이다. 즉 ! C가 더 오래전에 사용된 놈이 된다. 따라서, 이 경우 C를 빼고 A를 적재시켜주면 된다.

이렇게 적용되는 알고리즘이 LRU 이다.

#4. list를 이용한 Cache 표현

이제 본격적인 문제 풀이에 들어가보자.

본인은 , Cache Memory를 list를 이용해서 표현해 주었다. 왜 굳이 list를 사용했을까 ??

이 문제에서는 LRU 알고리즘을 사용해야 하는데, 본인은 캐시를 교체하는 경우, 가장 최근에 사용되지 않은 데이터들을 따로 곗나하지 않았다. 정말 간단하게, list에서 가장 앞에 있는 놈들부터 순차적으로 저장을 해 주었다.

즉, 캐시를 교체해야 할 경우가 온다면, 가장 앞에 있는 놈을 제거하고, 현재 캐시에 적재되어야 할 데이터는 list의 가장 마지막에 넣어주는 방식으로 구현하였다.

즉, 여기서 "가장 앞에 있는 놈을 제거" 하기 위해서는 pop_front()와 같은 연산을 가진 자료구조가 필요한데, vector는 이러한 연산이 불가능해서 list를 사용해 주었다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <list>
 
#define HIT 1
#define MISS 5
using namespace std;
 
void Remake_Word(vector<string> &Cities)
{
    for (int i = 0; i < Cities.size(); i++)
    {
        for (int j = 0; j < Cities[i].length(); j++)
        {
            if ('A' <= Cities[i][j] && Cities[i][j] <= 'Z')
            {
                Cities[i][j] = Cities[i][j] - 'A';
                Cities[i][j] = Cities[i][j] + 'a';
            }
        }
    }
}
 
int solution(int cacheSize, vector<string> cities) 
{
    if (cacheSize == 0) return cities.size() * MISS;
    Remake_Word(cities);
    list<string> Cache;
    int answer = 0;
    
    for (int i = 0; i < cities.size(); i++)
    {
        string Name = cities[i];
        bool Flag = false;
        list<string>::iterator Iter = Cache.begin();
        /* Cache를 탐색하면서 현재 데이터가 Cache에 적재되어 있는지 탐색. */
        for (Iter; Iter != Cache.end(); Iter++)
        {
            if (*Iter == Name)
            {
                /* 만약, 이미 적재되어 있는 놈이라면 = Cache Hit */
                /* 가장 최근에 사용된 놈이므로, 기존에 위치해있던 놈을 없애주고. */
                /* 가장 마지막에 다시 넣어준다. */
                Flag = true;
                answer = answer + HIT;
                Cache.erase(Iter);
                Cache.push_back(Name);
                break;
            }
        }
 
        if (Flag == false)
        {
            /* 만약, 적재되어 있지 않은 놈이라면 = Cache Miss */
            /* Cache가 꽉 차있다면, 가장 앞에 있는 놈을 제거 후, 가장 마지막에 삽입. */
            /* 그게 아니라면, Cache의 가장 마지막에 삽입. */
            answer = answer + MISS;
            if (Cache.size() == cacheSize)
            {
                Cache.pop_front();
                Cache.push_back(Name);
            }
            else Cache.push_back(Name);
        }
    }
    return answer;
}