<JAVA/자바> LRU 알고리즘

💡 개념

LRU(Least Recently Used) 알고리즘이란?
가장 오랫동안 사용되지 않은 데이터를 교체하는 캐싱 기법으로, 제한된 크기의 캐시에서 데이터를 효율적으로 관리하기 위해 사용됩니다.

캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 때 바로 사용해서 처리속도를 높이는 장치이다.

---

📌 과정

1. 입력 데이터를 읽어오며, 현재 캐시에 해당 데이터가 있는지 확인한다.

2. 캐시 히트 시

   • 해당 데이터를 가장 최근 위치(0번 인덱스, head)로 이동합니다.

3. 캐시 미스 시

   • 캐시가 가득 찬 경우, 가장 오래된 데이터(데이터 중 가장 마지막 인덱스)를 제거합니다.
     새로운 데이터를 캐시의 가장 최근 위치(head)에 삽입합니다.

주요 변수

• S: 캐시의 크기.
• N: 입력 데이터 개수.
• lru: LRU 캐시를 나타내는 배열.

주요 메서드

1. find(int input)

   캐시에서 데이터의 위치를 검색한다.

• 리턴 값
  • 캐시 히트: 데이터의 인덱스
  • 빈 공간 발견: 해당 인덱스
  • 캐시 미스: -1

2. shiftAndInsert(int input, int pos)

• 캐시 히트 또는 빈 자리 발견 시: 데이터를 해당 위치로 옮기고 나머지 데이터를 뒤로 이동
• 캐시 미스 시: 가장 오래된 데이터를 제거하고 새로운 데이터를 삽입

---

👨‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int S, N;
    static int[] lru;
    
    public static void solution() {
        for (int idx = 0; idx < N; idx++) {
            int input = Integer.parseInt(st.nextToken());

			// 캐시에서 데이터 찾기
            int pos = find(input);

			// 위치에 따라 데이터 삽입 및 정렬
            shiftAndInsert(input, pos);
        }
    }

    private static int find(int input) {
        for (int idx = 0; idx < S; idx++) {
            // Cache hit
            if (lru[idx] == input)
                return idx;

            // 빈 자리가 있는 경우
            if (lru[idx] == 0)
                return idx;
        }

        return -1; // Cache miss, 메모리가 가득 찬 경우
    }

    private static void shiftAndInsert(int input, int pos) {
        // Cache miss, 마지막 작업을 삭제하고 head 에 새로운 작업을 삽입해야 하는 경우
        if (pos == -1) pos = S - 1;

        for (int idx = pos; idx > 0; idx--) {
            lru[idx] = lru[idx - 1]; // 오른쪽으로 이동
        }

        lru[0] = input; // head 위치에 삽입
    }

    public static void main(String[] args) throws IOException {
        init();

        solution();

        for (int idx = 0; idx < S; idx++) {
            sb.append(lru[idx]).append(" ");
        }
        System.out.println(sb);
    }

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine().trim());
        S = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        lru = new int[S];

        st = new StringTokenizer(br.readLine().trim());
    }
}

---

🚀 실행 과정

입력 데이터

• 캐시 크기(S): 5
• 입력 데이터 개수(N): 9
• 입력 데이터: 1, 2, 3, 2, 6, 2, 3, 5, 7

---

1. 입력 데이터: 1

1. find(1) 호출 → 캐시 미스 (-1).

2. shiftAndInsert(1, -1) 호출 → 1을 삽입.

캐시 상태: [1, 0, 0, 0, 0]

---

2. 입력 데이터: 2

1. find(2) 호출 → 캐시 미스 (-1).

2. shiftAndInsert(2, -1) 호출 → 2를 삽입.

캐시 상태: [2, 1, 0, 0, 0]

---

3. 입력 데이터: 3

1. find(3) 호출 → 캐시 미스 (-1).

2. shiftAndInsert(3, -1) 호출 → 3를 삽입.

캐시 상태: [3, 2, 1, 0, 0]

---

4. 입력 데이터: 2

1. find(2) 호출 → 캐시 히트 (1).

2. shiftAndInsert(2, 1) 호출 → 2를 가장 최근 위치로 이동.

캐시 상태: [2, 3, 1, 0, 0]

---

5. 입력 데이터: 6

1. find(6) 호출 → 캐시 미스 (-1).

2. shiftAndInsert(6, -1) 호출 → 6을 삽입.

캐시 상태: [6, 2, 3, 1, 0]

---

6. 입력 데이터: 2

1. find(2) 호출 → 캐시 히트 (1).

2. shiftAndInsert(2, 1) 호출 → 2를 가장 최근 위치로 이동.

캐시 상태: [2, 6, 3, 1, 0]

---

7. 입력 데이터: 3

1. find(3) 호출 → 캐시 히트 (2).

2. shiftAndInsert(3, 2) 호출 → 3를 가장 최근 위치로 이동.

캐시 상태: [3, 2, 6, 1, 0]

---

8. 입력 데이터: 5

1. find(5) 호출 → 캐시 미스 (-1).

2. shiftAndInsert(5, -1) 호출 → 가장 오래된 데이터(0)를 제거하고 5 삽입.

캐시 상태: [5, 3, 2, 6, 1]

---

9. 입력 데이터: 7

1. find(7) 호출 → 캐시 미스 (-1).

2. shiftAndInsert(7, -1) 호출 → 가장 오래된 데이터(1)를 제거하고 7 삽입.

캐시 상태: [7, 5, 3, 2, 6]

---

최종 결과

• 최종 캐시 상태: [7, 5, 3, 2, 6]