프로그래머스 레벨 2 : [1차] 캐시 (자바스크립트)

Description

코딩테스트 연습 - [1차] 캐시

캐시 교체 알고리즘 중 하나인 LRU(Least Recently Used)를 활용해서 해결하는 문제이다. 이번 알고리즘 문제를 계기로 캐시 교체 알고리즘과 LRU에 대해서 조사해 보았다. 새로운 알고리즘도 학습할 기회를 준 코딩 테스트 문제다. 무려 약 5년 전에 출제된 카카오 신입 공채 문제이다. 

 

카카오 신입 공채 1차 코딩 테스트 문제 해설

위 링크에서 캐시 문제에 대한 간단한 해설을 볼 수 있다. 

 

Cache? Cache Replacement Algorithms?

[Cache] 캐시 동작과 캐시 교체 정책

알고리즘 풀이로 곧장 들어가기 전, 우선 Cache란 무엇일까? 평소에 "캐싱한다"라는 말을 들어 본 적이 있다.

위 글을 참고해서 적어보자면 "데이터나 값을 미리 복사해 놓는 임시 장소"라고 한다. 왜 데이터를 복사해 놓을까? 계산이나 접근 시간이 없이 더 빠른 속도로 데이터에 접근할 수 있기 때문이다. 

"Caching" 이라고 ing를 붙여서 행위 자체를 말하기도 한다. 이것은 이런 식으로 설명이 되어 있다.

"Caching is the process of storing some data near where it's supposed to be used rather than accessing them from an expensive origin, every time a request comes in."

즉, 요청이 들어올 때마다 데이터에 접근하는 것은 꽤나 자원이 많이 드는 일이기 때문에, 데이터가 사용되어야 하는 위치의 근처에 일부 데이터를 저장하는 프로세스가 바로 캐싱이다.  

캐시는 CPU부터 브라우저까지 다방면에 존재한다. 캐싱은 매우 유용하다! 성능이 좋은 캐시 시스템을 구현하는 것은 꽤나 어려운 일이라고 한다. 

Cache Replacement Algorithms: How To Efficiently Manage The Cache Storage

그렇다면 캐시 교체 알고리즘(Cache Replacement Algorithms) 이라는 것은 또 무엇일까? 

캐시 저장 공간(cache storage)은 무한하지 않다. 그렇기 때문에 어떤 것은 제거하고 어떤 것은 유지하는 알고리즘이 필요하다. 대표적인 캐시 교체 알고리즘으로 3가지가 있다. FIFO, LFU, 그리고 이번 알고리즘 문제에서 요구되었던 LRU까지. 

FIFO는 Queue에서도 쓰이는 방식인데 바로 First In First Out, 가장 먼저 들어간 캐시가 가장 먼저 나오는 것이다. 이 방법은 캐시를 관리하는 간단한 방법이다. 하지만 많이 사용되는 개체라 하더라도 오래되었다면 제거된다는 문제가 있다.

LFU란 Least Frequently Used의 약자로, 가장 사용 횟수가 적은 캐시를 교체하는 것이다. LRU와 비슷한 면이 있지만, 다른 점으로는 캐시에 접근한 횟수를 추적한다는 것이다. 그래서 각 개체에는 접근 횟수를 계산하는 카운터가 있다. 만약 용량이 꽉 차게 되면 카운터의 횟수가 가장 낮은 캐시가 제거된다. 하지만 이 알고리즘에는 문제가 존재한다. 만약 캐시에 짧은 기간에 엄청나게 많이 접근되어 카운터 횟수가 엄청나게 증가했다면? 이 캐시에 장기간 접근하지 않더라도 카운터 횟수가 높기 때문에 제거되기가 어렵게 된다. 

LRU란 Least Recently Used의 약자로, 가장 오랫동안 사용되지 않은 캐시를 교체하는 것이다. 이 알고리즘은 가장 최근에 사용된 캐시를 맨 위에 유지하고, 캐시가 꽉 차면 가장 오랫동안 쓰이지 않은 캐시를 제거한다. 

 

My Solution

function solution(cacheSize, cities) {
  let time = 0;
  const cache = [];
  const [HIT, MISS] = [1, 5];
  const cacheHit = city => cache.includes(city);

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

  cities.forEach(city => {
    city = city.toUpperCase();

    if (cacheHit(city)) {
      time += HIT;
      cache.splice(cache.indexOf(city), 1);
    } else {
      time += MISS;
      if (cache.length >= cacheSize) cache.shift();
    }

    cache.push(city); 
  });

  return time;
}

• 실행 시간은 0, 캐시는 빈 배열로 설정하였다.
• 하드 코딩을 피하고 싶어서 HIT, MISS라고 각각의  실행시간에 이름을 붙여 주었다.
• cacheHit도 좀 더 의미를 주고 싶어서 따로 함수로 만들어 보았다. 
• cacheSize가 0인 경우는 cacheHit이 발생할 수 없으니 바로 MISS에 cities 배열에 들어 있는 도시의 개수만큼을 곱해서 바로 리턴해 주었다.
• cacheSize가 0이 아닌 경우는 cities 배열을 돌면서 각 city를 우선 대문자로 바꿔 준다. (대소문자 구별이 없으므로)
• 그 후 만약 cacheHit이 발생하면 실행 시간에 HIT 시간을 누적해 주고, cache 배열에서는 현재 city의 인덱스를 찾아 splice로 제거해 준다. 그 후 현재 city를 cache 배열에 push해준다.
• 만약 cacheHit이 발생하지 않는 경우에는 실행 시간에 MISS 시간을 누적해 준다. 여기서 만약 cache 배열의 길이가 cacheSize와 같거나 더 길게 될 경우에는 가장 오래된 요소를 shift로 제거해 준다. 그 후 현재의 city를 cache 배열에 push해준다. 

 

• 예를 들어 cache 배열에 [5,7,3,2]가 있고 현재 요소가 3이어서 cache Hit이 되었다면, 배열에 있는 3을 우선 제거를 해 주고 현재 요소를 가장 최신의 요소로 해 준다. 그 결과 [5,7,2,3]이 된다. 
• 만약 현재 요소가 9여서 cache Miss가 되었다면 가장 오래된 요소를 제거하고 9를 캐시에 저장한다. 그래서 [7, 3, 2, 9]가 된다.