LRU (Least Recently Used)

LRU

LRU 알고리즘에 대해 알아보자.

LRU 알고리즘은 Least Recently Used의 약자로, 직역하자면 가장 최근에 사용되지 않은 것이라는 의미를 가진다.

 

예를 들어 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다고 했을 때, 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘이다.

 

만약 캐시 사이즈가 5이고 작업이 [A, B, C, F, D]순으로 저장되어 있다면,

1. Cache Miss
   • 해야할 작업이 캐시에 없는 상태라면  Cache miss가 된다.
   • 모든 작업이 뒤로 밀리며 해당 작업이 캐시의 맨 앞에 위치하게 된다.
     • 예) G일 경우 → [G, A, B, C, F]
     • 이때 D는 캐시에서 삭제
2. Cache Hit
   • 해야할 작업이 캐시에 있는 상태라면 Cache Hit가 된다.
   • 해당 작업이 있는 캐시의 앞에(최근 캐시) 있는 캐시들은 뒤로 밀리고, 해당 작업이 캐시의 맨 앞에 위치하게 된다.
     
     • 예) C일 경우 → [C, A, B, F, D]

 

문제

코딩테스트 연습 - [1차] 캐시

위 프로그래머스 [1차] 캐시 문제를 통해 LRU 알고리즘을 코드로 구현해보도록 하자.

 

풀이

풀이 코드

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int time = 0;
        String[] cache = new String[cacheSize];

        if (cacheSize <= 0) // 캐시가 없을 경우 모두 miss 처리
            return cities.length * 5;

        for (String city : cities) {
            int pos = -1;

            for (int i = 0; i < cacheSize; i++)
                if (city.equalsIgnoreCase(cache[i])) // 캐시에 있다면 hit
                    pos = i;

            if (pos == -1) { // miss 상황일 경우
                for (int i = cacheSize - 1; i >= 1; i--)
                    cache[i] = cache[i - 1];
                time += 5;
            } else { // hit 상황일 경우
                for (int i = pos; i >= 1; i--)
                    cache[i] = cache[i - 1];
                time += 1;
            }

            cache[0] = city;
        }

        return time;
    }   
}

 

풀이 설명

• 주어진 cacheSize만큼 캐시를 담을 배열을 만들어준다.
• cacheSize가 0 이하인 경우는 캐시를 사용할 수 없기 때문에 모두 Cache Miss 처리한다.
• cacheSize가 1 이상인 경우는 Cache Hit인지, Cache Miss인지 구별이 필요하다.
  • 캐시의 위치를 나타내는 pos를 -1로 초기화해준다.
  • 캐시를 모두 탐색하며 해당 도시(city)가 있는지 확인한다.
    • 있다면 Cache Hit : pos를 찾은 캐시의 위치로 바꿔준다.
    • 없다면 Cache Miss 
• Cache Hit의 경우
  • pos 앞에 있는 캐시를 한칸씩 뒤로 밀고, 해당 도시(city)를 캐시 맨 앞에 위치시킨다. (이때 i=1까지 반복, 이유는 맨 앞 캐시는 현재 작업이 되기 때문에 )
  • 실행시간(time)에 5를 추가한다.
• Cache Miss의 경우
  • 캐시를 모두 뒤로 한칸씩 밀고, 해당 도시(city)를 캐시 맨 앞에 위치시킨다. (이때 i=1까지 반복, 이유는 맨 앞 캐시는 현재 작업이 되기 때문에 )
  • 실행시간(time)에 1를 추가한다.

 

이해가 쉽도록 문제에 나와있는 테스트 케이스를 그림으로 설명하겠다.

// test case
cacheSize = 3
cities = { "Jeju", "Pangyo", "NewYork", "newyork" }

 

이렇게 LRU 알고리즘에 대해 간단하게 정리해보았다. 😊