[알고리즘] LRU with Java, remove, 시나리오의 중요성

4. Least Recently Used

 

설명

캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가

필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.

철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.

LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다.

캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.

캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후

캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다.

두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.

출력

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.

예시 입력 1 

5 9
1 2 3 2 6 2 3 5 7

예시 출력 1

7 5 3 2 6

힌트

오늘 배운 것

1. 알고리즘 시나리오의 중요성

. 시나리오를 한번 쭉 그려보는 것이 중요하다는 것을 알게 되었다. 그래야 상상을 하고, 전체적인 코드를 구현할 수 있게 되는 것 같다.

 

2. remove 

https://hianna.tistory.com/564

[Java] ArrayList에서 특정 값 삭제하기

특정 값을 삭제하기 위한 문법을 배웠다. 

기본 int 값을 넘기면 index가 삭제된다. 하지만 Integer or Object 로 넘기면 해당 value가 지워지게 된다는 점을 착안해서 코드를 구현했다.

 

2. 문제 풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int S = kb.nextInt();
        int N = kb.nextInt();
        List<Integer> arr = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            arr.add(kb.nextInt());
        }

        solution(S,arr);

    }

    private static void solution(int s, List<Integer> work) {
        List<Integer> arr = new ArrayList<>();

        for (int i = 0; i < work.size(); i++) {
            int w = work.get(i);

            // 이미 값이 존재 한다면
            if(isExistArr(w,arr)){
                // Integer 값으로 넘긴 해당 요소를 지워주고, 맨 앞에 더해준다.
                arr.remove(Integer.valueOf(w));
                arr.add(w);
                continue;
            }

            // 값이 존재하진 않지만, size full 인 경우
            if(arr.size()>=s){
                arr.add(w);

                // 가장 뒤의 숫자를 지워준다.
                // 출력 시 거꾸로 출력하게 됨으로 0 인덱스가 가장 마지막에 나오게 된다.
                arr.remove(Integer.valueOf(arr.get(0)));
                continue;
            }
            // 사이즈도 작고, 같은 수도 없다면 걍 더해준다.
            arr.add(w);
        }
        for (int j = arr.size()-1; j >=0; j--) {
            System.out.print(arr.get(j)+" ");
        }
    }

    private static boolean isExistArr(int w, List<Integer> arr) {
        for (int i = 0; i < arr.size(); i++) {
            if(arr.get(i) == w){
                return true;
            }
        }
        return false;
    }
}

. 강의에서는 삽입정렬을 이용하여 코드를 구현했다. 역시 강의를 같이 들으니 내가 생각하지 못했던 구현력을 키울 수 있는 부분을 계속 짚어주셨다.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int S = kb.nextInt();
        int N = kb.nextInt();
        int [] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = kb.nextInt();
        }

        solution(S,arr);

    }
    // 삽입정렬을 이용한 solution
    private static void solution(int s, int[] work) {
        int[] ans = new int[s];

        for(int x : work){
            int pos = -1;
            
            // 캐쉬 내부에 존재하면 index를 해당 위치로 바꿔준다.
            for (int i = 0; i < ans.length; i++) {
                if(x == ans[i]){
                    pos = i;
                }
            }
            // cache miss 인 경우
            if(pos == -1){
                for (int i = ans.length-1; i >= 1; i--) {
                    ans[i] = ans[i-1];
                }
            }else{
                // cache hit 인 경우
                for (int i = pos; i >= 1 ; i--) {
                    ans[i] = ans[i-1];
                }
            }
            ans[0] = x;
        }
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i]+" ");
        }
    }
}