Algorithm (13) 썸네일형 리스트형 세그먼트 트리(Segment Tree) 구간 합 계산, 배열의 원소 값 변경을 반복하는 상황에서 유용한 알고리즘으로 트리 자료구조를 사용한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 import java.io.*; im.. CCW(Counter Clock Wise) 알고리즘 3개의 점이 있을 때, 이 점을 이은 직선의 방향을 계산하는 알고리즘이다. 직선을 이은 방향은, 시계 방향, 직선 방향, 반시계 방향 중 하나로 결정된다. CCW 알고리즘을 이용하여 컨벡스 헐 알고리즘(Convex Hull Algorithm) 문제를 풀 수 있다. 커넥스 헐 알고리즘은 2차원 평면상에 여러 개의 점이 있을 때, 점 중 일부를 이용하여 모든 점을 포함하는 볼록 다각형을 만드는 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60.. 다익스트라 알고리즘 1. 인접 행렬 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public cla.. 프림 알고리즘 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class MST2_PrimTest { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syste.. 크루스칼 알고리즘 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class MST1_KruskalTest { static class Edge implements Comparable { int from, to, w.. Union & Find 알고리즘 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 static int N; static int[] parents; // 단위집합 생성 static void makeSet() { parents = new int[N]; // 자신의 부모노드를 자신의 값으로 세팅 for (int i = 0; i KMP(Knuth-Morris-Pratt) 알고리즘 패턴의 접두사와 접미사를 이용한 부분일치 테이블을 만들어서 매칭이 실패했을 때 패턴 포인터가 돌아갈 인덱스 번호를 계산한다. 해당 테이블을 이용하여 만든 KMP 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys.. 네트워크 플로우(Network Flow) 및 이분 매칭(Bipartite Matching) 네트워크 플로우 : 특정 지점에서 다른 지점으로 데이터가 얼마나 흐르고 있는가를 측정하는 알고리즘, 최대 유량이라고도 한다. 남아있는 모든 가능한 경로를 찾아내기 위해 음의 유량에 대해서도 계산한다. 참고 사이트 : https://blog.naver.com/ndb796/221237111220 27. 네트워크 플로우(Network Flow) 네트워크 플로우(Network Flow)는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를... blog.naver.com 이분 매칭 : 두 개의 집단에서 최대로 매칭시키는 방법을 구하는 방법이다. 깊이 우선 탐색(DFS)를 통해 다른 대체제가 있는지 확인하여 대체제가 있다면 바꾸는 방법으로 최대한 많이 매칭되도록 만들 수 있다. 참고 사이트 : h.. 이전 1 2 다음
