캐시 - LRU(Least Recently Used)

카카오 코테문제로 유명한 알고리즘이라고 한다.

먼저 문제부터 보자.

LRU가 뭔지 몰라 벙쪄서 바로 블로깅 해봤다.

https://dailylifeofdeveloper.tistory.com/355

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

https://fomaios.tistory.com/entry/Algorithm-LRULeast-Recently-Used-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80-feat-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

여기 블로그에서 잘 설명해줬다. 한번 보시길.

일단 LRU란, 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이다. FIFO, LFU, MFU 등과 함께 페이지 교체 방식중 하나다.

자료를 찾아보니 정보처리기사에도 나오는 내용이었다. FIFO만 기억에남았다.. 반성해야겠다.

페이지 교체방식을 잘 정리해둔 블로그다. 참고하시길

https://doh-an.tistory.com/28

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR

아무튼 다시 돌아와서, LRU는 가장 참조한지 오래된데이터라면 앞으로도 참조할일이 가장 적을거라는 가정하에 생긴 알고리즘이라고 한다. 

풀이를 살펴보자. 이 풀이는 내가 푼게 아니라 프로그래머스에 신재권 님이라는 분이 올리신 풀이다.

풀이를 아예 외워봐야겠다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static int solution(int cacheSize, String[] cities) {
        Queue<String> caches = new LinkedList<>();
        int time = 0;

        if (cacheSize == 0) {
            return cities.length * 5;
        }

        for (String city : cities) {
            String cityLowerCase = city.toLowerCase();
            if (caches.contains(cityLowerCase)) { // 이미 존재하면
                caches.remove(cityLowerCase); // 최신화
                caches.offer(cityLowerCase);
                time++;
            } else {// 캐시 미스라면
                if (caches.size() < cacheSize) { // 여유 공간이 있다면
                    caches.offer(cityLowerCase);
                } else { // 여유 공간이 없다면, 가장 먼저 참조된 페이지 삭제
                    caches.poll();
                    caches.offer(cityLowerCase);
                }
                time += 5;
            }
        }

        return time;
    }
}

이분은 FIFO구조의 큐를 사용해 풀었다.

일단 캐시크기가 0인경우를 처리했고,

그다음 캐시 힛과, 캐시 미스인 경우를 매우 쉽게 처리한 것을 볼 수 있다.