🔎 캐시

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/17680

📄 제출 코드

function solution(cacheSize, cities) {
  var answer = 0;
  let cache = [];
  //캐시 크기가 0인 경우는 따로 처리
  if (cacheSize === 0) return cities.length * 5;

  while (cities.length) {
    const city = cities.shift().toLowerCase();
    if (cache.includes(city)) {
      cache.splice(cache.indexOf(city), 1);
      cache.push(city);
      answer += 1;
    } else {
      if (cache.length === cacheSize) {
        cache.shift();
      }
      cache.push(city);
      answer += 5;
    }
  }
  return answer;
}
let cacheSize = 3;
let cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
console.log(solution(cacheSize, cities))

이번 문제는 LRU알고리즘에 대한 것을 구현하는 문제다.
그래서 LRU가 뭔지부터 검색해보고, 다른사람의 코드를 보고 어떤건지 알아가는게 더 낫겠다 싶어 그 코드를 보며 정리해보려한다.

👉 LRU 알고리즘

LRU 알고리즘은 (Least Recently Used)의 약자로 페이지 교체 알고리즘으로
캐시에서 사용한지 가장 오래된 캐시를 지우는 알고리즘이다.

즉, 캐시크기가 꽉 찼고 새로운 값을 캐시에 넣을 때, 캐시 내에서 사용한지 가장 오래된 값을 지우고 새로운 값을 캐시에 넣는다.

캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.
이를 위해 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.

👉 어떻게 구현?

가장 최근에 사용된 항목은 push, 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다.
cache hit: 캐시안에 현재 값이 들어있기 때문에 +1
cache miss: 캐시안에 현재 값이 없기 때문에 +5

if (cacheSize === 0) return cities.length * 5; // cache miss
while (cities.length) {
    const city = cities.shift().toLowerCase();
    if (cache.includes(city)) { // cache hit
      cache.splice(cache.indexOf(city), 1);
      cache.push(city);
      answer += 1;
    } else { // cache miss
      if (cache.length === cacheSize) {
        cache.shift();
      }
      cache.push(city);
      answer += 5;
    }
  }

각 도시이름은 대소문자를 구분하지 않기 때문에 반복 시 소문자로 변경해 비교합니다.

const city = cities.shift().toLowerCase();

만약 cache에 city가 있으면, 기존에 cache에 있는 city를 지워내고 가장뒤에 넣습니다.
그리고 1증가 시킵니다.
캐시 길이가 주어진 캐시 사이즈와 같아지면, 가장 오래된(가장 앞에 있는)city를 빼내고, 새로운 도시를 push합니다.
그리고 +5를 합니다.

마지막으로 캐시 사이즈가 0이라면 항상 cache miss기 때문에 배열길이만큼 5를 곱해줍니다.

이렇게 작성하다보니까 전에 개인 프로젝트에서 했던 검색어 태그 추가가 생각이 났습니다.
먼저 태그박스의 제한은 5개이고, 검색어를 입력하고 태그박스가 추가되는데 그때 있는 검색어를 입력하면 해당 위치의 검색어를 제거하고 뒤에 새로 push하였고, 없으면 가장 앞의 태그를 지우고, push했었습니다.
그때는 그게 LRU라는 알고리즘인지 모르고 작성했었는데 지금 이 글을 쓰면서 정리하다 보니까 LRU알고리즘 인거 같습니다.
(지식이 늘었다 👍)