가치투자자

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

백준 2164번 : 카드2 🔗 문제 링크 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 💬 문제 큐(queue) 에 대한 이해가 있다면 더 잘 이해할 수 있고, 큐를 몰라도 쉽게 이해할 수 있는 문제이다. 숫자 N이 주어지므로 1부터 N까지 담고 있는 배열을 생성해준다. 맨 위에 있는 수, 즉 배열 첫 번째 요소를 제거(shift)해준다. 그 다음 위에 있는 수를 빼서(shift) 맨 밑으로 옮겨준다(push). 그리고 단 1장의 숫자가 남을..

연결리스트 (Linked List) 큐(queue)에 해당하는 알고리즘 문제를 풀다가 시간 복잡도 문제를 해결하기 위해 연결리스트에 대해 공부해보았다. 1. 연결리스트란? 연결리스트(Linked List) 는 index 번호를 사용하는 배열과 달리 연결(link)을 이용해 구현한 리스트를 말한다. 배열의 경우엔 아래처럼 index 번호로 값을 알 수 있다. 즉, index 번호와 값이 서로 연결되어 있다. const arr = ['a', 'b', 'c']; console.log(arr[1]) // index 1번의 값은 b 하지만 연결리스트는 각각의 값들이 서로 연결되어 있다. 아래의 사진을 보면, 10이라는 값에는 10이라는 data뿐만 아니라 10과 연결된 20의 주소(Link)까지도 담고 있다. 이..