URL https://programmers.co.kr/learn/courses/30/lessons/17680
캐시
- 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
- 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
- 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
- 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.
입력 형식
- 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
- cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
- cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
출력 형식
- 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.
조건
- 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
- cache hit일 경우 실행시간은 1이다.
- cache miss일 경우 실행시간은 5이다.
Cache란?
- 자주 사용하는 데이터나 값을 임시저장소에 미리 복사해 놓는것
- 빠를수록 더 비싸고, 저장공간이 작음 (registers -> l1 cache -> l2 cache -> l3 cache -> ram -> SSD -> HDD)
- Cache에 저장되어 있으면 DB에서 읽지않고 그냥 바로 가져옴 이것을 Cache Hit이라고 함,
- 반대로 Cache에 없어서 실제 DB에서 읽는것을 cache miss라고 함
- LRU는 캐시가 꽉 찼다면 가장 오래된것을 지우고 새로운 정보를 마지막에 넣음
문제풀이
- 아래의 5가지 경우의 수가 있음
- 1) cachessize가 0이 아닐때
- 1-1) 같은 도시가 캐시에 있을때 (cache hit)
- 캐시에서 도시를 빼오니까, 빼온 캐시는 삭제하고 다시 도시를 맨 뒤에 저장하고 time은 +1
- 1-2) 같은 도시가 캐시에 없을때 (cache miss)
- 1-2-1) 캐시가 가득 찼을때
- 캐시의 맨 앞을 삭제하고, 새로운 도시를 캐시에 저장 후 time +5
- 1-2-2) 캐시가 가득 안찼을때
- 새로운 도시를 캐시에 저장 후 time + 5
- 1-2-1) 캐시가 가득 찼을때
- 1-1) 같은 도시가 캐시에 있을때 (cache hit)
- 2)cachesize가 0일때
- 캐쉬에 저장이 안되니 cities의 갯수만큼 * 5를 해주면됨
- 위의 경우의 수를 고려하여 time을 구하여 return 하면됨
- cache의 개념이 없어서 조금 햇갈렸었음
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def solution(cacheSize, cities):
# 기준점이 되는 times와 cache를 만듬
times = 0
cache = []
# 모든 단어를 소문자로 바꿈, 소문자와 대문자 구별이 없다고 하니
temp_cities = [city.lower() for city in cities]
temp_cities
# cachesize가 0이 아닐때 0이면 저장을 못하니까, 전부다 5초로 해야함
if cacheSize != 0:
for city in temp_cities:
# 같은 도시가 캐시에 있을때 -> cache hit
if city in cache:
cache.pop(cache.index(city))
cache.append(city)
times += 1
# 같은 도시가 캐시에 없을때 -> cache miss
else:
# 캐시가 가득 찼을때
if len(cache) >= cacheSize:
cache.pop(0)
cache.append(city)
times += 5
# 캐시가 비었을때
else:
cache.append(city)
times += 5
# cachesize가 0일때
else:
times += len(temp_cities) * 5
return times
1
2
3
cacheSize = 3
cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
solution(cacheSize, cities)
1
50
1
2
3
cacheSize = 3
cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]
solution(cacheSize, cities)
1
21
1
2
3
cacheSize = 2
cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]
solution(cacheSize, cities)
1
60
1
2
3
cacheSize = 5
cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]
solution(cacheSize, cities)
1
52
1
2
3
cacheSize = 2
cities = ["Jeju", "Pangyo", "NewYork", "newyork"]
solution(cacheSize, cities)
1
16
1
2
3
cacheSize = 0
cities = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
solution(cacheSize, cities)
1
25