LRU(Least Recently Used) Algorithm

백준 문제

https://www.acmicpc.net/problem/4568

4568번: LRU Caching

LRU(Least Rescently Used ) Algorithm

가장 오래전에 추가된 것은 캐시에서 제거하자는게 핵심 아이디어이다.

 

LRU 알고리즘에서 주어지는 것은 캐시의 크기이다.

캐시의 크기가 허용하는 만큼, 가장 최근에 들어온 자료는 뒤에 추가해준다.

만약 캐시의 크기가 꽉차면, 가장 오래된 것을 제거해주고, 새로운 것을 추가해준다.

여기서 주의할 것은, 이미 캐시 안에 있는 것이 또 들어올 경우인데, 이때에는 캐시에서 기존의 것을 제거하고, 새로 들어온 것을 뒤에 추가해주면 된다.

사용하는 자료구조는 map과 queue로 충분하다.(아무튼 유동적으로 추가/삭제 되면 상관 X)

자료가 캐시에 존재하는지 빠르게 확인하기 위해 map을 사용하고, 추가/삭제를 쉽게 해주기 위해 queue를 사용한다.

 

소스 코드 링크 : 깃허브

 

프로그래머스 스킬 체크 레벨2에서 2017 카카오 코테 문제 3번이 나왔는데, 해당 문제가 LRU를 사용한 것이었다.