2025. 2. 21. 21:04ㆍ프로그래머스/LV.2
문제링크: [1차] 캐시
문제설명
지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.
제한조건
입력 형식
- 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
- cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
- cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
출력 형식
- 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.
조건
- 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
- cache hit일 경우 실행시간은 1이다.
- cache miss일 경우 실행시간은 5이다
문제풀이
캐시...처음에는 글자 수로 따지는 건가 하다가 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다. 이 문구를 보고 아 캐시메모리지..했다.
그래서 리스트를 만들고 캐시 사이즈보다 작을때 와 메모리가 다 찼을때(리스트 길이가 캐시 사이즈와 같을때), 검색단어가 메모리에 있을때와 없을때 총 4가지를 조건문으로 만들어서 계산을 해주었다.
LRU(Least Recently Used) 라 써있기 때문에 뭔지 몰라도 젤 최근에 들어간것이 먼저 사용되는구나 알 수 있다.
메모리에 검색단어가 있으면 리스트에서 삭제 후 다시 젤 마지막원소로 넣어주었다.
메모리에 검색단어가 없으면 맨 앞 리스트 원소를 삭제 후 해당 단어를 마지막 원소로 넣어주었다.
나의코드
def solution(cacheSize, cities):
answer = 0
from collections import deque
# 조건문으로 비교를 해야하기 때문에 미리 cache 사이즈만큼 만들 필요 X
cache=deque([])
# 영어대소문자를 구분하지 않기 때문에 소문자든 대문자든 하나로 바꾸어줘야함
# for city.lower() in cities: ## 이렇게 바로 하는건 안되네
for city in cities:
city=city.lower()
# 캐시사이즈가 0일때 따로 생각해줘야함
if cacheSize==0:
return len(cities)*5
if len(cache)<cacheSize and city not in cache:
cache.append(city)
answer+=5
elif len(cache)<cacheSize:
cache.remove(city)
cache.append(city)
answer+=1
elif city not in cache:
cache.popleft()
cache.append(city)
answer+=5
else:
cache.remove(city)
cache.append(city)
answer+=1
return answer
참고하기
def solution(cacheSize, cities):
import collections
cache = collections.deque(maxlen=cacheSize)
time = 0
for i in cities:
s = i.lower()
if s in cache:
cache.remove(s)
cache.append(s)
time += 1
else:
cache.append(s)
time += 5
return timedeque에는 maxlen이라는 함수가 있나보다... 최대길이를 정해줘서 검색단어가 메모리에 있는지 없는지만 신경쓰면 된다.
def solution(cacheSize, cities):
if cacheSize == 0:
return len(cities) * 5
cache = []
time = 0
for city in cities:
if city.lower() in cache:
cache.remove(city.lower())
cache.append(city.lower())
time += 1
else:
time += 5
if len(cache) == cacheSize:
cache.pop(0)
cache.append(city.lower())
return time검색단어가 메모리에 있을때는 리스트길이가 cache 사이즈보다 커지지 않으니 조건문으로 구분해 줄 필요가 없다.
조건문을 하나 안써서 시간을 줄일 수 있음. 코드도 더 간결하게 쓸 수 있다.
# LRU cache reference : https://www.kunxi.org/blog/2014/05/lru-cache-in-python/
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.tm = 0
self.cache = {}
self.lru = {}
def get(self, key):
if key in self.cache:
self.lru[key] = self.tm
self.tm += 1
return self.cache[key]
return -1
def set(self, key, value):
if len(self.cache) >= self.capacity:
# find the LRU entry
old_key = min(self.lru.keys(), key=lambda k:self.lru[k])
self.cache.pop(old_key)
self.lru.pop(old_key)
self.cache[key] = value
self.lru[key] = self.tm
self.tm += 1
def solution(cacheSize, cities):
process_time = 0
if cacheSize != 0:
cache = LRUCache(cacheSize)
for city in cities:
if cache.get(city.lower()) == -1:
cache.set(city.lower(), city)
process_time += 5
else:
process_time += 1
else:
process_time = len(cities) * 5
return process_time음...혼자 코드를 읽어보려 했지만 약간 이해가 안되는 부분들이 있어서 결국 도움을 받음
주어진 코드는 LRU(Least Recently Used) Cache를 활용하여 도시 이름을 캐시하는 방식으로 동작하며, 주어진 도시 목록을 처리하는 데 걸리는 총 시간을 계산하는 프로그램입니다.
각 부분을 자세히 설명해줄게요.
1. LRUCache 클래스
LRU 캐시는 가장 오랫동안 사용되지 않은 항목을 제거하는 캐시 알고리즘입니다.
이 클래스를 사용하면 일정 용량(capacity)을 가진 캐시를 구현할 수 있습니다.
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity # 캐시 최대 크기
self.tm = 0 # 시간 역할을 하는 변수
self.cache = {} # 실제 캐시 저장소 (key: 도시명, value: 캐시된 값)
self.lru = {} # LRU 추적 (key: 도시명, value: 최근 접근 시간)
- capacity: 캐시의 최대 크기
- tm: 최근 접근한 시간을 저장하는 변수
- cache: 캐시된 데이터를 저장하는 딕셔너리
- lru: 각 키가 마지막으로 접근된 시간을 기록하는 딕셔너리
2. get() 메서드
캐시에서 데이터를 가져오는 함수입니다.
def get(self, key):
if key in self.cache:
self.lru[key] = self.tm # 현재 시간을 기록하여 최신으로 갱신
self.tm += 1 # 시간 증가
return self.cache[key] # 캐시된 값 반환
return -1 # 캐시에 없으면 -1 반환
- 만약 key가 cache에 존재하면:
- lru를 업데이트하여 가장 최근 사용 시간을 갱신
- 해당 값을 반환
- 존재하지 않으면 -1을 반환하여 캐시 미스(Cache Miss)를 나타냄
3. set() 메서드
새로운 데이터를 캐시에 저장하는 함수입니다.
def set(self, key, value):
if len(self.cache) >= self.capacity: # 캐시가 가득 찬 경우
# 가장 오래된 (즉, LRU) 키 찾기
old_key = min(self.lru.keys(), key=lambda k:self.lru[k])
self.cache.pop(old_key) # 캐시에서 제거
self.lru.pop(old_key) # LRU에서도 제거
self.cache[key] = value # 새로운 값 저장
self.lru[key] = self.tm # 현재 시간 저장
self.tm += 1 # 시간 증가
- 만약 캐시가 가득 차 있으면:
- self.lru에서 가장 오래된 키(min())를 찾아 삭제
- 새로운 데이터를 추가하고 lru를 업데이트
- lru의 값이 작으면 가장 적은 시간일때 저장된 것이니 가장 오래된 원소임. 그래서 min 사용
4. solution() 함수
LRU 캐시를 사용하여 도시 이름 목록을 처리하는 함수입니다.
def solution(cacheSize, cities):
process_time = 0 # 총 처리 시간
if cacheSize != 0:
cache = LRUCache(cacheSize) # 주어진 크기의 LRU 캐시 생성
for city in cities:
if cache.get(city.lower()) == -1: # 캐시에 없으면 (Cache Miss)
cache.set(city.lower(), city) # 캐시에 추가
process_time += 5 # Cache Miss: 5초 소요
else:
process_time += 1 # Cache Hit: 1초 소요
else:
process_time = len(cities) * 5 # 캐시 크기가 0이면 모두 Cache Miss
return process_time
- cacheSize == 0이면 모든 요청이 Cache Miss(5초 소요)
- cacheSize > 0이면 LRU 캐시를 활용하여 캐시 히트(Cache Hit: 1초) 또는 캐시 미스(Cache Miss: 5초)를 처리
- 도시 이름을 **소문자(.lower())**로 변환하여 대소문자 구분 없이 처리
5. 동작 예시
입력 예시
cacheSize = 3
cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]
print(solution(cacheSize, cities))
LRU 캐시 동작 과정
Step 도시 캐시 상태 Hit/Miss 소요 시간| 1 | Jeju | ["Jeju"] | Miss | +5 |
| 2 | Pangyo | ["Jeju", "Pangyo"] | Miss | +5 |
| 3 | Seoul | ["Jeju", "Pangyo", "Seoul"] | Miss | +5 |
| 4 | Jeju | ["Pangyo", "Seoul", "Jeju"] | Hit | +1 |
| 5 | Pangyo | ["Seoul", "Jeju", "Pangyo"] | Hit | +1 |
| 6 | Seoul | ["Jeju", "Pangyo", "Seoul"] | Hit | +1 |
| 7 | Jeju | ["Pangyo", "Seoul", "Jeju"] | Hit | +1 |
| 8 | Pangyo | ["Seoul", "Jeju", "Pangyo"] | Hit | +1 |
| 9 | Seoul | ["Jeju", "Pangyo", "Seoul"] | Hit | +1 |
총 소요 시간: 5 + 5 + 5 + 1 + 1 + 1 + 1 + 1 + 1 = 21초
6. 개선할 점
이 코드는 기본적인 LRU 캐시 구현이지만, 성능을 더 향상시킬 수 있습니다.
- OrderedDict 활용: Python의 collections.OrderedDict를 사용하면 **get()과 set() 연산을 O(1)**로 최적화할 수 있음.
- 현재 구현의 문제점:
- min(self.lru.keys(), key=lambda k: self.lru[k])는 O(N) 연산 → 성능 저하 발생 가능.
- 딕셔너리 대신 OrderedDict를 사용하면 LRU를 O(1) 연산으로 유지 가능.
개선된 코드
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key) # 최근 사용으로 갱신
return self.cache[key]
return -1
def set(self, key, value):
if key in self.cache:
self.cache.move_to_end(key) # 기존 값 갱신
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # LRU 항목 제거
self.cache[key] = value
이렇게 하면 get()과 set() 연산이 **O(1)**에 실행됩니다.
7. 결론
- 주어진 코드는 LRU 캐시를 이용하여 도시 캐싱을 수행하고, 캐시 히트/미스를 기반으로 처리 시간을 계산.
- OrderedDict를 사용하면 더 효율적인 LRU 캐시를 구현 가능.
- 이 방식은 캐시 최적화 및 성능 향상이 중요한 문제에서 많이 사용됨 (예: 운영체제의 페이지 교체 알고리즘, 데이터베이스 쿼리 캐싱 등).
📌 OrderedDict란?
OrderedDict는 Python의 collections 모듈에서 제공하는 순서를 유지하는 딕셔너리입니다.
일반적인 dict와 기능은 비슷하지만, 항목이 추가된 순서를 유지하는 특징이 있습니다.
🔹 기본적인 dict와 OrderedDict 차이
파이썬 3.7부터 일반적인 dict도 삽입 순서를 유지하지만, OrderedDict는 몇 가지 추가 기능을 제공합니다.
1️⃣ 일반 dict 예시 (파이썬 3.7 이상)
d = {} # 일반 딕셔너리
d["b"] = 2
d["a"] = 1
d["c"] = 3
print(d) # {'b': 2, 'a': 1, 'c': 3} (삽입 순서 유지됨)
2️⃣ OrderedDict 예시
from collections import OrderedDict
od = OrderedDict()
od["b"] = 2
od["a"] = 1
od["c"] = 3
print(od) # OrderedDict([('b', 2), ('a', 1), ('c', 3)])
✅ 차이점:
- 일반 dict도 삽입 순서를 유지하지만, **OrderedDict는 더 강력한 기능(항목 이동, 순서 조작 등)**을 제공.
🔹 OrderedDict의 주요 기능
1️⃣ move_to_end(key, last=True)
특정 키를 마지막(또는 처음)으로 이동시킬 수 있음 → LRU 캐시 구현할 때 유용!
od = OrderedDict()
od["a"] = 1
od["b"] = 2
od["c"] = 3
od.move_to_end("a") # 'a'를 맨 뒤로 이동
print(od) # OrderedDict([('b', 2), ('c', 3), ('a', 1)])
od.move_to_end("b", last=False) # 'b'를 맨 앞으로 이동
print(od) # OrderedDict([('b', 2), ('c', 3), ('a', 1)])
2️⃣ popitem(last=True)
- last=True: 마지막 요소 제거 (FIFO → 일반적인 큐처럼 동작)
- last=False: 첫 번째 요소 제거 (LRU 방식처럼 동작)
od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
od.popitem() # 마지막 요소 제거
print(od) # OrderedDict([('a', 1), ('b', 2)])
od.popitem(last=False) # 첫 번째 요소 제거
print(od) # OrderedDict([('b', 2)])
🔹 OrderedDict를 이용한 LRU 캐시 구현
LRU(Least Recently Used) 캐시는 가장 오래된 데이터를 제거하는 캐시입니다.
OrderedDict를 활용하면 O(1) 시간 복잡도로 구현할 수 있음!
✅ LRU 캐시 코드 (OrderedDict 활용)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key) # 사용한 항목을 가장 최근으로 이동
return self.cache[key]
return -1 # 캐시에 없으면 -1 반환
def set(self, key, value):
if key in self.cache:
self.cache.move_to_end(key) # 기존 값 갱신 (가장 최근으로 이동)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # 가장 오래된 항목 제거 (LRU 방식)
self.cache[key] = value # 새 값 추가
# LRU 캐시 테스트
cache = LRUCache(2) # 최대 크기 2
cache.set("a", 1)
cache.set("b", 2)
print(cache.cache) # OrderedDict([('a', 1), ('b', 2)])
cache.get("a") # 'a' 사용 → 최근으로 이동
cache.set("c", 3) # 새로운 값 추가 → 가장 오래된 'b' 삭제
print(cache.cache) # OrderedDict([('a', 1), ('c', 3)])
✅ 시간 복잡도: O(1)
move_to_end()와 popitem()을 사용하면 항목을 O(1) 시간 내에 관리 가능.
🔹 결론
- OrderedDict는 항목 순서를 유지하며 추가적인 기능을 제공하는 딕셔너리.
- move_to_end(), popitem(last=False)를 활용하면 LRU 캐시를 쉽게 구현 가능.
- 성능 최적화가 필요할 때 유용하게 사용할 수 있음! 🚀
=> 여기서 딕셔너리의 벨류값은 딱히 안 중요해보임...그럼 set의 value값도 필요없는 거 아닌가???
📌 self.cache[key] = value가 필요한 이유
맞아요! LRU 캐시에서는 "값(value)" 자체가 중요하지 않다고 했는데,
그럼에도 불구하고 self.cache[key] = value 부분이 필요한 이유가 있습니다.
1️⃣ OrderedDict는 (key, value) 쌍을 저장하는 자료구조
OrderedDict는 단순히 키(key)만 저장할 수 있는 자료구조가 아닙니다.
반드시 (key, value) 형태로 저장해야 합니다.
from collections import OrderedDict
od = OrderedDict()
od["A"] = 100 # (A, 100) 저장
od["B"] = 200 # (B, 200) 저장
print(od) # OrderedDict([('A', 100), ('B', 200)])
✅ 즉, key의 순서를 관리하려면 value도 있어야 하므로, 값을 저장해야 합니다.
(비록 값 자체가 중요하지 않더라도, OrderedDict를 사용하려면 넣어야 함!)
2️⃣ get() 호출 시 실제 값을 반환해야 함
get() 메서드는 캐시에서 값을 가져오는 역할을 합니다.
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key) # 최근 사용된 키를 맨 뒤로 이동
return self.cache[key] # 캐시된 값 반환 (여기가 중요!)
return -1 # 캐시에 없으면 -1 반환
이때, 만약 self.cache[key] = value가 없었다면 self.cache[key]를 반환할 수 없겠죠?
예제
cache = LRUCache(2)
cache.set("A", 100)
print(cache.get("A")) # 100 (저장된 값이 반환됨)
print(cache.get("B")) # -1 (캐시에 없음)
✅ 즉, "값"이 필요 없는 것처럼 보이지만, get()이 정상적으로 작동하려면 저장이 필요합니다.
3️⃣ set()에서 같은 키가 들어왔을 때 값 갱신을 위해
이미 캐시에 존재하는 키를 다시 set() 하면, 기존 값을 새로운 값으로 갱신해야 합니다.
def set(self, key, value):
if key in self.cache:
self.cache.move_to_end(key) # 기존 값 갱신 (최근으로 이동)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # 가장 오래된 항목 제거 (LRU 방식)
self.cache[key] = value # 🔹 새로운 값 저장
예제
cache = LRUCache(2)
cache.set("A", 100) # ("A", 100) 저장
cache.set("A", 200) # 같은 키지만 값 변경
print(cache.get("A")) # 200 (값이 갱신됨!)
✅ 즉, 같은 키가 들어왔을 때 새로운 값으로 덮어쓰기 위해 self.cache[key] = value가 필요합니다.
🚀 결론
self.cache[key] = value는 단순히 OrderedDict의 형식을 맞추기 위한 것만이 아니라:
- OrderedDict는 (key, value) 형태로 저장해야 하기 때문
- get() 호출 시 캐시된 값을 반환해야 하기 때문
- 같은 키가 들어오면 값을 갱신하기 위해 필요함
📌 따라서, "값(value)이 중요하지 않다"는 것은 삭제할 때 결정되는 것이지, 저장할 때는 필수적! 🎯
내말은 value값을 인자로 받지않고 그냥 1 이런식으로 저장하면 안되냐는 거였는데...
📌 굳이 value를 받을 필요가 있을까?
맞아요! **LRU 캐시에서 중요한 것은 "키(key)의 순서"**지,
실제로 저장되는 값(value) 자체는 캐시의 동작에 큰 영향을 주지 않습니다.
그래서 만약 LRU 캐시를 단순히 **"어떤 키가 가장 최근에 사용되었는지"**를 확인하는 용도로만 쓴다면,
굳이 value 값을 외부에서 받을 필요 없이 항상 1 같은 더미 값을 저장해도 됩니다. ✅
✅ 항상 1 같은 값을 저장해도 될까?
네, 가능합니다! 실제로 LRU 캐시에서 값이 의미가 없고, 키의 순서만 필요하다면
우리는 항상 1 같은 값을 저장해도 LRU 캐시의 동작에는 전혀 문제가 없습니다.
🔹 값 대신 1을 저장하는 예제
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key) # 최근 사용된 키를 가장 뒤로 이동
return 1 # ✅ 항상 같은 값(1)을 반환
return -1 # 캐시에 없으면 -1 반환
def set(self, key):
if key in self.cache:
self.cache.move_to_end(key) # 기존 키를 최근으로 이동
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # 가장 오래된 항목 제거
self.cache[key] = 1 # ✅ 항상 1 저장 (값은 의미 없음)
# LRU 캐시 테스트
cache = LRUCache(2)
cache.set("A")
cache.set("B")
print(cache.cache) # OrderedDict([('A', 1), ('B', 1)])
cache.get("A") # 'A' 사용 → 가장 최근으로 이동
cache.set("C") # 새로운 값 추가 → 가장 오래된 'B' 삭제
print(cache.cache) # OrderedDict([('A', 1), ('C', 1)])
✅ 이 코드에서도 LRU 캐시가 정상적으로 동작!
✅ self.cache[key] = 1로 항상 같은 값을 저장하지만, LRU 알고리즘에는 영향 없음.
🔹 그런데도 굳이 value를 받는 이유는?
하지만 일반적으로 LRU 캐시는 **"최근에 사용한 데이터를 빠르게 조회"**하는 목적도 있습니다.
따라서, 캐시에 저장된 실제 데이터를 활용하려면 원래의 value를 유지하는 것이 좋습니다.
🔹 예제: value를 유지하는 경우
cache = LRUCache(2)
cache.set("A", "Hello") # ✅ 값 저장
cache.set("B", "World")
print(cache.get("A")) # "Hello" 반환 (값이 유지됨)
print(cache.get("B")) # "World" 반환
✅ 만약 1을 저장했다면, "Hello"나 "World" 대신 항상 1이 반환되므로 데이터 활용이 불가능
✅ 따라서, 데이터 캐싱을 활용하는 경우에는 원래 value를 유지하는 것이 더 적절함
🚀 결론
🔹 "LRU 캐시에서 값(value)이 꼭 필요할까?" → 상황에 따라 다름
✔ 키의 순서만 필요하다면? → value를 받지 않고, 1 같은 더미 값 저장해도 됨
✔ 캐싱된 데이터를 활용해야 한다면? → value를 그대로 저장하는 것이 필요함
🎯 즉, LRU 캐시가 단순히 "사용 순서"를 관리하는 용도라면 1을 저장해도 문제없지만,
실제 데이터를 캐싱하려면 원래 value를 유지해야 한다! 🚀
'프로그래머스 > LV.2' 카테고리의 다른 글
| [프로그래머스][LV.2] 전화번호 목록 | python3 (0) | 2025.03.05 |
|---|---|
| [프로그래머스][LV.2] [3차] 방금그곡 | python3 (1) | 2025.02.22 |
| [프로그래머스][LV.2] [1차] 프렌즈4블록 | python3 (0) | 2025.02.20 |
| [프로그래머스][LV.2] 예상 대진표 | python3 (0) | 2025.02.18 |
| [프로그래머스][LV.2] 영어 끝말잇기 | python3 (0) | 2025.02.15 |