LRU 알고리즘이란 무엇인가?

▏목적

 

      ◦ LRU 알고리즘 이해하기

 

 

 

▏시작하는 말

 

정처기 자격증 준비했을 때 이론을 공부했었다. 그런데 마침 오늘 프로그래머스에서 문제를 보는데 LRU를 사용해야 하는 문제였다. 그래서 오늘은 그 LRU알고리즘을 설명해보려고 한다. 

 

 

 

▏LRU 란 무엇인가?

 

LRU (Least Recently Used) : 가장 오랫동안 참조하지 않은 페이지를 교체하는 기법

 

페이지 교체 알고리즘들의 종류중 하나로 가장 최근에 사용되지 않은 페이지를 제거하는 알고리즘이다.

대표적인 방법으로 전에 포스팅했던 Queue 형식을 생각하면 된다.

 

 

 

▏원리

 

크기가 4인 배열이 있다고 가정했을 때, 처음 4번은 들어온 순서대로 넣어주면 된다.

 

하지만 오른쪽 처럼 숫자 5를 넣으려고 한다면 가장 먼저 넣었던 1 (오래된 데이터)를 제거하고 넣어주면 된다.

 

 

 

 

여기서 궁굼증이 하나 생길 수 있다.

만약 이미 존재하고 있는 데이터를 넣으려고 한다면 순서는 어떻게 될까?

 

아래 그림을 살펴보면 색을 기준으로는 노랑 - 파랑 - 빨강 순으로 오래된 순서다. 따라서 무언갈 제거해야한다면 이와같은 순으로 제거하면 되는것이다.

 

보라색 박스를 보면되는데 그 왼쪽에 이미 존재하는 5를 다시 넣는다면 기존데이터인 5를 삭제하고 새롭게 넣어주면 된다. 

이와같은 방법으로 5,6,7,8 모두 갱신했다면 다음 9를 넣을때도 똑같이 가장 오래된 6을 제거하고 9를 넣어주면 된다.

 

 

 

 

 

▏관련 예제

 

이 알고리즘으로 푼 문제에 관한 설명을 보고 싶다면 다음 링크를 참고하면 좋다.

https://ddukbaegi.tistory.com/59 

[프로그래머스(programmers)] (2018 KAKAO BLIND RECRUITMENT) 캐시

 

 

 

▏참고자료

 

https://hwiyong.tistory.com/398