💻 [1차] 캐시

❓ 문제

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

✔️ 코드

function solution(cacheSize, cities) {
    var cache = [];
    var runTime = 0;
    cities = cities.map(x => x.toUpperCase())

    for (let i = 0; i < cities.length; i++) {
        var city = { name: cities[i], index: i };
        var isHit = cache.find(a => a.name === cities[i]);

        if (isHit) {
            var findIndex = cache.indexOf(isHit);
            cache[findIndex].index = i;
            runTime += 1;
        } else {

            cache.push(city);
            runTime += 5;
            if (cache.length > cacheSize) {
                cache.shift();
            }
        };

        cache.sort((a, b) => a.index - b.index);


    }

    var answer = runTime;
    return answer;
}

var cacheSize = 3;
var cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]
console.log(solution(cacheSize, cities));

❗️풀이과정

LRU 알고리즘

캐시가 메모리를 관리하는 알고리즘이다.

https://gomguard.tistory.com/115

• 캐시에 새로 들어올 데이터의 값이 이미 있다
  • 해당 값을 캐시의 기존의 자리에서 가장 앞의 자리로 이동시킨다.
• 캐시에 새로 들어올 데이터의 값이 없다
  • 캐시 메모리가 이미 꽉차 있는 경우 : 캐시메모리의 가장 뒤의 자리값을 비워두고 가장 앞의 자리에 새로운 값을 넣는다.
  • 캐시 메모리가 꽉차 있지 않은경우 : 캐시메모리의 가장 앞의 자리에 새로운 값을 넣는다.

알고리즘 자체는 이렇게 되지만 해당 메모리 값마다 우선순위를 부여해야한다. 우선순위는 메모리중 가장 앞에 놓이는 순서이다.

따라서 메모리의 우선순위를 변경하면서 LRU 기법을 충실히 구현한다.

위 코드에서 shift대신 기존 값의 index 값을 찾아 제거 해도 된다.

배운점

• LRU 알고리즘
• 문제에 알고리즘이 100퍼센트 사용된다면 해당 알고리즘을 충실히 구현하자