[CodeKata] 프로그래머스 : 3.26(금), 캐시 / [이론] 캐시 교체 알고리즘

🥋 Ooooth!! (Level 2)

LRU 캐시 알고리즘만 이해하면 어려운 문제는 아니다.

캐시는 cacheSize 만큼만 데이터 저장이 가능하며, 캐시 유무에 따라 answer에 1 또는 5를 더하는 것이다.

 

 

 🧮 풀이

function solution(cacheSize, cities) {
  let cache = [];
  let answer = 0;
  
  for (let city of cities) {
    city = city.toUpperCase();
    const index = cache.indexOf(city)
    if (index === -1) {
      answer += 5;
      cache.push(city);
      if (cache.length > cacheSize) {
        cache.shift();
      }
    }
    else {
      answer += 1;
      cache.splice(index, 1);
      cache.push(city)
    }
  }
  return answer;
}

1. cache는 우리가 캐시로 활용할 배열이다. answer는 반환할 정답이자, cache hit/miss 에 따른 실행시간을 누적할 변수이다.
2. cities 배열을 순회하며 city(도시명)을 캐시와 대조한다. 우선, 대소문자 구분을 없애기 위해 toUpperCase() 로 통일한다.
3. index는 cache에서 city(도시명)의 인덱스이다. indexOf() 메서드를 활용했고, 존재하지 않을 시 -1이 할당된다.
4. 존재하지 않을 경우, answer에 5를 더한다. 또, cache에 city를 push() 하며, cache 길이가 cacheSize를 초과하면 맨 앞을 shift()
5. 존재할 경우, answer에 1을 더한다. 또한, cache에서 city 부분을 splice() 한 뒤, 맨 뒤로 다시 push() 한다.

 

🖇 리뷰

- 캐시 교체 알고리즘

 

캐시(Cache)란, 속도가 빠른 장치와 느린 장치간의 병목현상을 줄이기 위한 범용 메모리로, 지역성을 이용해 사용할 데이터를 예측해 저장한다. 쉽게 말하면, 사용했던 데이터를 속도가 빠른 저장장치에 저장해놓고, 다음에 참조할 때 캐시 메모리를 이용해 빠르게 Read하는 것이다.

 

이 때, 캐시의 용량이 한정적이므로 어떠한 데이터를 지우는지 결정하는 알고리즘이 바로 캐시 교체 알고리즘인 것이다.

(페이지 교체 알고리즘 이라고도 일컫는다.)

위에서 언급한, cache hit의 확률이 높을수록 우수한 알고리즘으로 분류되며, LRU 역시 우수한 알고리즘 중 하나에 포함된다.

 

* 종류

1) Random : 교체될 페이지를 임의 선정. 오버헤드(메모리 처리시간) 가 적음.

2) FIFO(First In First Out) : 캐시 내에 오래 있었던 페이지 교체. 자주 사용되는 페이지가 교체될 우려가 있음.

3) LFU(Least Frequently Used) : 사용 횟수가 가장 적은 페이지 교체. 최근 적재된 페이지가 계속 교체되는 불합리성 잔존.

4) LRU(Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지 교체. Time Stamping(시간기록) 에 의한 오버헤드 존재.

5) NRU(Not Recently Used) : 2개의 비트(참조비트, 수정비트)를 이용하여, 오랫동안 사용되지 않은 페이지 교체.

6) SCR(Second Chance Replacement) : 최초 참조비트 1로 셋팅, 1인 경우 0으로 셋팅, 0인 경우 교체. (기회를 한 번 더 줌)

7) MFU(Most Frequently Used) : 참조횟수가 가장 많은 페이지 교체. (가장 많이 사용된 페이지는 향후 사용되지 않을거라는 논리)

 

• 페이지(page) : 주기억 장치의 물리적 용량을 구분하는 단위. 주기억 장치와 보조기억 장치 사이의 전송단위.
• 오버헤드(overhead) : 운영 체제가 시스템을 관리하는 데 필요로 하는 CPU 타임이나 메모리 용량.

 

모범답안 풀이는 유사했다. (LRU 로직에 근거하다보니) 캐시의 페이지 교체 알고리즘에 대해 새로이 알게 된 계기였다.

 

[출처]

- 긍정대마왕 님의 블로그 : m.blog.naver.com/babyj2005/221508257824