캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.
만약 캐시의 사이즈가 5이고 작업이
순으로 저장되어 있다면,
(맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)
Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작 업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번작업은 캐시의 맨 앞에위치한다.
7번 작업은 캐시에서 삭제된다.
Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용 한다면 Cache Hit가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.
입력 예제
5 9
1 2 3 2 6 2 3 5 7
출력 예제
7 5 3 2 6
풀이:
function solution(size, arr){
// 0으로 이루어진 size크기의 배열 생성
let answer=Array.from({length:size}, ()=>0);
// 매개변수 arr 배열을 forEach를 통해 요소 호출
arr.forEach(x => {
// 반복문을 통해 x 요소가 answer 배열에 포함되어있을경우 저장될 변수
let pos=-1;
// answer배열에 x요소가 포함되어있는지 찾는 반복문
for(let i=0; i<size; i++) if(x===answer[i]) pos=i;
//pos가 -1이면 answer배열에 x요소가 없을경우
if(pos===-1){
//size의 -1이 초기값 (배열의 마지막 인덱스 앞) 부터 1번째 인덱스까지 감소하며 반복문
for(let i=size-1; i>=1; i--){
// answer[i] 는 answer[i-1]이 됨 즉 자신보다 앞의 인덱스요소가 자신이됨
answer[i]=answer[i-1];
}
}
// pos가 -1이 아니고 answer에 x요소가 포함이 되었을경우 즉 pos 변수에 x요소가 포함된 인덱스번호가 저장되었을경우
else{
// i는 pos(x요소의 인덱스) 부터 1번째 인덱스 까지 감소하며 반복문
for(let i=pos; i>=1; i--){
// answer[i] 는 answer[i-1]이 됨 즉 자신보다 앞의 인덱스요소가 자신이됨
// pos 부터 감소하며 반복문이 되기때문에 pos 자리에 있는 값은 앞의 인덱스에 매꿔지며 사라짐.
answer[i]=answer[i-1];
}
}
// answer 배열의 첫번째 인덱스는 무조건 x 요소
answer[0]=x;
});
return answer;
}
let arr=[1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr));