LRU(Least Recently Used) / 선택정렬

LRU (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.LinkedList를 이용해 해결

• LinkedList는 각 노드들이 앞뒤의 참조 주소값으로 연결되어있는 형태이다. 따라서 삭제, 추가가 되어도 각 노드들이 index변경이 없기 때문에 ArrayList에 비해 데이터의 추가, 삭제 처리가 빠르다.
  다만 index가 없기 때문에 특정 index에 접근하기 위해서는 순차 탐색이 필요하므로 효율이 떨어진다. 따라서 정렬, 탐색을 자주 사용하는 경우 List를, 추가/삭제가 잦은 경우 LinkedList를 사용해준다.

public int[] solution(int size, int num, int[] arr) {
	List<Integer> answer = new LinkedList<>();
    for(int i = 0; i < num; i++){
    	for(int j = 0; j < answer.size(); j++){
        	//cash에 저장되 있는 경우 해당 값 제거
        	if(arr[i] == answer.get(j) answer.remove(j);
        }
        answer add(0, arr[i));
        //cash size 유지
        if(answer.size == size+1) answer.remove(size);
    }
    
    return answer;
}

2.알고리즘을 이용해 해결

public int[] solution(int size, int num, int[] arr) {
    int[] answer = new int[size];
    for(int x : arr){
        int index = -1;
        for(int i = 0; i < answer.length; i++){
            //이미 cash에 있는 경우
            if(x == answer[i]) index = i;
        }
        // cash에 있는 경우
        if(index != -1){
            // j앞을 j까지 밀음
            for(int j = index; j >= 1; j--){
                answer[j] = answer[j-1];
            }
        } else{
            // cash에 없는 경우
            for(int j = size-1; j >= 1; j--){
                answer[j] = answer[j-1];
            }
        }
        answer[0] = x;
    }
    return answer;
}

선택정렬(Selection Sort)

선택정렬이란 제자리 정렬 알고리즘 중 하나로, 전체 항의 가장 작은 수를 찾아 맨 앞부터 차례대로 교환해주는 방법이다.
비교회수는 n(n-1)/2이며, 시간 복잡도는 O(n²)이 된다.

✏️ 문제

* 설명
N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.

* 입력
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

* 출력
오름차순으로 정렬된 수열을 출력합니다.

🔍풀이

    public int[] solution(int n, int[] num) {
        int[] answer = num;
        for(int i = 0; i < n-1; i++){
            int idx=i;
            for(int j=i+1; j<n; j++){
                if(num[j] < num[idx]) idx = j;
            }
            int tmp = num[i];
            num[i] = num[idx];
            num[idx] = tmp;
        }
        return answer;
    }