6080 : 캐시 교체 정책 시뮬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
캐시 교체 정책 시뮬레이션
주어진 페이지 요청 순서와 캐시 정책에 따라 캐시 미스(Cache Miss) 횟수를 구하시오.
구현할 정책:
-
-
-
구현 힌트:
- LRU: 큐 + 해시셋 또는 OrderedDict
- FIFO: 큐
- LFU: 최소힙 + 해시맵
[제약 조건]
• 요청 수 $N$: $1 \le N \le 10{,}000$ (정수)
• 캐시 크기 $K$: $1 \le K \le 100$ (정수)
주어진 페이지 요청 순서와 캐시 정책에 따라 캐시 미스(Cache Miss) 횟수를 구하시오.
구현할 정책:
-
LRU: Least Recently Used — 가장 오래 전에 사용된 페이지 교체-
FIFO: First In First Out — 가장 먼저 들어온 페이지 교체-
LFU: Least Frequently Used — 사용 빈도가 가장 낮은 페이지 교체구현 힌트:
- LRU: 큐 + 해시셋 또는 OrderedDict
- FIFO: 큐
- LFU: 최소힙 + 해시맵
[제약 조건]
• 요청 수 $N$: $1 \le N \le 10{,}000$ (정수)
• 캐시 크기 $K$: $1 \le K \le 100$ (정수)
입력 설명
첫째 줄에 캐시 크기 C (1 ≤ C ≤ 1,000)와 요청 횟수 N (1 ≤ N ≤ 10,000)이 주어집니다.
둘째 줄에 N개의 페이지 번호가 공백으로 주어집니다.
셋째 줄에 정책 문자열(LRU, LFU, FIFO)이 주어집니다.
둘째 줄에 N개의 페이지 번호가 공백으로 주어집니다.
셋째 줄에 정책 문자열(LRU, LFU, FIFO)이 주어집니다.
출력 설명
캐시 미스의 총 횟수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 8
1 2 3 4 1 2 5 1
LRU
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5