sm 기술 블로그

캐시 교체 알고리즘 LRU : 캐시에서 메모리를 다루기 위해 사용되는 알고리즘으로 새로운 정보가 들어왔을 때 사용한지 가장 오래된 데이터를 제거하고 새로운 데이터를 삽입한다. 용어 1) Cache Hit CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우, Cache Hit이라고 한다. 2) Cache Hit CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않을 떄는 Cache Miss라고 함.

우선순위 큐 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙을 이용한다. 힙(Heap) 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조. 여러 개의 값 중에서 최대값과 최솟값을 찾아내는 연산이 빠르다. 최대 힙 (Max Heap)❝ key(부모노드) ≥ key(자식노드) ❞ 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다. 최소 힙 (Min Heap)❝ key(부모노드) ≥ key(자식노드) ❞ 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진..

이분 탐색(Binary Search) 정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 차는 것이 아니라 탐색범위를 절반씩 줄여가며 찾는 방법이다. 예시) 1 2 3 4 5 6 라는 값에서 6을 찾고자 한다. 배열의 중간에 위치한 3이라는 값과 6을 비교한다. 6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로 3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도한다. 이제 456 남았으므로 다시 중간값인 5와 찾고자하는 대상인 6을 비교한다. 6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색을 다시 시도한다. 이제 6만이 남아았는데 6과 6을 비교하면, 값이 일치하므로 탐색을 종료한다. 자바 코드..

분할정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 알고리즘 설계 유형 1)Divide : 문제가 분할이 가능한 경우 2개 이상의 문제로 나눈다. 2)Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다. 3)Combine : Conquer한 문제들을 퉁합하여 원래 문제의 답을 얻는다. 분할정복 알고리즘은 최소한 두 개의 하위 문제를 생성하므로 재귀 호출을 여러번 실행한다. 사용정렬 퀵정렬 특정 원소 피봇을 기준으로 주어진 배열을 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용하는 방식이다. 1)Divide 피봇 하나를 선택하여 피봇을 기준으로 2개의 부분 배열로 ..