알고리즘/이론5 LRU Cache Algorithm(Least Recently Used) LRU 알고리즘이란? 해석 그대로 가장 오래된 데이터를 없애고 새로운 데이터를 넣는 알고리즘이다. 캐시에서 사용되는 알고리즘 캐시는 많은 데이터를 담지 못하므로 이러한 페이지 교체 알고리즘이 필요하다. 이중연결리스트를 사용하여 node를 관리한다. 설명 ListNode로 사용할 클래스를 만든다. 접근 성능 개선을 위해 Map을 사용하여 key의 존재 유무를 빠르게 찾을 수 있다. head는 새로 들어올 node를 nodeList에 연결해 주기 위한 역할(next만 사용) tail은 삭제될 node를 가리키기 위한 역할 (prev만 사용) put 메서드 새로운 노드 생성 키 존재 여부확인 존재하는 경우, Listnode에서 해당 키를 가진 노드를 삭제 후 inserToHead 호출 존재하지 않은 경우, 또.. 2019. 11. 3. 프림 알고리즘(Prim's algorithm) 프림 알고리즘이란? 가중치가 있는 연결된 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘 그래프에 간선이 많이 존재하는 밀집 그래프인 경우 적합하다. 시간 복잡도 - O(ElogV), 그래프가 충분히 뺵빽한 경우 피보나치 합을 이용하여 더 빠르게 값을 구할 수 있다. 설명 그래프에서 하나의 노드를 선택한 후 트리를 만든다. 그래프의 모든 간선이 들어있는 집합을 만든다. 모든 노드들을 방문하기 전까지 반복 ->트리 자체와 연결된 간선들 중에서 가중치가 가장 작은 간선을 선택 후 연결되어 있는 노드로 넘어감. 반복이 끝났을 때 최소비용 신창트리가 완성! 관련 문제 섬 연결하기 - https://eoghks0521.tistory... 2019. 10. 17. 깊이 우선 탐색(depth-first search, DFS) 깊이 우선 탐색이란? 트리에서는 왼쪽 노드부터 확인하여 탐색하지 않은 경우에 왼쪽노드에 넘어가고를 반복하여 마지막 깊이까지 들어간 뒤 마지막 노드의 인접 노드들을 전부 탐색한 뒤 백트래킹을 하며 탐색하지 않은 노드들을 탐색한다. 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색. 얻어진 해가 최단 경로가 된다는 보장이 없다. 탐색 지점에서 일직선으로 탐색을 해나가는 느낌 설명 방문을 체크하는 배열 존재 시작 노드를 설정한 뒤 DFS메서드를 불러오고 시작노드의 방문체크를 true로 바꾼다. DFS메서드에서는 설정한 시작노.. 2019. 10. 10. 너비 우선 탐색(Breadth-first search, BFS) 너비 우선 탐색이란? 시작 정점에서 인접한 모든 정점들을 우선 탐색하는 방법 OPEN List(검색 가능성이 있는 노드의 집합)는 큐(Queue)를 사용해야지만 레벨 순서대로 접근 가능 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 경로가 매우 길 경우, 탐색 가지가 급격히 증가하여 보다 많은 기억 공간이 필요하다. 탐색 지점에서 둥그렇게 탐색을 해나가는 느낌 설명 방문을 체크하는 배열존재 시작노드를 큐에 넣고 탐색시작 이중 반복문을 사용! - 큐 안에 있는 값을 pop하고 pop해서 나온 값의 인접한 노드에 대해서 가져오고 방문한 적 없는 노드에 경우 방문체크해주고 큐안에 노드를 넣어준다. 예시 코드(Java) import java.io.*; import java.util.*; /* 인접 리스.. 2019. 10. 6. 퀵 정렬(Quick sort) 퀵 정렬이란? 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행 수행속도가 매우 빠르다. 설명 임의의 수를 pivot(피봇)이라는 이름으로 기준을 잡는다.(pivot은 중간값이 적절) pivot값을 기준으로 pivot값보다 작은 값은 pivot 앞으로 큰 값은 뒤로 가게 값들의 위치를 바꾼다. 이 과정이 마무리되면 pivot은 중간에 들어가 있게 되어 있다.(중간값이 적절한 자리를 찾음) pivot을 기준으로 좌우로 나누고(분할) 나눠진 리스트에 대해서 다시 1, 2, 3 과정을 반복한다(재귀). 예시 피벗은 p, 리스트 왼쪽.. 2019. 9. 30. 이전 1 다음
