[프로그래머스] 캐시

문제 링크

프로그래머스

 

문제 설명

 

입력 형식

 

출력 형식

 

조건

 

입출력 예제

 

문제 풀이

1. 캐시 사이즈가 0이라면 계속 cache miss이기 때문에 cities길이 * 5를 먼저 반환해줌

2. cities길이 만큼 while 반복문을 돌면서 소문자로 치환한 city 이름을 구해준다. (대소문자 구분 x)

3. 캐시에 city가 있으면 해당 인덱스에 있는 city를 삭제하고, count 1증가

4. 캐시에 city가 없으면 count 5증가 후 cache.push(city)를 해주는데, 캐시 길이가 캐시사이즈랑 같으면 shift를 해준다 (LRU이기 때문에)

 

function solution(cacheSize, cities) {
    let answer = 0;
    let cache = [];
    
    if(cacheSize === 0) return cities.length * 5;
    while(cities.length) {
        const city = cities.shift().toLowerCase();
        if(cache.includes(city)) {
            answer += 1;
            cache.splice(cache.indexOf(city), 1);
            cache.push(city);
        } else {
            answer += 5;
            if(cache.length === cacheSize) {
                cache.shift();
            }
            cache.push(city);
        }
    }
    return answer;
}

 

마무리

페이지 교체 알고리즘

• 무작위 : 스왑 영역으로 옮길 대상 페이지를 특별한 로직없이 무작위로 선정 (성능이 좋지 않아 거의 사용 X)
• FIFO (First In First Out) : 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 옮긴다. 올라온 순서만 고려하고 자주 사용하는 페이지를 고려하지 않기 때문에 성능이 좋지 않다. 이런 단점을 개선하기 위해 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있다.
  • 2차 기회 페이지 교체 알고리즘 : 마찬가지로 큐를 사용하지만 페이지 부재없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 기회를 한 번 더 주는 방식
  • 시계 알고리즘 : 2차 기회 페이지 교체 알고리즘과 비슷하지만 원형 큐를 사용한다는 점이 다르다.
• 최적 : 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다. 즉, 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하는데, 성능은 좋지만 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다. 그래서 이에 근접하는 LRU와 LFU, NUR 등이 개발되었다.
  • LRU (Least Recently Used) : 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다.
  • LFU (Least Frequently Used) : 페이지가 몇 번 사용 되었는지를 기준으로 대상 페이지를 선정한다. 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.
  • NUR (Not Used Recently) : 최근 미사용 페이지 교체 알고리즘

 

그럼 LRU와 FIFO는 무엇이 다른걸까??

 

FIFO 알고리즘은 메모리에 올라온 시간을 기준으로 가장 오래된 페이지를 교체하고, LRU 알고리즘은 페이지에 접근한지 가장 오래된 페이지를 교체한다는 점이 다르다!