Least Recently Used(카카오 캐시 문제 변형)(37)

37. Least Recently Used(카카오 캐시 문제 변형)
캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다. 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가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으

로 위치하게 된다.
5 2 3 1 6
--->
3 5 2 1 6
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 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 0 0 0 0
2 1 0 0 0
3 2 1 0 0
2 3 1 0 0
6 2 3 1 0
2 6 3 1 0
3 2 6 1 0
5 3 2 6 1
7 5 3 2 6

 

 

#include <iostream>

using namespace std;


int C[20];

int main(void)
{
	int  n, s, pos,a,j;
	cin >> s>>n;

	for (int i = 0; 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++)
		printf("%d ", C[i]);
	return 0;
	
}

 

 

삽입 정렬을 이용한 문제이다.

 

3

2

1

0

0

제일 최근에 쓴 숫자는 맨 왼쪽에 온다.

 

값이 다 차있는데 새로운 값이 들어오면 맨 오른쪽의 값은 사라진다. 

 

여기서 중요한건 

 

새로 들어오는 값이

1) 배열 안에 있는 상태인지 

2) 배열 안에 없는 상태인지 

둘을 나누어서 구현하면 된다.

 

1)의 상황이라면 그 배열 안에 있던 값을 맨 앞으로 땡기고, 나머지는 한칸씩 뒤로 민다.

2)의 상황이라면 그냥 새 값이 맨 처음에 오고 나머지 뒤로 한 칸씩 땡기면 된다.

 

코드 구현을 보자.

 

for (int i = 0; i < n; i++)
	{
		cin >> a;
		pos = -1;
		for (j = 0; j < s; j++)
		{
			if (C[j] == a)
				pos = j;
		}

i는 몇 번이나 값을 받을지를 정한다.

새로들어온 값을 a에 저장하고 pos를 -1로 지정한다.

pos가 -1이라면 배열 안에 새로 들어올 값이 없는 상태이다.

 

그리고 for문을 돌려 배열 안에 새로 들어올 값이 있는지를 확인하고, 있다면 pos=j로 하고, 없다면 -1인 상태가 된다.

 

if (pos == -1)
			{
				for (j = s - 1; j >= 1; j--)
					C[j] = C[j - 1];
			}

-1인 상태 = 배열 안에 새로 들어오는 값이 없는 상태에는 값을 한칸씩 뒤로 미룬다.

배열의 크기이며 s-1을 해야 인덱스 마지막에서부터 하나씩 줄여나갈 수 있다.

 

else
			{
				for (j = pos; j >= 1; j--)
					C[j] = C[j - 1];
			}
			C[0] = a;

배열안에 있을 때의 경우

한칸씩 뒤로 미룬다. 근데 그 시작점이 pos, 맨 위에서 그 값이 있던 곳에서부터 앞에 있던 값을 한칸씩 뒤로 민다.

 

그리고 처음 값을 a로 초기화해준다.

 

그리고 출력한다.