주의! 본 게시물은 프로그래머스 '[1차] 캐시' 문제에 대한 중요 내용을 포함하고 있습니다. 풀기 전이시라면 이 점 참고해주시길 바랍니다!
링크: https://school.programmers.co.kr/learn/courses/30/lessons/17680
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제를 읽으면서 나온 조건 중 '캐시 교체 알고리즘은 LRU를 사용한다'라는 표현이 있었고 이 LRU를 알지 못하면 문제를 정상적으로 풀 수 없다라는 생각이 들어 LRU에 대해 공부했다.
LRU
LRU란 Lease Recently Used의 줄임말로, 메모리를 관리하는 운영체제에서 사용하는 페이지 교체 알고리즘중 하나로, 새로운 페이지를 할당받아야 할 때, 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다. 표로 살펴보면 다음과 같다.
| 시간 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 참조값 | 1 | 2 | 3 | 4 | 3 | 2 | 2 | 1 | 3 |
| 페이지 (크기: 3) |
1 | 1 | 1 | 2 | 2 | 4 | 4 | 3 | 2 |
| 2 | 2 | 3 | 4 | 3 | 3 | 2 | 1 | ||
| 3 | 4 | 3 | 2 | 2 | 1 | 3 |
어떤 참조값을 페이지에 저장할 때, 참조값이 페이지에 존재한다면 존재하던 값이 맨 위로 다시 올라가게 되고 기존에 존재하지 않아도 참조값이 들어갈 공간이 페이지에 존재한다면,일단 저장된다. 그렇게 진행되다 참조값이 들어갈 공간이 페이지에 부족해진다면 페이지는 가장 오래된 참조값부터 삭제하기 시작한다.
이번 문제를 통해 페이징 기법을 알게 되었다.
'TIL' 카테고리의 다른 글
| TIL - 20221009 (0) | 2022.10.09 |
|---|---|
| TIL - 20221008 (객체와 Map 성능 차이) (0) | 2022.10.08 |
| TIL - 20221006 (비트 연산자) (0) | 2022.10.06 |
| TIL - 20221005 (continue 정리) (1) | 2022.10.05 |
| TIL - 20221004 (유클리드 거리와 맨해튼 거리) (1) | 2022.10.04 |