LRU 알고리즘 + 카카오 문제

LRU 알고리즘이란 Oracle DATABASE의 메모리 관리를

효율적으로 하기 위해 고안된 대표적인 알고리즘으로

최신 데이터를 메모리에 유지시키고

오래된 데이터는 메모리에서 내보내게 하는 알고리즘

예를 들어,

SQL > select sal from emp where ename='scott';

위 SQL 문장은 메모리에 정보가 올라와있다면 1초,             -> cashe hit

메모리에 정보가 없어 디스크에서 조회하면 5초가 걸린다.    -> cashe miss

(걸리는 시간은 예시일 뿐)

하지만 메모리 공간이 한정되어 있어, 무한히 데이터를 올릴 수 없다.

따라서 오래된 데이터는 버리고 최신 데이터로 올린다.

'최근에 내가 검색한 데이터는 다시 검색할 확률이 높을거야' 라고 가정한다.

예제 : 2017 카카오 블라인드 1차 캐시

이게 무슨 말인가 했더니, 그냥 리스트에 넣고, 입력한 캐시 크기만큼의 길이의 리스트를 따로 만들어서

리스트의 요소를 하나씩 넣고 요소가 겹치면 +1, 안 겹치면 +5 하면서 그 리스트의 길이는 유지시키는 거뿐이었다.

말을 왜.. 이해를 못하겠냐 ㅠㅠ

이해하고 나면 할만했는데 이해하기 전까진 도대체 무슨 문제인가 했다.

갈 길이 멀구나..

내 코드

def kakao(cities,cacheSize):
    t=0
    for i in range(len(cities)):
        cities[i]=(cities[i].lower())
    list=[]
    for i in range(len(cities)):
        if cities[i] in list:
            t+=1
        else:
            t+=5
            list.append(cities[i])
            if len(list)>cacheSize:
                list=list[1:]
    print(t)
    return
kakao(["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"],3)
kakao(["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"],3)
kakao(["Jeju","Pangyo","Seoul","NewYork","LA","SanFrancisco","Seoul","Rome","Paris","Jeju","NewYork","Rome"],2)
kakao(["Jeju","Pangyo","Seoul","NewYork","LA","SanFrancisco","Seoul","Rome","Paris","Jeju","NewYork","Rome"],5)
kakao(["Jeju","Pangyo",'NewYork','newyork'],2)
kakao(["Jeju","Pangyo","Seoul","NewYork","LA"],0)
kakao(['Jeju', 'Jeju','Jeju'],3)