알고리즘/이론

가. 세그먼트 트리 a. 무엇인가 - 어떤 배열의 구간합을 트리형태로 저장 b. 특징 - 배열로 구간합을 저장하고 (S[i]= S[i-1]+A[i]) 원하는 구간을 (S[R] - S[L-1])의 형태로 구현이 가능[O(1)] - 하지만 배열의 값이 바뀌는 경우 바뀔때마다 구간합을 더해서 저장해야한다 O(N*변경) - 세그먼트 트리는 이를 O(logN)으로 만들어 줄 수 있다. 나. 구현 a. DFS 및 이분탐색의 활용 - node는 1번부터 시작하며 node*2가 왼쪽 자식노드 node*2+1이 오른쪽자식 노드가 된다. - 트리의 구성은 이분탐색으로 쭉쭉 내려가면서 start랑 end가 같아질때 해당 노드번호에 요소를 저장한다. - 리프에 저장이 끝나면 위로 돌아와서 해당구간을 더한 값을 저장해준다. p..

가. 무엇인가? a. 캐시 알고리즘 - 데이터를 빠르게 가져오기도 하고 DB 부하를 줄이기 위해 캐시를 많이 사용한다. - 하지만 캐시에도 용량이 있기 때문에 지워주면서 사용해야한다. - 이런 캐시를 관리하는 여러 알고리즘이 존재한다. b. LRU - Least Recently Used, 최근까지 적게 hit된 캐시데이터를 지우는 방법이다 나. 구현 a. LinkedHashMap을 활용 - LinkedHashMap에는 두가지 정렬 모드가 있다. ( ordering mode, insertion-order mode) => 들어온 순서를 그대로 가져가는 모드, access로 가져가는 모드 - access 모드를 이용해 쉽게 LRU를 구현할 수 있다. public static void main(String[] ..

가. 무엇인가 a. 정렬 - 싸이클이 없는 방향그래프에서 정점들을 일렬로 나열하는 알고리즘이다. => 각 정점에 대해서 순위를 부여함 ex. 강의 수강 순서도 b. 시간복잡도 - O(N+M) DFS 탐색시간 + O(N) 뒤집는시간 = O(N+M) 나. 구현 a. DFS를 활용 public class 위상정렬 { public static void main(String[] args) { int N = 7; List[] graph = new ArrayList[N]; for(int i = 0; i < N; i++) { graph[i] = new ArrayList(); } graph[0].add(4); graph[0].add(5); graph[1].add(3); graph[1].add(4); graph[2].ad..

가. 무엇인가 a. 최단경로 - 시작정점부터 모든 정점으로 가는 최단경로를 구하는 알고리즘 => 가중치가 양수일 경우에만 사용가능 - 진행 0. 모든 정점이 가지고 있는 가중치합(시작정점부터 도착정점까지의 최단경로)을 INF(엄청큰값) 초기화한다. 1. 현재 정점(동그리미)이 가진 간선들중 가장 최소값을 가지는 간선의 정점을 방문한다. => 이때 방문 정점이 가지고 있는 가중치합은 여러 정점을 거쳐왔을수도 있다. 2. 현재 경로의 가중치합과 방문정점이 가지고 있는 가중치의 합을 비교해서 최소값으로 업데이트한다. 3. 현재 시점에서 가중치합이 더 작았다면 방문정점에서 다시 1번을 수행한다. 나. 구현하기 a. 배열 public class 다익스트라 { public static void main(String..