LRU(Least Recently Used, 카카오 캐시 문제 변형, 삽입정렬 응용) / c / 제한시간 없음

▣ 문제

- 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.

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

2

3

1

6

7

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

5

2

3

1

6

2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용 한다면 Cache Hit가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으 로 위치하게 된다. 5 2 3 1 6 ---> 3 5 2 1 6 캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

5

2

3

1

6

                      ↓

3

5

2

1

6

 

▣ 입력설명

- 첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다. 두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.

 

▣ 출력설명

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

 

▣ 입력 예시

5 9 1 2 3 2 6 2 3 5 7

 

▣ 출력 예시

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

 

<내 코드>

#pragma warning(disable:4996)
#include <stdio.h>

int main() {
	int s, n, i, j;
	int cache[1000] = { 0 };
	int temp;
	int cmd;
	int cur = 0;
	int pos = -1;
	scanf("%d %d", &s, &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &cmd);
		temp = cmd;

		pos = -1;
		if (cur > s) cur = s;
		for (j = 0; j < cur; j++) {
			if (temp == cache[j]) {
				pos = j;
				break;
			}
		}

		//cache miss
		if (pos == -1) {
			for (j = cur; j >= 0; j--) {
				cache[j + 1] = cache[j];
			}
			cache[0] = temp;
			cur++;

		}
		//cache hit
		else {
			for (j = 0; j < cur; j++) {
				cache[j + 1] = cache[j];
			}
			cache[0] = temp;
		}

	}

	for (i = 0; i < s; i++) {
		printf("%d ", cache[i]);
	}

	return 0;
}

cur는 cache 메모리 내에서 현재 크기를 알려주는 변수이다. cache miss가 나올때마다 cur++을 해줌으로써 cache 메모리의 현재 크기를 나타냈다. cache 메모리는 s값을 넘어갈수 없기 때문에 'if (cur > s) cur = s;' 라는 조건문을 사용했다.

 

pos는 'cache hit'가 생기는 위치를 알려주는 변수로 사용했다. cache 메모리중 temp값과 같은 메모리가 있으면 'pos=j'를 통해서 그 위치를 저장했다.

 

cache miss와 hit의 경우 삽입정렬의 개념을 사용했다.

한가지 케이스만 안되는데 이유를 모르겠음

 

<수정한 코드>

#pragma warning(disable:4996)
#include <stdio.h>

int main() {
	int s, n, i, j;
	int cache[20] = { 0 };
	int cmd;
	int pos = -1;
	scanf("%d %d", &s, &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &cmd);

		pos = -1;
		for (j = 0; j < s; j++) {
			if (cmd == cache[j]) {
				pos = j;
				break;
			}
		}

		//cache miss
		if (pos == -1) {
			for (j = s-1; j >= 1; j--) {
				cache[j] = cache[j - 1];
			}
			
		}
		//cache hit
		else {
			for (j = pos; j >= 1; j--) {
				cache[j] = cache[j - 1];
			}
		}
		cache[0] = cmd;
		
	}

	for (i = 0; i < s; i++) {
		printf("%d ", cache[i]);
	}

	return 0;
}

cache hit가 날때 pos부터 시작해서 이전값을 앞으로 끌어당기는 코드로 짜야 효율적임

 

cache[0] = cmd 는 cache hit나 miss 둘다 쓰는 코드이기 때문에 굳이 따로따로 쓸 필요가 없음

 

.

 

내가 사용한 불필요한 변수들 : cur temp

 

이런것만 줄여도 코드를 보거나 짤때 잘 정리된것같다