[Algorithm] 37. Least Recently Used(카카오 캐시 문제 변형)

 

인트로

LRU 페이지 교체 알고리즘을 간단하게 구현하는 문제이다.

 

문제에서도 설명하겠지만 LRU란 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 중 하나이다. 

 

LRU(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가 되고, 3번 앞에 있는 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이다.

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

입력

5 9
1 2 3 2 6 2 3 5 7

출력

7 5 3 2 6

코드 설명

LRU 캐시의 메커니즘을 이해하면 쉽게 풀 수 있다.

 

1) Hit or Miss?

▶작업 번호를 보고 Cache Hit인지 Miss인지 판별하기.

 

2) Cache Miss 

▶기존에 있던 모든 작업이 뒤로 밀리고 맨 앞에 새로운 작업이 들어간다.

 

3) Cache Hit

▶작업을 맨 앞으로 가져오고 기존에 있던 작업은 한 칸씩 뒤로 밀린다.

 

 

본 문제가 어려웠다면 참고하시길 바랍니다.

삽입 정렬(Insertion Sort) 코드와 시간 복잡도

[Algorithm] 삽입 정렬(Insertion Sort) 코드와 시간 복잡도 (+ 예제)

 

참고로 LRU 캐시는 Double Linked List로 구현하는 게 일반적이다. 하지만 나는 배열로 간단하게 해결했다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int s, n, i, j, k, taskID;
	bool hit;
	
	cin >> s >> n;

	vector<int> cache(s, 0);


	for (i = 0; i < n; i++)
	{
		hit = false;
		cin >> taskID;

		for (j = 0; j < s; j++)
		{
			if (cache[j] == taskID)
			{
				hit = true;
				break;
			}
		}

		if (hit)
		{
			for (k = j; k >= 1; k--)
				cache[k] = cache[k - 1];
		}
		else
		{
			for (k = s - 1; k >= 1; k--)
				cache[k] = cache[k - 1];
		}

		cache[0] = taskID;
	}


	for (int i = 0; i < s; i++)
		cout << cache[i] << " ";
}