[algorithm] 2018 Kakao Blind Recruitment 1차 - 캐시

1. 문제

 

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

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

 

 

2. 풀이

def solution(cacheSize, cities):
    answer=0
    mycache = []
    for city in cities:
        lowcase = city.lower()
        if lowcase in mycache:
            answer+=1
            mycache.remove(lowcase)
            mycache.append(lowcase)
        else:
            answer+=5
            mycache.append(lowcase)
            if len(mycache) > cacheSize:
                mycache = mycache[1:]

    return answer

LRU 알고리즘을 구현하는 문제.

해당 도시가 cache에 들어있다면  +1 없다면 +5를 한다.

cache는 가장 최근에 방문한 도시가 가장 뒤로 관리되므로 캐시에 들어있는 도시를 방문할 경우 이미 캐시안에 있는 해당 도시를 지우고 append 시켜서 가장 뒤로 오도록 한다.

cache 크기가 cacheSize를 초과하면 제일 앞을 잘라낸다.

 

 

3. algorithm

 

페이징 기법(paging) : 컴퓨터가 메인메모리에서 사용하기 위해 데이터를 저장하고 검색하는 메모리 관리기법

페이지 부재 : CPU가 access 한 페이지가 주 기억장치에 없는 경우 , 해당 페이지를 주 기억장치로 가져와야함.

 

페이지 교체 알고리즘 이란?

 -  페이지 부재 발생시 어떤 페이지를 교체할 것인가에 대한 정책

 

FIFO(First In First Out)

- 가장 오래된 page를 교체한다. FIFO queue를 사용하며 가장 구현이 간단하다.

 

LRU(Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체한다.

 

LFU(Least Frequently Used)

- 사용 빈도가 적은 페이지를 교체한다.

 

 

4. 후기

잘 생각하면 구현 자체는 어렵지 않았지만 cache 사이즈가 0인 경우도 고려해야 했다.