[인프런 C++] 37. Least Recently Used (카카오 캐시 문제 변형)

🍧 문제

LRU 알고리즘 : Least Recently Used. 가장 최근에 사용되지 않은 것. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘. 

만약 캐시의 사이즈가 5이고, 작업이 2 3 1 6 7 순으로 저장되어 있다면(맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업)

 

1. cache miss : 해야할 작업이 캐시에 없는 상태. 위상태에서 만약 새로운 작업인 5번 작업을 cpu가 사용한다면 cache miss가 되고, 모든 작업이 뒤로 밀리고 5번 작업은 캐시의 맨 앞에 위치한다. 5 2 3 1 6 (7번 작업은 캐시에서 삭제된다)

 

2. cache hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 cpu가 사용한다면, cache hit가 되고, 3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다. 5 2 3 1 6 👉 3 5 2 1 6

 

캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 n개의 작업을 cpu가 차례로 처리한다면 n개의 작업을 처리한 후 캐시 메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

 

🍧 입력

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

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

 

🍧 출력

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

캐시메모리가 비어 있는 부분은 0으로 출력합니다.

 

 

🍧 1트 (강의 풀이)

삽입정렬 활용. 선생님은 어떻게 이런 생각을 하셨을까..! 나는 a[0]에만 집중했는데.. 😂

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main(void){
	freopen("input.txt", "rt", stdin);
	
	int s, n, a, pos, i, j;
	cin >> s >> n;
	int c[s];
	
	for(i = 1; i <= n; ++i){
		cin >> a;
		pos = -1;
		for(j = 0; j < s; ++j){
			if(c[j] == a){
				pos = j;
			}
		}
		
		if(pos == -1){
			for(j = s-1; j >= 1; --j){
				c[j] = c[j-1];
			}
		}
		else{
			for(j = pos; j>=1; --j){
				c[j] = c[j-1];
			}
		}
		
		c[0] = a;
	}
	
	for(int i = 0; i < s; ++i){
		cout << c[i] << ' ';
	}
	
	return 0;
}

 

아닙니다. 흑흑