전체 글
-
다익스트라 알고리즘(Dijkstra Algorithm)Computer Science/Algorithm 2021. 9. 25. 18:38
다익스트라 알고리즘이란? - 그래프 상의 한 노드에서 다른 모든 노드까지의 최단 거리를 구할 때 유용하게 사용되는 알고리즘이다. - 노드와 노드 사이의 간선의 가중치가 0 이상의 정수일 때만 사용이 가능하다. 다익스트라 알고리즘의 동작 과정 1단계 노드 1 2 3 4 5 6 거리 0 2 5 1 INF INF - 출발 노드인 1을 기준으로 인접한 노드인 2, 3, 4 노드에 대한 최단 거리 테이블을 만들어 준다. - 인접하지 않은 노드인 경우 무한으로 표시한다. 2단계 노드 1 2 3 4 5 6 거리 0 2 1+3=4 1 1+1=2 INF - 노드 1과 인접한 노드들 중 최단 거리가 가장 짧은 노드인 4번으로 진행한다. - 노드 4와 인접한 노드는 3, 5 노드이고, 이 노드까지의 최단 거리와 기존의 최단..
-
위상 정렬(Topological Sorting)Computer Science/Algorithm 2021. 9. 25. 18:23
위상 정렬이란? ㆍ 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. ㆍ 큐, 스택 자료구조를 이용하여 구현이 가능하다. 위상 정렬의 처리 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; int indegree; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.indegree = 0; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; for (int i = 0; i < size; i++) nodes[i] = new Node..
-
크루스칼 알고리즘(Kruskal Algorithm)Computer Science/Algorithm 2021. 9. 25. 18:16
크루스칼 알고리즘이란? ㆍ 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘이다. 크루스칼 알고리즘의 동작 과정 ㆍ 위 그래프는 7개의 노드와 11개의 엣지로 이루어져 있다. 알고리즘의 동작 과정 1. 그래프를 구성하고 있는 엣지를 비용을 기준으로 오름차순 정렬을 한다. 2. 비용이 작은 엣지부터 정렬된 순서대로 그래프를 구성한다. 3. 그래프를 구성할 때 사이클을 형성하는지 확인한다. 4. 사이클을 형성하는 경우 해당 그래프에 엣지를 포함시키지 않는다. 구현 방법 엣지의 구성 class Edge implements Comparable { int node01; int node02; int cost; Edge(int node01, int node02, int cost) { this.node0..
-
BFS(너비 우선 탐색)Computer Science/Algorithm 2021. 9. 25. 11:02
BFS란? ㆍ DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다. ㆍ 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. ㆍ 스택 자료구조를 통해 구현할 수 있다. BFS의 그래프 순회 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; boolean marked; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.marked = false; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; fo..
-
DFS(깊이 우선 탐색)Computer Science/Algorithm 2021. 9. 25. 10:57
DFS란? ㆍ DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다. ㆍ 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. ㆍ 스택 자료구조를 통해 구현할 수 있다. DFS의 그래프 순회 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; boolean marked; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.marked = false; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; fo..
-
다양한 정렬 알고리즘Computer Science/Algorithm 2021. 9. 25. 10:47
정렬 알고리즘의 종류 ㆍ 선택 정렬 ㆍ 삽입 정렬 ㆍ 쉘 정렬 ㆍ 계수 정렬 ㆍ 기수 정렬 ㆍ 병합 정렬 (Top-Down) ㆍ 병합 정렬 (Bottom-Up) 구현 방법 추상 클래스 public abstract class AbstractSort { public static void sort(Comparable[] a) { }; /** compare the size of two elements */ protected static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /** change two elements */ protected static void exch(Comparable[] a, int i, int j) ..