[프로그래머스] 캐시

Programmers : [1차] 캐시

 

🔗 문제 링크

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

프로그래머스

 

---

💬 문제

처음 이 문제를 읽었을 때, 문제 내용을 읽었을 때 주어진 변수들이 어떻게 작동해서 주어진 결과값이 나왔는지 이해하기 쉽지 않았다.

이 문제의 핵심은 캐시 교체 알고리즘 LRU이다. LRU가 무엇인지 먼저 알아보자.

 

 

 LRU 알고리즘 (Least Recently Used) 

LRU 알고리즘은 페이지 교체 알고리즘 중 하나로, 사용한지(참조되지 않은지) 가장 오래된 페이지를 교체하는 알고리즘이다.

이 알고리즘은 사용한지 가장 오래된 페이지는 더이상 쓰지 않을 확률이 높다는 가정 하에 만들어진 알고리즘이다.

 

LRU 알고리즘에서 알아둬야 할 개념에는 Cache Hit와 Cache Miss가 있다.

만약 캐시에 참조하고자 하는 페이지가 없다면 맨 앞에 추가하면 되고, 참조하고자 하는 페이지가 있다면 그것을 가져와 맨 앞에 넣어주면 된다. 참고로 맨 뒤가 가장 오랫동안 참조하지 않은 페이지다.

 

• Cache Hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하는 경우
  
  
• Cache Miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우

더 자세한 내용은 아래 링크를 참조하길 바란다.
https://valueengine.tistory.com/65

[알고리즘] LRU 알고리즘

 

이 문제에 이 알고리즘을 적용해 생각해보자면, 다음과 같다.

참조할 도시들을 하나씩 꺼내와 캐시에 넣어주고, 캐시(배열)가 가득 찼을 경우에는 캐시 배열 내 가장 오래된(가장 먼저 넣어준) 도시를 지워주면 된다.

 

---

💬 문제 설명

1. 캐시 크기 cacheSize와 도시 이름들이 담긴 배열 cities가 주어진다.
   
   - 각 도시의 이름은 대소문자가 섞인 영문자이며, 알파벳이 동일하다면 대소문자를 구분하지 않는다
   
   
2. LRU 알고리즘을 사용하여 총 실행시간을 구해준다
   
   1) 도시이름 배열에서 꺼낸 도시가 캐시에 없을 때, 캐시 맨 뒤(최신)에 넣어준다
   
     - 이때 캐시가 가득찼다면 가장 오래전에 넣은 도시를 빼고, 새로운 도시를 추가해준다
   
     - Cache miss의 경우이므로 실행 시간 +5을 해준다
   
   2) 특정 도시가 캐시에 있다면, 그 도시를 배열의 맨 뒤(최신)로 옮겨준다
   
     - Cache Hit의 경우이므로 실행 시간 +1를 해준다
   
   
3. 캐시의 크기가 0일 때도 고려해준다

 

728x90

 

---

💡 입출력 예시

5번째 예제를 보면, 캐시 크기가 2이므로 2개의 도시만 캐시 배열에 담을 수 있다.
Jeju와 Pangyo를 캐시에 넣으면 실행시간은 +10가 된다. 그 다음으로 NewYork을 넣으려 할 때 캐시가 가득찼으므로 Jeju를 빼주고 넣어주며, 실행시간은 15가 된다. 마지막으로 대소문자는 다르지만 newyork이 캐시에 있으므로 newyork을 캐시의 최신으로 가져오고, 실행시간은 16이 된다.

["Jeju", "Pangyo"] => ["Pangyo", "NewTork"] => ["Pangyo", "newyork"]

 

6번째 예제를 보면, 캐시가 0이기에 아예 도시를 넣을 수 없어 모두 cache miss가 나오므로, 도시 5개 x miss 5번해서 실행시간은 25가 된다.

 

 

반응형

 

---

💻 풀이

LRU 알고리즘을 JavaScript 코드로 구성하면 다음과 같다.

• 대소문자를 구분하지 않기에 전부 소문자로 바꿔준다.
  
  
• 도시를 넣어줄 캐시 배열과 실행시간 변수를 만들어준다.
  
  - 캐시에 도시가 없는 경우(MISS)의 실행시간은 5이고, 이미 있는 경우(HIT)는 1이다.
  
  
• 캐시가 0인 경우는 전부 MISS이므로 도시의 개수(length)와 MISS를 곱해 실행시간을 구해준다.
  
  
• 캐시에 넣을 도시가 있다면, 캐시에서 그 도시만 잘라내 배열 맨 끝으로 옮겨준다.
  
  - 이때 실행시간은 +1 (HIT)이다.
  
  
• 캐시가 도시에 없다면, 배열 맨 뒤에 도시를 넣어준다.
  
  - 이때 실행시간은 +5 (MISS)이다.
  
  - 만약 이미 캐시가 가득찬 상태라면, 가장 오래전에 넣은 배열 1번째 도시를 빼주고 넣어준다.

function solution(cacheSize, cities) {
    cities = cities.map(city => city.toLowerCase());
    
    const cache = [];
    const HIT = 1, MISS = 5;
    let time = 0;
    
    if (cacheSize === 0) {
        return cities.length * MISS;
    }
    
    while (cities.length) {
        let city = cities.shift();
        // Cache Hit
        if (cache.includes(city)) {
            cache.splice(cache.indexOf(city), 1);
            cache.push(city);
            time += HIT;
            
        // Cache Miss
        } else {
            if (cache.length >= cacheSize) {  // 캐시가 가득 찼다면
                cache.shift();
            }
            cache.push(city);
            time += MISS;
        }
    }
    return time;
}

 

실행 결과와 채점 결과는 다음과 같다.

 

 

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://velog.io/@ddyy094/LRULeast-Recently-Used-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%9E%80
• https://dailylifeofdeveloper.tistory.com/355