[Python] Lv.2 캐시

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

프로그래머스

 

이 문제는 캐시 교체 알고리즘으로 LRU를 사용한다. 이 문제를 통해 LRU라는 개념을 처음 보았기 때문에, 간단하게 ChatGPT로 어떤 알고리즘인지만 이해했다. 아래는 LRU 알고리즘에 대한 요약이다.

 

LRU(Least Recently Used)는 캐시 교체 알고리즘 중 하나로, 주로 메모리 캐싱에서 사용된다. 이 알고리즘은 가장 최근에 사용되지 않은 데이터를 교체하는 방식으로 동작한다. 구체적으로 설명하면 다음과 같다:

1. 사용된 데이터 추적: 각각의 데이터에 접근할 때마다 해당 데이터의 "사용 시간"을 기록한다. 사용 시간은 각 데이터가 언제 마지막으로 사용되었는지를 나타낸다.
2. 캐시 교체: 캐시에 새로운 데이터를 저장할 때, 캐시 공간이 가득 차 있는 경우 새로운 데이터를 추가하기 위해 교체할 데이터를 선택해야 한다. 이때 LRU 알고리즘은 가장 오랫동안 사용되지 않은 데이터를 교체 대상으로 선택한다.
3. 사용 시간 갱신: 데이터에 접근할 때마다 해당 데이터의 사용 시간을 갱신한다. 이를 통해 가장 최근에 사용된 데이터를 파악하고, 교체 대상을 결정할 수 있다.

 

이 개념을 간단히 이해하면 여기서 주어지는 변수 cacheSize, cities가 어떤 역할을 하는지 알 수 있다. cacheSize는 한정된 캐시 공간을 뜻하고, cities는 넘어갈 캐시의 대상이다. len(cacheSize)만큼 캐시를 넣을 수 있다는 뜻이다. 알고리즘을 이해하니 문제가 어렵지 않아서 아래와 같이 계산하였다.

 

def solution(cacheSize, cities):
    if cacheSize == 0 : return 5*len(cities)
    cities = list(reversed(cities)) # 도시를 스택처럼 처리
    cache = [] # 스택 활용
    time = 0
    while cities :
        city = cities.pop().lower()
        if city in cache :
            idx = cache.index(city)
            if idx != len(cache)-1 :
            	cache = cache[:idx] + cache[idx+1:] + [city] # 캐시 우선순위를 위해 조정
            time += 1
            continue
        time += 5
        if len(cache) < cacheSize : cache.append(city)
        else : 
            cache = cache[1:]
            cache.append(city)
    
    return time