[프로그래머스] [1차] 캐시

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

코딩테스트 연습 - [1차] 캐시

이 문제는 LRU(Least Recently Used) Algorithm을 구현하는 문제이다.  LRU알고리즘은 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법이다. Cache알고리즘 중 가장 유명한 알고리즘 중 하나며, 캐시 메모리를 다루기 위해 주로 사용되는 알고리즘이다. 이러한 알고리즘을 이용하는 이유는 캐시가 사용하는 리소스 양은 제한되어있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장, 접근할 수 있어야 하기 때문이라고 한다. 일반적으로 LinkedList로 구현된 Queue형태를 띄고 있다고 한다.

 

LRU의 작동 원리를 간단하게 살펴보자

 

저장공간이 3인 캐시에서 1,2,3이라는캐시를 넣는 경우에는 아래와 같다

 

3->2->1

 

만약 여기서 2번 캐시를 호출하는 경우에는 2번 캐시를 꺼내서 캐시의 맨 앞에 넣는다.

 

2 -> 3 -> 1

 

4번캐시를 넣어야한다고 가정하자. 근데 저장공간이 3인 캐시이므로 꽉찬 상태이다.이런 경우, 가장 사용을 안하고 있는 마지막 자리에 있는 1을 빼고, 4를 넣어준다.

 

4 -> 2 -> 3 (1은 캐시에서 제거)

 

정리해보면 아래와 같다.

 

<새로운 데이터가 들어오는 경우 : Cache Miss>

• 캐시 공간이 남아있는 경우, 캐시에 넣는다
• 캐시가 가득차있는 경우, 가장 오래된 데이터를 제거하고 넣어준다

<존재하는 데이터가 들어온 경우 : Cache Hit>

• 해당 데이터를 꺼낸다
• 꺼낸 데이터를 가장 최근 데이터 위치(캐시의 맨 앞)로 보낸다.

 

위 LRU개념을 가지고 문제에 주어진대로 풀면 아래와 같다. 단, 캐시 공간이 0인 경우에는 모든 데이터에 대해 Cach Miss만 발생하고, 저장이 되지 않으므로 바로 5 * datalength 를 return 해주면 된다.

 

한가지 더 유의할 점은 아래 입출력 예제를 살펴보자

 

이 예제를 NewYork와 newyork이 다른 데이터로 본다는 관점에서 해석해 보면

 

1) Jeju / + 5

2) Jeju - Pangyo / + 10

3) NewYork - Jeju / + 15

4) newyork - NewYork / + 20

 

다른 데이터로 본다는 관점으로 해석하면 20이 나온다. 이번에는 NewYork와 newyork가 동일한 데이터로 본다는 관점에서 해석해보자

 

1) Jeju / + 5

2) Jeju - Pangyo / + 10

3) NewYork - Jeju / + 15

4) NewYork - Jeju / + 16 (Cache Miss가 아닌 Cache Hit가 발생함)

 

이 관점으로 봐야 예제 입출력과 동일한 값이 나오는 것을 알 수 있다. 즉, 대소문자 구분 없이 내용으로 캐시값을 판별한다는 의미이므로 lower 혹은 upper메소드로 맞춰주고 검사하는것이 좋다

 

from typing import Any
from collections import deque

def solution(cacheSize, cities):
    # CacheSize가 0일 경우에는 Cache miss만 발생한다.
    if cacheSize == 0:
        return 5 * len(cities)
    cache = []
    execution_time = 0
    for i in cities:
        # NewYork, newyork는 동일한 캐시로 취급하는 예시가 있다
        i = i.lower() # i값에 대해서 
        # Cache hit
        if i in cache:
            cache.append(cache.pop(cache.index(i)))
            execution_time += 1
        # Cache miss
        else:
            if len(cache) >= cacheSize:
                cache.remove(cache[0])
                cache.append(i)
                execution_time += 5
            else:
                cache.append(i)
                execution_time += 5
    return execution_time