LRU(Least Recently Used) 알고리즘

프로그래머스 문제를 풀다가 LRU 알고리즘 문제를 풀게 되었다.

👉🏻문제 링크👈🏻

캐시크기와 데이터가 주어졌을 때 데이터베이스에서 데이터를 가져오는 실행시간을 구하는 문제이다.
문제 조건에서 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다고 명시하였다.

먼저 캐시(Cache)란?
데이터나 값을 미리 복사해 놓는 임시장소!
캐시에 해당 데이터가 있다면 데이터를 가져올 때 훨씬 빠를 것이다.

그러나 캐시에 모든 데이터를 저장할 수 없기 때문에 어떠한 룰에 따라 캐시에 데이터가 저장될 것이다. 그 룰이 바로 캐시 교체 알고리즘인 것이다.

캐시 교체 알고리즘의 종류
1. FIFO(First in First Out)
2. LFU(Least Frequently Used)
3. LRU(Least Recently Used)

이 중 LRU 알고리즘은 말 그대로 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다.
참조하는 값이 캐시 안에 없으면 가장 오래 전에 참조한 값을 빼고 현재 값을 캐시에 넣어주고, 참조하는 값이 있다면 해당 값을 캐시의 가장 최근 위치에 넣어주면 된다.

파이썬으로 구현한 코드는 다음과 같다.

def solution(cacheSize, cities):
    answer = 0
    cache = []
    if cacheSize == 0:
        return len(cities) * 5
    for city in cities:
        c = city.lower()
        if c in cache: # 캐시 적중
            cache.pop(cache.index(c))
            cache.append(c)
            answer += 1
        else: # 캐시 실패
            if len(cache) == cacheSize:
                cache.pop(0)
            cache.append(c)
            answer += 5
    return answer