[알고리즘] Least Recently Used(LRU) 알고리즘 / [1차] 캐시

Least Recently Used 알고리즘이란?

- 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

- 컴퓨터의 자원은 한정적이며, 한도내에서 최고의 효율을 얻기 위해 여러 알고리즘이 존재, 그 중에 하나.

   (FIFO,OPT,LRU,LFU,MFU 등등..)

 

 

방법 

첫번째 : 페이지에 저장 된 데이터가 언제 사용되었는지를 알 수 있게하는 부분을 구현해서 제일 오랫동안 참조되지 않는 데이터를 제거 하는 방법.

두번째 : 페이지에 데이터를 큐 형식으로 저장하는 방식.

            페이지내에 데이터가 존재한다면 데이터를 페이지 내에서 제거하고 맨 위로 다시 올리고,

            존재하지 않는다면, 바로 입력하여 맨 아래에 있는 데이터를 삭제하는 과정을 진행.

 

 

 

예제 그림

 

 

 

위 그림에서 7번, 9번같은 상황은 참조하는 값이 이미 페이지에 존재하며 Cache Hit 라고 하며, 

나머지 상황들이 존재하지 않을때 새로 교체 됨으로 Cache Miss 라고한다.

 

 

 

응용

https://programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

 

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

int solution( int cacheSize, vector<string> cities ) {

	if( cacheSize == 0 ) {
		return cities.size() * 5;
	}
	int answer = 0;
	int tempcacheSize = 0;
	vector<string> cach;

	for( auto city : cities ) 
    {
    
		transform( city.begin(), city.end(), city.begin(), ::tolower );
		auto it = find( cach.begin(), cach.end(), city ); //해당 도시가 있는지 확인 find 함수

		if( it == cach.end() )
		{ //없을 때
			answer += 5; //cach miss

			if( tempcacheSize >= cacheSize ) //사이즈 초과 시
				cach.erase( cach.begin() ); //맨앞의 도시 목록 삭제
			else
				tempcacheSize++;
		}
		else
		{ //이미 있을 때
			answer += 1; //cach hit			
			if( tempcacheSize >= cacheSize ) //사이즈 초과 시
				cach.erase( it ); //도시 목록 삭제
			else
				tempcacheSize++;
		}
		cach.push_back( city );



	}
	return answer;
}

 

 

 

 

 

 

 

 

 

이미지 참고 블로그 : 

gomguard.tistory.com/115

페이지 교체 알고리즘 - LRU