알고리즘/이론5 [Java] 위상정렬 위상 정렬은 특정 수강과목에서 선수과목이 있을 경우 어떤 순서로 들어야 하는지 순서를 쉽게 찾아낼 수 있는 알고리즘입니다. 이때, 위상 정렬을 위해서는 그래프는 방향이 있어야 하고 사이클이 없는 DAG(Directed Acyclic Graph) 여야만 합니다. 위상 정렬 방법(Queue 사용) 1. 진입 차수 즉, 특정 노드로 들어오는 간선의 개수를 알아내기 위해 in 배열의 크기를 정점의 개수만큼 만듭니다. 2. 특정 노드로 들어오는 간선이 있을 때마다 in 배열의 크기를 +1 해줍니다. ex) 예를 들어, 위 이미지와 같은 DAG가 있다면 진입 차수는 1 2 3 4 진입 차수 0 1 0 3 와 같이 됩니다. 3. 큐를 만들고 진입 차수가 0인 노드를 전부 큐에 삽입합니다. 4. 큐에 아무것도 남지 않.. 2021. 5. 11. [Java] Dijkstra 알고리즘 Dijkstra 알고리즘은 가중치와 방향이 있는 그래프에서 출발지에서 도착지까지의 최단거리를 구할 수 있는 알고리즘입니다. 이때, 주의할점은 음수인 가중치가 존재하면 안됩니다. MST를 구하는 Prim 알고리즘과 매우 비슷한 과정으로 진행됩니다. 때문에, Dijkstra 알고리즘을 학습하면 Prim 알고리즘을 학습하실때 큰 도움이 됩니다! [Java] Prim 알고리즘 Kruskal과 같이 MST를 찾는 알고리즘입니다. Prim을 잘 익혀두시면 최단거리를 구하는 Dijkstra 알고리즘을 학습하실때 큰 도움이 됩니다! [Java] Kruskal 알고리즘 MST를 찾는 알고리즘입니다. (설명을 잘 comgong-man.tistory.com (설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ).. 2021. 5. 10. [Java] Prim 알고리즘 Kruskal과 같이 MST를 찾는 알고리즘입니다. [Java] Kruskal 알고리즘 MST를 찾는 알고리즘입니다. (설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ) 1. 간선의 정보가 E개가 들어온다면 E개의 시작점, 도착점, 가중치를 저장할 수 있는 Edge 객체 배열을 만 comgong-man.tistory.com Prim을 잘 익혀두시면 최단거리를 구하는 Dijkstra 알고리즘을 학습하실 때 큰 도움이 됩니다! [Java] Dijkstra 알고리즘 Dijkstra 알고리즘은 가중치와 방향이 있는 그래프에서 출발지에서 도착지까지의 최단거리를 구할 수 있는 알고리즘입니다. 이때, 주의할점은 음수인 가중치가 존재하면 안됩니다. MST를 구하는 Pr comgong-man.tistor.. 2021. 5. 10. [Java] Kruskal 알고리즘 MST를 찾는 알고리즘입니다. (설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ) 1. 간선의 정보가 E개가 들어온다면 E개의 시작점, 도착점, 가중치를 저장할 수 있는 Edge 객체 배열을 만들고 저장하였습니다. 다음으로, 크루스칼 알고리즘은 그리디 알고리즘을 적용하고 있기 때문에 가중치를 기준으로 Edge 배열을 정렬하여 가장 낮은 가중치를 갖고 있는 간선의 정보를 우선적으로 처리하게 했습니다. 2. make() 함수를 이용해서 자기 자신이 부모가 되게 parents 배열을 초기화하는 작업을 하였습니다. 3. Edge 배열에 든 Edge들을 하나씩 처리하면서 union()을 처리하게 했습니다. union()은 최상위 부모 정점을 찾아주는 findSet을 통해 aRoot와 bRoot를 .. 2021. 4. 28. [Java] KMP 알고리즘 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class KMP { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] text = br.readLine().toCharArray(); char[] pattern = br.readLine().toCharArray(); int tLength = text.length; int pLength = pattern.length; int[] .. 2021. 4. 28. 이전 1 다음
