LRU(Least Recently Used) Cache 교체 알고리즘

Programmers Lv.2 - [1차] 캐시

 

캐시(Cache)는 연산에 필요한 데이터들을 미리 저장하는 임시 메모리이다.

 

연산을 처리할 때, CPU에서 주기억장치, 보조기억장치까지 도달해서 연산을 처리한다.

이는 물리적으로 거리가 멀어서 비용이 많이 든다.

 

캐시의 경우는 CPU 바로 옆에 붙어있기 때문에, 물리적으로 거리가 가까워 비용이 적다.

 

그렇기 때문에, 연산에 자주 사용되는 값이나 데이터들을 캐시에 미리 적재해놓으면 접근 시간을 줄여 성능을 높일 수 있다.

 

 

캐시 히트(Hit)율, 캐시 미스(Miss)율이라는 것이 존재한다.

 

캐시에 적재된 데이터들을 사용하여 연산을 처리하면, 캐시 히트율이 올라가는 거고, 적재된 데이터들을 사용하지 않으면 캐시 미스율이 올라가는 것이다.

 

LRU 캐시 교체 알고리즘이 필요한 이유는 캐시에 적재될 데이터들을 자주 사용될 데이터들로 교체하는, 즉 캐시 히트율을 높이기 위한 알고리즘이라고 할 수 있다.

 

 

연산을 위해 A  →  B  →  C 순서로 데이터가 호출이 되었다고 가정해보자.

 

캐시에는 호출된 순서부터 차례대로 데이터가 적재될 것이고, 캐시에는 가장 마지막에 호출된 데이터부터

C  →  B  →  A 순으로 적재될 것이다.

 

만약에 연산을 위해 B라는 데이터가 필요하다면,

 

캐시에는 B  →  C  →  A 순으로 적재된다.

 

 

추가적으로 캐시의 용량(Size)이 3이라고 가정해보자.

 

캐시에 B  →  C  →  A 순으로 적재되어 있는 상태에서 D라는 데이터를 적재시킬 때,

 

D  →  B  →  C 로 적재가 되고, 마지막의 A의 데이터는 캐시에서 지워진다.

 

용량이 3이기 때문이고, 캐시의 사용 목적상으로 캐시 히트율이 낮은 데이터는 사라져야하는 게 맞기 때문이다.

(캐시 미스율을 낮추기 위함인 것이다)

 

 

Programmers Lv.2 - [1차] 캐시 문제의 코드 풀이는 다음과 같다. - Java

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        List<String> list = new ArrayList<>();

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

        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();

            if (list.contains(cities[i])) {
                answer++;
                list.remove(cities[i]);
                list.add(cities[i]);
            } else {
                answer += 5;

                if (list.size() == cacheSize) {
                    list.remove(0);
                    list.add(cities[i]);
                } else list.add(cities[i]);
            }
        }

        return answer;
    }
}