코드

from collections import deque
def solution(cacheSize, cities):
	
    if cacheSize == 0:
        return len(cities) * 5
        
    lru = deque()
    excute_time=0
    
    for city in cities:
        city = city.lower()
        
        if city in lru:
            excute_time+=1
            lru.remove(city)
            lru.appendleft(city)
            
        else :
            excute_time+=5            
            if len(lru) < cacheSize:
                lru.appendleft(city)
            else:
                lru.pop()
                lru.appendleft(city)
                
    return excute_time

풀이

LRU 알고리즘

• 캐싱 방법 중 하나
• OS 페이지 교체 알고리즘으로도 사용된다.

LRU 알고리즘을 한마디로 말하자면 다음과 같다

가장 오랫동안 사용하지 않는 데이터를 제거하고 새로운 데이터를 추가한다.

직관적이고 단순한 방법이다. 캐싱이라는 것이 데이터를 원래 속도보다 빨리 읽기 위해 사용되는 것인데, 당연히 사용되지 않는 데이터일 수록 중요도가 떨어지고, 결국에는 제거되게 된다.

구현방법

LRU 알고리즘은 더블 링크드리스트 로 구현한다.

• head는 가장 최근에 사용된 데이터를 가르킨다
• tail은 가장 오랫동안 사용하지 않는 데이터를 가르킨다.
• 포인터가 두개로 앞, 뒤를 가르킨다

파이썬에서 포인터를 구현해서 위와 같이 정석적으로 메소드 하나하나를 구현하는 방법도 있겠으나, 우리는 deque 자료구조를 사용해서 LRU 알고리즘을 구현한다.

deque

데크 덱 이라고도 불리는 자료구조로 큐 자료구조와 유사하다.

큐가 데이터의 입구가 하나인 반면에 deque의 데이터 입구는 두개로 앞과 뒤로 데이터를 추가, 삭제할 수 있다.

📪deque 메서드 정리

생성

from collections import deque

deq = deque()

deq2 = deque([1,2,3,4]) 

deq3 = deque(maxlen=3)

• 초기값을 설정해 줄 수 있다.
• maxlen 설정으로 최대크기를 설정할 수 있다
• 만약 deque의 크기가 maxlen보다 크다면 head로 데이터가 삭제되고, tail로 데이터가 추가된다. (왼쪽으로 밀려간다)

deq.append(1)  // deque([1], maxlen=3)
deq.append(2)  // deque([1, 2], maxlen=3)
deq.append(3)  // deque([1, 2, 3], maxlen=3)
deq.append(4)  // deque([2, 3, 4], maxlen=3)
deq.append(5)  // deque([3, 4, 5], maxlen=3)
deq.append(6)  // deque([4, 5, 6], maxlen=3)

🍕추가

1. append( ) : tail에 추가
2. appendleft( ) : head에 추가
3. insert(idx,value): idx번째 위치에 value를 추가
   • 만약 deque의 범위를 넘어선 idx를 참조하면 tail에 추가된다.

🧑‍🔧삭제

1. pop() : tail 제거
2. popleft() : head 제거
3. remove(value) : 순회하면서 첫번째 찾은 value 제거
4. clear() : 모든 요소를 삭제

🐁조회

1. count(value) : value와 같은 값의 갯수
2. index(value,[start [,end]]) : value의 index를 반환

🧨그 외

1. reverse() : 반대로 뒤집음

deq = deque([1,2,3,4,5,6])
deq.reverse()

# ([6, 5, 4, 3, 2, 1])

2. rotate(n=num) : n만큼 오른쪽 회전.
   • n의 음수라면 왼쪽으로

deq = deque([1,2,3,4,5,6])
deq.rotate(1)

# [6, 1, 2, 3, 4, 5]


deq2 = deque([1,2,3,4,5,6])
deq2.rotate(-1)

# [2, 3, 4, 5, 6, 1]

deque로 LRU 알고리즘 구현하기

maxlen으로 쉽게 구현할 수 있지만, 문제를 풀 때는 몰랐기 때문에 다음처럼 구현했다.

if city in lru:
	lru.remove(city)
    lru.appendleft(city)
            
else :
	if len(lru) < cacheSize:
    	lru.appendleft(city)
	else:	
    	lru.pop()
        lru.appendleft(city)

• 데이터가 캐시에 존재한다면 cache hit 해당 데이터를 삭제하고, head에 추가한다.

• 데이터가 캐시에 존재하지 않다면 cache miss
  1. 캐시사이즈가 충분하다면 head에 추가한다.

  2. 부족하다면 tail을 삭제하고 head에 추가한다

maxlen으로 구현하기

maxlen으로 쉽게 구현할 수 있다.

from collections import deque

def solution(cacheSize,cities):
    deq = deque(maxlen=cacheSize)
    excute_time = 0
    for city in cities:
        city = city.lower()
        if city in deq:
            excute_time +=1
            deq.remove(city)
            deq.appendleft(city)
        else :
            excute_time +=5
            deq.appendleft(city)

    return excute_time

• maxlen 설정을 해줌으로서 데이터를 추가할 때 cacheSize를 신경쓰지 않고 구현할 수 있다.
• 문자열 메소드 lower()으로 소문자로 치환한다

후기

1. LRU 알고리즘이 무엇인지 배웠다.
2. 파이썬 deque 메소드 사용법을 배웠다.
3. 파이썬 만세