[JAVA] Union-Find
2022. 6. 6. 14:54
JAVA/알고리즘 개념 정리
Union-Find 란? Union : 특정 2개의 노드를 연결해 1개의 집합으로 묶는 작업 Find : 특정 2개의 노드가 같은 집합에 속해 있는지 확인하는 작업 다음과 같이 6개의 노드가 있다고 가정 (1, 2), (2, 3), (4, 6), (3, 6) 을 연결했을 때, 생기는 그룹은 몇개일까? group[1~6] = [1, 2, 3, 4, 5, 6]으로 초기화 이는 각 index가 속한 그룹의 대표값이라 생각하면 됨 1, 2 연결 노드 1과 노드 2의 대표값이 다름 => group[2]에 1을 넣어줌 => group = [1, 1, 3, 4, 5, 6] 2, 3 연결 노드2와 노드 3의 대표값이 다름 => group[3]에 노드2의 대표값 1을 넣어줌 => group = [1, 1, 1, 4, 5..
[JAVA] 플로이드-워셜 알고리즘 (Floyd-Warshall)
2022. 6. 5. 20:11
JAVA/알고리즘 개념 정리
Floyd-Warshall 알고리즘 이란? 모든 노드간에 최단거리를 구하는 알고리즘 다익스트라, 벨만포드는 한 노드에서 모든노드까지의 최단경로 Floyd-Warshall은 모든노드에서 모든노드까지의 최단 경로 벨만포드와 같이 가중치에 음수가 있어도 가능 시간복잡도 : O(V^3) (V:노드의 수) 위 그래프에서 1 -> 5의 최단경로는 1 -> 3 -> 4 -> 5 임 이 때, 중간지점을 4로 지정해 보면 (1 -> 4) + (4 -> 5) = 1 -> 5 가 항상 성립 Floyd-Warshall은 이 논리를 사용 시작점 : s, 끝점 : e, 중간점 : k => dist[s][e] = min(dist[s][e], dist[s][k] + dist[k][e]) k, s, e는 3중 for문을 통해 모든 경..
[JAVA] 벨만포드 알고리즘 (Bellman-Ford)
2022. 6. 5. 17:13
JAVA/알고리즘 개념 정리
Bellman-Ford 알고리즘 이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복잡도 : O(NE) (N:노드의 수, E: 엣지의 수) 다음과 같은 그래프가 있다고 가정 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면 1 -> 2 = 1 1 -> 2 -> 3 = 2 1 -> 2 -> 3 -> 4 = 4 가 되고 노드 2는 이미 방문했기 때문에 4 -> 2 경로는 고려하지 않음 결과적으로 1 -> 2의 최단경로는 1이 됨 하지만 실제 1 -> 2의 최단경로는 -∞ 임 이를 해결하기 위해 벨만포드 알고리즘 탄생 Bellman-Ford 원리 엣지는 1->2, 4->2, 2->3, 3->..
[JAVA] 다익스트라 (Dijkstra) (+ Priority Queue을 사용한 시간 단축)
2022. 6. 4. 21:51
JAVA/알고리즘 개념 정리
Dijkstra 란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 단, 가중치에 음수가 있으면 사용할 수 없음 시간복잡도 : O(E logN) (N:노드의 수, E: 간선의 수) 다음과 같은 그래프가 있다고 가정 1번 노드에서 2, 3, 4, 5번 노드까지의 최단거리를 모두 구해야 함 dist[1~5] = [0, ∞, ∞, ∞, ∞]로 초기화 후 시작 1번 노드에서 갈 수 있는 노드 = 2, 3, 4 1(시작노드) -> 2로 갈 때 드는 비용 ( = dist[1] + (1->2) )과 지금까지 2로가는 최소 비용 (=dist[2])를 비교해서 지금까지 2로가는 최소비용이 더 크다면 dist[2] = dist[1] + (1->2)로 갱신 이 방식으로 1번노드에서 갈 수 있는 노드들에 대한 ..
[JAVA] DFS, BFS
2022. 5. 31. 15:57
JAVA/알고리즘 개념 정리
DFS, BFS 란? DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함 BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함 다음과 같은 그래프를 탐색한다고 가정 DFS 수행 과정 1번 노드에서 시작 2, 5번 노드로 갈 수 있음 숫자가 더 작은 2번 노드로 감 (전략은 마음대로 설정) 3, 4번 노드로 갈 수 있음 3번 노드로 감 3번 노드에서는 갈 수 있는 곳이 없음 2번노드로 돌아감 4번 노드로 감 4번 노드에서 갈 수 있는 곳이 없음 2번 노드로 돌아감 2번 노드에서도 더 이상 갈 수 있는 곳이 없음 1번 노드로 감 .... 이런 식으로 탐색을 진행 결과 : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 BFS ..
[JAVA] 다양한 정렬 알고리즘 개념 및 시간 복잡도 비교
2022. 5. 28. 20:18
JAVA/알고리즘 개념 정리
정렬 알고리즘 별 시간 복잡도 정렬 알고리즘 시간 복잡도 Bubble Sort (버블 정렬) O(n^2) Selection Sort (선택 정렬) O(n^2) Insertion Sort (삽입 정렬) O(n^2) Quick Sort (퀵 정렬) 평균 : O(nlogn) / 최악 : O(n^2) Merge Sort (병합 정렬) O(nlogn) Radix Sort (기수 정렬) O(kn) / k : 최대 데이터의 자릿수 Arrays.sort() 평균 : O(nlogn) / 최악 : O(n^2) Collections.sort() O(nlogn) 위 표를 보면 병합정렬이 퀵정렬보다 빠르다고 생각할 수 있음 최악의 상황에선 퀵정렬이 느리지만, 보통은 퀵정렬이 더 빠르고, 병합 정렬은 메모리를 더 많이 차지함 이..
[JAVA] 우선순위 큐 (Priority Queue), 정렬 전략 설정법
2022. 5. 28. 18:17
JAVA/기본 문법
우선순위 큐 란? 큐 자료구조는 선입선출(FIFO) 방식이지만 우선순위 큐는 들어간 순서와는 상관없이 높은 우선순위를 가진 원소가 먼저나온다는 특징을 가짐 숫자가 작을수록 먼저 나오는 큐를 최소힙 (Min Heap) 이라 하고, 숫자가 클 수록 먼저 나오는 큐를 최대힙 (Max Heap)이라 함 우선순위 큐 시간복잡도 삽입, 삭제 : O(log n) 우선순위 큐 선언 방법 // 낮은 수가 우선순위를 가짐 PriorityQueue pq = new PriorityQueue(); // 높은 수가 우선순위를 가짐 PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); // 사전 순으로 더 빨리오는 문자열이 우선순위를 가짐 PriorityQueue p..