LRU(Last Recently Used)알고리즘 공부하기

프로그래머스 코딩테스트에서 캐시 관련 문제가 나왔다.

 

LRU가 뭔지 모르는 채로 풀이 예시만 보고 LRU를 간단하게 이해했다.

 

대충 내가 이해한 대로 설명하자면 캐시에 항목이 저장되어 있으면 HIT로 받아들여

출력 속도가 빨라지고 캐시 제일 마지막 칸에 데이터가 저장된다.

 

문제 예시에서 [1,2,3,1,5] 이런 Data를 입력받으면 캐시(길이3)는 [1] > [1,2], > [1,2,3] > [2,3,1] > [3,1,5]

이런 식이였다.

 

그래서 나는 아~ 오래된 거랑 중복되면 캐시 맨 뒤에 넣어주면 되겠다 싶어서

캐시에 들어오려는 Data가 있으면 캐시 맨 첫번째 데이터를 shift로 밀어내고 마지막에 Data를 넣어줬는데

당연히 틀렸다.

 

반례는 캐시배열 중간에 중복된 Data가 있을 수 있는 경우였는데,

그래서 캐시.includes로 있는지 여부를 확인하고 indexOf와 slice로 제거한 뒤 push로 맨 마지막에 넣어줬다.

 

코딩테스트를 하면서 알고리즘이나 코딩문제를 수학적으로 풀어내는 눙력이 전반적으로 향상되고 있음을

스스로 느낀다.. 2단계도 정복해보자!!

 

나보다 더 좋은 설명을 해준 분의 글을 첨부한다. 참고바람^^

https://rangsub.tistory.com/124