CS 공부/알고리즘

LRU(Least Recently Used) 알아보기

LRU 알고리즘은 페이지 교체 알고리즘 종류 중의 하나이다. 우선 페이지 교체 알고리즘이란 무엇인지 살펴보자. 0. 페이지 교체 알고리즘 페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.즉 가상기억장치를 모두 같은 크기의 블록으로 편성하여 운용하는 기법이다. 이때의 일정한 크기를 가진 블록을 페이지라고 한다. 페이지 교체 알고리즘은 온라인 알고리즘의 일종이다. 페이징 기법? 컴퓨터가 메인 메모리에서 사용하기 위해 2차 기억 장치로부터 데이터를 저장하고 검색하는 메모리 관리 기법이다. -위키백과- 온라인 알고리즘? 전산학에서 온라인 알고리즘이란 시작할 때 모든 입력 정..

[탐색 알고리즘] - DFS 이해하기

코테를 하면서 dfs랑 bfs를 이해하기가 좀 어려웠다. 그래도 머리가 좀 굵어져서인지 최근에는 코테 문제를 풀면서 dfs를 어느 정도 활용할 수 있게 되었다. 오늘 이 시간에는 dfs에 대해 이해하면서 코테 사이트에서 본 문제를 예제 삼아 어떻게 풀었는지에 대해 흐름을 따라가고자 한다. 1. DFS 1.1 정의 탐색 알고리즘 종류 중의 하나이다. Depth First Search. 줄여서 DFS로 불리며 우리나라 말로는 '깊이 우선 탐색'으로 표기할 수 있다. 말 그대로 탐색 시 깊숙이 들어가서 우선 탐색한다. 1.2 구현 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다..