245. 캐시

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

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

• 큐 사용

<내 풀이>

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    cache = deque([0 for _ in range(cacheSize)])
    # 캐시 길이 설정
    # 캐시 맨 앞에 있을 수록 최근에 쓰인거, 맨 뒤에 있는 애가 오래된 거 , 맨 뒤애 
    # 아이를 뽑아버려야 하지 
    if cache : # 캐시가 존재하면 
        for city in cities : 
        	# 캐시 안에 내가 찾는 city 있나 찾기 
            if city.lower() not in cache : 
                cache.pop()
                cache.appendleft(city.lower())
                answer+=5
            else : 
                cache.remove(city.lower())
                cache.appendleft(city.lower())
                answer+=1
    
    else : # 캐시용량 0 이면 매번 5초씩 걸림 바로 여기로 빼주기
        answer = 5*len(cities)
            
    return answer
    

< 내 틀렸던 풀이, 문제점>

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    cache = deque([0 for _ in range(cacheSize)])
    if cache : 
        for city in cities : 
            if city.lower() not in cache : 
                cache.pop()
                cache.appendleft(city.lower())
                answer+=5
            else : 
                answer+=1
    
    else : 
        answer = 5*len(cities)
            
    return answer
    

힝 75 점~
테케 11, 15, 18, 19, 20 wrong

아마도 LRU(Least Recently Used) 에 대한 미숙지인듯

LRU 알고리즘 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법
https://j2wooooo.tistory.com/121

• 아 ㅇㅋㅇㅋ 원래 캐시에 있으면 그대로 두었는데, 그 아이 빼서 맨 앞에 다시 appendleft 해줘서 이번에 쓰였다고 갱신시켜줘야겠다.

NICE!

위거 바로 반영해주니까 맞음

<반성 점>

• 문제에서 제시된 조건 지나치지 말자

<배운 점>

https://j2wooooo.tistory.com/121

• LRU 말고도 여러 페이지 교체 알고리즘이 있다.

페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있습니다.

FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법

단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있음.

LFU : 가장 적은 횟수를 참조하는 페이지를 교체

단점 : 참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생

LRU : 가장 오랫동안 참조되지 않은 페이지를 교체

단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생