가치투자자

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

DFS와 BFS 그래프는 여러 정점(node)과 그 정점들을 연결하는 간선(edge)으로 이루어진 자료구조다. 그래프나 트리 등 비선형 구조로 데이터가 담긴 자료구조는 순차적으로 나열된 선형 구조(배열, 연결리스트, 스택, 큐)에 비해 데이터 탐색이 훨씬 어렵다. 이러한 그래프의 정점들을 처음부터 끝까지 탐색할 때 대표적인 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 자주 쓰이는 이 두 가지 알고리즘에 대해 쉽게 설명해보고자 한다. 1. 깊이 우선 탐색 (DFS, Depth First Search) 깊이 우선 탐색 (DFS) 은 가장 깊이 있는(끝에 있는)정점까지 다 탐색하고, 다시 갈림길로 돌아와 다른 길로 끝까지 탐색하는 알고리즘이다. 쉽게 설명하자면, 여러 드라마들이 ..

유클리드 호제법 (유클리드 알고리즘, Euclidean algorithm) 1. 유클리드 호제법이란? 유클리드 호제법 은 두 수 A와 B의 최대공약수를 구하는 알고리즘이다. 여기서 호제법 이란 두 수가 서로 상대방을 나누어 결국 원하는 수를 얻어내는 알고리즘을 말한다. 1-1. 일반적으로 최대공약수 구하기 보통 최대공약수를 구하기 위해 소인수분해 를 사용한다. 22와 8의 경우, 각각 소인수분해하여 최대공약수 2를 구할 수 있다. 22 = 11 x 2 8 = 2 x 2 x 2 그러나 이 방법의 경우, 숫자가 너무 크거나 숫자가 난해한 경우 소인수분해를 하기 어렵다. 1. 수가 너무 큰 경우 : 2304와 1440 => 최대공약수 288 2. 숫자가 난해한 경우 : 403과 155 => 최대공약수 31 이..

퀵 정렬 (Quick Sort) 1. 퀵 정렬이란? 퀵 정렬(quick sort) 역시 병합 정렬과 마찬가지로 어떤 문제를 2개의 작은 문제로 분리해 각각을 해결하는 분할 정복 알고리즘 중 하나다. 1-1) 차이점 병합 정렬 - 분할 단계에서는 분할만 하고 병합 단계에서 정렬을 한다 퀵 정렬 - 분할 단계에서 정렬이 이루어지며, 병합 시에는 병합만 한다. 퀵 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다. 분할 (Divde) : 입력된 배열을 기준점(pivot)을 기준으로 비균등하게 분할한다. 정복 (Conquer) : 분할된 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 1이 아니면) 순환 호출을 이용하여 다시 분할한다. 결합 (Combine) : 정렬된 부분 배열들을..

병합 정렬 (merge sort) 1. 병합 정렬이란? 병합 정렬(merge sort)은 어떤 문제를 2개의 작은 문제로 분리해 각각 해결한 다음, 이걸 모아서 원래 문제를 해결하는 분할 정복 알고리즘 중 하나다. 병합 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다. 분할(Divide) : 입력된 배열을 같은 크기의 부분 배열 2개로 분할한다. 정복(Conquer) : 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 0 또는 1이 아니면) 다시 분할을 한다. 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다. 병합 정렬은 다음 단계들로 진행된다. 부분 배열의 요소들을 결합할 빈 배열이 필요하다. 부분 배열의 크기(length)가 1이 될 때까지 쪼개준다. 부분 배열의 0번째..