두구둥둥

MST = Minimal Spanning Tree 일단 MST를 알기 전에 Spanning Tree를 알아야 한다! Spanning Tree란, 그래프의 모든 정점을 포함하면서 간선의 수가 최소인 트리이다. Spanning Tree의 조건 N개의 정점 N-1개의 간선 사이클이 없다. MST는 Spanning Tree 중에서 가중치의 합이 최소인 것을 말한다! '마을과 마을을 잇는 도로들이 주어지고, 도로의 길이가 최소가 되게 모든 마을을 이어라.' 와 같은 문제에 사용되는 알고리즘이다. MST 알고리즘 종류 크루스칼 프림 크루스칼 vs. 프림 유형 시간복잡도 따라하세요! 크루스칼 Greedy 간선 중심 O(ElogE) 간적크 프림 정점 중심 O(V^2)/O(ElogV) 간많프 크루스칼 알고리즘 간선중심으..

이진탐색이란? - 특정 데이터를 빠르게 검색할 수 있다. O(logN) - 정렬되어 있는 배열에서 사용 가능하다. 구현 코드 (Java) int binarySearch(int[] arr, int target, int start, int end){ //1. 이진탐색은 무조건 정렬된 배열에서 가능하다. Arrays.sort(arr); //2. 어떤 값을 기준으로 할지를 정하고, 초기값을 정한다. //이 예시에서는 매개변수로 받는걸로 한다. int mid = 0; //start가 end보다 커질때까지 반복 while(start

최단경로 알고리즘이란 그래프에서 노드간의 최단경로를 찾는 알고리즘이다. 대표적인 최단경로 알고리즘 BFS 다익스트라 벨만포드 플로이드 와샬 다음 표는 상황에 따라 어떤 알고리즘을 선택해야 하는지에 대한 표이다. 단일 노드 - 단일 노드 모든 노드 쌍 Edge에 weight 없음 BFS 플로이드 와샬 알고리즘 Edge에 weight 있음 음수 weight 있음 벨만 포드 알고리즘 음수 weight 없음 다익스트라 알고리즘 (출처. https://shnoh.tistory.com/15) 다익스트라 알고리즘 한 정점 A에서 다른 정점으로 가는 촤단경로를 구할 때 사용. 가중치는 0 또는 양수만 가능하다. 그리디를 이용한 알고리즘 O(V^2) O((V+E)logV) // 우선순위 큐를 사용했을때 private v..

다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 최단경로를 찾는 알고리즘이다. 최단경로 알고리즘 종류 다익스트라 벨만포드 플로이드 음의 가중치가 없을 때, 하나의 정점에서 나머지 모든 정점으로의 최단경로를 구할 때 사용된다. 다익스트라 알고리즘은 DP를 활용한다. DP가 가능한 이유 > 최단거리는 여러 개의 최단거리로 이루어져 있기 때문! 시간복잡도 V : 정점의 개수, E : 간선 개수 O(V^2) 우선순위큐 사용시 : O((V+E)logN) O(VlogN) : 미방문 노드 중 현재까지의 최단거리를 가지는 노드 찾기 O(ElogN) : 각 노드마다 이웃한 노드이 최단 거리를 갱신할 때 필요 변수 int[] distance // 최단 거리 저장 boolean[] visite..