가치투자자

LRU (Least Recently Used) 알고리즘 코딩테스트 문제에 나온 LRU 알고리즘에 대해 정리해보고자 한다. LRU 알고리즘은 페이지 교체 알고리즘이기에 페이지 교체 알고리즘에 대해 간단하게 살펴보고 가자. 1. 페이지 교체 알고리즘 페이지 교체 알고리즘은 새로운 페이지를 실행하려고 하지만 메모리가 없을 때 기존의 어떤 페이지를 교체할지 결정하는 알고리즘이다. 이러한 알고리즘에는 다음과 같은 종류들이 있다. 1) FIFO (First-in, First-Out) 메모리에 적재된 순서대로 내보내는 알고리즘으로, 큐(queue)를 이용해 저장할 수 있다 장점 : 구현이 간단하고 이해하기 쉽다 단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되어야 하며, Belady의 모순이라는 현상으로 인해..

스택(stack)과 큐(queue) 스택과 큐. 처음 들었을 땐 어려울 수 있지만, 쉽게 설명해보고자 한다. 1. 스택 (Stack) 스택(stack) 은 데이터를 아래에서 위로 쌓아올리는 구조를 말한다. 이때 데이터를 추가하거나 제거할 때 위에서부터 추가/삭제해야 하며, 이러한 자료구조를 LIFO(후입선출, Last-in, First-out)이라고 한다. 예로는 다음과 같은 것이 있을 수 있다. 브라우저창에서 뒤로가기 새로운 주소에 접속하면 그 방문기록이 히스토리 스택 아래에서부터 쌓일거고, 뒤로 돌아간다는건 맨 위에 쌓인 방문기록에서 아래로 돌아가는 것 Ctrl+Z로 실행 취소하여 직전 상태로 되돌아가기 역순 문자열 만들기 가장 마지막에 입력된 문자부터 출력하기 때문 수식의 괄호 검사 연산자 우선순위..