프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
캐시 교체 알고리즘 LRU를 처음 만났다. 관련 내용을 정리하면서 개념을 익혔다.
페이지 교체 알고리즘과 LRU Cache
운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다. 페이징 기법으로 메모리를 관리하는
suebin-log.tistory.com
Kakao Tech 블로그에서 문제 해설을 보니 이 문제의 정답률은 45.26%이다.
물론 당연하다 . 나도 보자마자 살짝 당황했다 .
신기한 건 문제 풀고, 운영체제 강의 듣는데 바로 LRU 에 대해 배워서 반가웠다 !
LRU (Least Recently Used)는 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.
LRU 캐시 교체 알고리즘 구현은 보통 Queue, ArrayList, LinkedList를 사용하는 것 같다.
Java에서는 LinkedList가 Queue의 구현체라고 한다.
그래서 LinkedList를 사용했다.
아래는 LinkedList 메소드이다.
add(Object object)는 LinkedList의 마지막에 데이터를 추가한다.
remove(int index)는 해당 인덱스 위치의 값이 지워지는 것이지만,
remove(Object object)는 해당 값이 없다면 false, 있다면 지우고 true를 반환한다고 한다.
이 문제는 세 가지 경우를 생각하면 된다.
1) cache size가 0인 경우
이 문제에서 중요한 포인트는 cache size가 0인 경우를 잊지 말고 생각해야 한다는 점이다.
cache size가 0이면 모든 경우는 cachs miss이므로 그냥 cities의 길이에 5를 곱해주면 된다.
2) cache hit 인 경우
3) cache miss 인 경우
아래는 문제 풀이 코드이다.
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
// cache size가 0이면 모든 경우는 cache miss 이다.
if (cacheSize == 0) return cities.length*5;
int answer = 0;
LinkedList<String> cache = new LinkedList<>();
for (int i=0; i<cities.length; i++) {
// 대문자로 통일한다.
String s = cities[i].toUpperCase();
// cache hit 인 경우 실행시간은 1이다.
if (cache.remove(s)) {
answer += 1;
cache.add(s);
}
// cache miss 인 경우 실행시간은 5이다.
else {
answer += 5;
if (cache.size() >= cacheSize) {
cache.remove(0);
}
cache.add(s);
}
}
return answer;
}
}

'Algorithms > programmers' 카테고리의 다른 글
Programmers, [3차] 방금그곡 : Java (0) | 2022.12.08 |
---|---|
Programmers, 오픈채팅방 : Java (0) | 2022.12.07 |
Programmers, [1차] 다트 게임 : Java (0) | 2022.12.06 |
Programmers, [1차] 뉴스 클러스터링 : Java (0) | 2022.12.06 |
Programmers, [1차] 비밀지도 : Java (0) | 2022.12.02 |