CS/알고리즘
-
알고리즘 - Shortest PathCS/알고리즘 2021. 2. 16. 22:50
Shortest Path 최단경로 간선 가중치가 있는 유향 그래프에서 두 정점 사이의 최단 경로를 찾는다. Dijkstra Algorithmn 첫 정점을 기준으로 연결되어있는 정점의 거리 정보를 min heap에 넣고 가장 작은 거리를 갖는 정점을 선택한다. (방향성이 있다는 것만 제외하면 MST의 prim알고리즘과 유사하다.) 시작 정점이 A일때, A -> B: 8이고, B -> E: 10이면 A -> E: 18로 갱신해준다. 하나의 정점에서 다른 모든 정점들의 최저 비용을 구한다. 모든 간선의 가중치는 음이 아니어야하고 재방문을 허용하지 않는다. 수행시간: O(ElogV) 구현 with JAVA (백준 1753 최단 경로) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..
-
알고리즘 - MSTCS/알고리즘 2021. 2. 15. 22:21
MST MST Minimum Spanning Trees. 최소 신장 트리. 조건: 싸이클이 없는 무향 연결 그래프. 연결 그래프란 모든 정점 간에 경로가 존재하는 그래프를 말한다. 간선의 합이 최소인 신장트리를 말한다. Prim Algorithmn 임의의 시작 노드를 골라 min heap에 insert한 후 노드와 연결된 노드를 min heap에 insert해준다. 거리가 작은 노드부터 꺼내며 꺼낼 때마다 연결된 노드를 찾아 min heap에 넣어주는 과정을 반복한다. min heap에 저장되는 정보는 현재 노드 정보와 이전 노드에서 현재 노드까지의 거리 정보이다. 수행시간: O(ElogV) 구현 with JAVA (백준 1197 최소 스패닝 트리) 1 2 3 4 5 6 7 8 9 10 11 12 13 ..
-
알고리즘 - 위상정렬CS/알고리즘 2021. 2. 14. 19:36
위상정렬 Topological Sorting 싸이클이 없는 유향 그래프의 순서를 위배하지 않도록 나열한 것이다. 모든 정점을 일렬로 나열하되 정점x 에서 정점y 로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치한다. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다. 위상정렬 알고리즘 진입 간선이 없는 정점을 하나 선택한다. 해당 정점의 진출간선과 해당 정점을 모두 제거한다. 구현 with JAVA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public String topologicalSort(ArrayList[] list, int[] indegree) { Queue q = new LinkedList(); for(int i = 0; i
-
알고리즘 - 정렬CS/알고리즘 2021. 2. 13. 21:48
정렬 Selection Sort 최소 원소를 찾아 맨 왼쪽 원소와 교환하고 맨 왼쪽 원소를 제외한다. 하나의 원소가 남을 때까지 반복한다. 장점: 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적어 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용할 수 있다.(역순 정렬일때 가장 효율적이다.) 단점: 이미 정렬된 상태에서 자료가 추가되면 재정렬할때 최악의 처리 속도를 보인다. 수행시간: O(n^2) 구현 with JAVA 1 2 3 4 5 6 7 8 9 public void selectionSort(int[] arr) { for(int i = 0; i
-
알고리즘 - DFS, BFSCS/알고리즘 2021. 2. 12. 22:23
DFS, BFS DFS, BFS 그래프의 탐색 방법이다. 시간복잡도는 노드, 엣지의 개수에 영향을 받으며 DFS, BFS 동일하다. 인접 리스트로 구현시 -> O(|v|+|e|) 인접 노드로 구현시 -> O(v^2) DFS - 깊이 우선 탐색 재귀적으로 구현한다. 모든 노드를 다 탐색해야 최단 거리를 알 수 있으므로 최대 길이, 최대값 등을 찾을때 적합하다. 시작 노드로 부터 한 방향으로 계속 탐색을 진행하다가 더 이상 갈 곳이 없을때 되돌아와서 다른 방향으로 다시 탐색한다. 트리의 순회에서 중순위 탐색한 결과와 같다. 구현 with 자바 1 2 3 4 5 6 7 8 9 static void dfs(int[][] node, boolean[] memo, int num) { memo[num] = true; ..