LRU Caching

문제를 풀어본 후 해설을 보시면 좋습니다 !! ^ㅡ^

예상 난이도 : 5 / 10

이번 문제는 수업 시간에 지겹게 들었던 'LRU Caching'(https://www.acmicpc.net/problem/4568) 입니다.

컴퓨터 구조 수업에서 캐시에 동작에 대해서 배울 때 배우는 알고리즘 입니다.

이 문제가 좋다고 생각한 이유는 'LRU 알고리즘에 대해서 다시 한 번 고민해 볼 수 

있으며, 카카오 기출 문제'이기도 하기 때문입니다.

우선 문제가 모두 영어이기는 하지만 아무것도 읽을 필요가 없습니다.

그냥 LRU에 대해서 설명합니다.

입력 부분과 출력 부분 영어만 읽어주면 됩니다.

문제를 많이 풀어보셨다면, 대충 봐도 이해가 되실 텐데요.

'!'가 나올때 캐시에 어떤 문자가 있는지 출력하고 나머지 문자는 모두 

데이터에 관련된 값입니다.

이를 어떻게 구현할 것인가에 크게 두 가지가 있습니다.

1) 간단하게 c++에서 list를 사용하여 구현

2) 조금 더 어렵게, 링크드 리스트를 자체적으로 모두 구현

두 가지 방법 모두 해보기를 추천합니다.

왜냐하면 코딩 테스트에서는 고급 알고리즘은 거의 물어보지 않습니다. 

약 95%는 '완전 탐색'과 'DP', 'disjoint set' 선에서 끝입니다. 

주로 어려움을 겪는 곳은 '구현' 입니다. 

코딩 경험이 많이 없다면, 한 번도 해보지 못한 구현을 할 때가

가장 멘탈이 붕괴 됩니다.

모르는 알고리즘에 대해서 물어보면 고민하다가 못풀겠다는 것을 확신하고

포기하는 반면에, '구현' 문제는 좀만 더 하면 구현할 수도 있을 것 같은데 ... 이러다가 시간을 모두 소모하고

시험이 끝나버립니다.

'구현' 문제는 방향을 잘 잡아야 합니다. 무턱대고 키보드부터 두들기면 코드가 꼬이고 또 꼬이고 결국은 

다시 시험 준비를 해야하죠. 

구현 문제에서 뿐만 아니라, 거의 모든 경우에서 가장 중요한 것은 '경우의 수를 확실히 나눌 줄 아느냐' 입니다.

이것을 제대로 못하면 코드가 조금만 길어져도 '여긴 어디, 나는 누구'의 상황이 되버립니다. ㅠ.ㅠ

간단하게 list를 사용해서 구현하는 방법만 소개하겠습니다. list에서 많이 사용하는 함수 정도는 확실히 알아둬야 합니다.

list<char> ls;
ls.pop_back();
ls.pop_front();
ls.push_back('a');
ls.push_front('b');
auto it = ls.begin();
it = ls.erase(it);
it = ls.begin();
ls.insert(it,'c');
ls.size();
 
for (auto it = ls.begin(); it != ls.end(); it++)
    cout << (*it) << endl;
 
for (char c : ls)
    cout << c << endl;

위 코드에서 가장 중요한 부분은 7번째 줄 입니다. it가 가르키고 있는 노드를 삭제 후 it가 반환 값을 받습니다.

이를 출력해보면 지워진 노드의 next 노드를 가르키게 됩니다. 마지막 노드를 지웠다면 it는 ls.end()의 값을 갖습니다.

다시 문제로 돌아와 보면, '!'를 받아 출려해야 될 때는 12 - 16번째 줄에서 둘 중 마음에 드는 for문을 써서 

출력하면 됩니다.

그리고 'A' - 'Z'의 문자를 만났을 때는 

auto it = find(c, ls);
if (it != ls.end()) { // 캐시에 있을 경우
    ls.erase(it);
    ls.push_back(c);
}
else { // 캐시에 없을 경우
    if (ls.size() == n) ls.pop_front();
    ls.push_back(c);
}

1번 줄의 find 함수는 제가 따로 만든 함수입니다.  우선 두 가지 경우가 있습니다.  읽고자 하는 데이터가

1) 캐시에 잇느냐, 2) 없느냐. 

캐시에 있을 경우 해당 노드를 지우고(erase), 맨 뒤에 붙여주면 됩니다. 그래야 최근에 본 데이터라는 뜻이 되겠죠.

캐시에 없을 경우에는 두 가지 상황을 더 고려해야 합니다.

1) 캐시가 꽉 찼느냐

2) 캐시에 여유 공간이 있느냐

1번 상황에서는 제일 오래전에 접근했던 데이터를 지우고 (pop_front), 맨 뒤에 붙여주면 됩니다.

2번 상황일 때는 지울 필요없이 그냥 뒤에 붙여주면 됩니다.

이 코드에서 고쳐야 할 부분이 있습니다. 바로 중복되는 코드 부분인 4번과 8번 줄을 밖으로 빼서 한 번만

적어주면 될 것입니다. 어차피 어떤 데이터를 접근했을 경우에는 맨 뒤에 붙여줘야 하기 때문입니다.

추천 문제)

1. 키로거(https://www.acmicpc.net/problem/5397)

2. 회전하는 큐(https://www.acmicpc.net/problem/1021)

3. 조세퍼스 문제(https://www.acmicpc.net/problem/1158)

4. 에디터(https://www.acmicpc.net/problem/1406)