Java code12345678910111213141516171819202122232425262728293031323334import java.util.*; public class KMP { int[] getPi(String p){ int n = p.length(); int j=0; int[] pi = new int[n]; for(int i=1; i 0 && p.charAt(i) != p.charAt(j)) j = pi[j-1]; if(p.charAt(i) == p.charAt(j)) pi[i] = ++j; } return pi; } ArrayList kmp(String s, String p){ ArrayList ret = new ArrayList(); int[] pi = getPi(p); int n =..
Ford-Fulkerson그래프에서 최대 유량을 찾아내는 알고리즘*시간복잡도: O(E*f) Java code123456789101112131415161718192021222324252627282930313233343536public class FordFulkerson { int vertexNum; int[][] capacity; int[][] flow; public int networkFlow(int source, int sink){ int totalFlow = 0; while(true){ //최대 maxflow번 반복함 int[] parent = new int[vertexNum]; Arrays.fill(parent, -1); Queue q = new LinkedList(); parent[source] ..
MST방향이 없는 그래프에서 모든 정점을 연결하며 모든 간선의 합이 최소인 트리 Prim다익스트라 알고리즘과 아주 유사함출발 정점을 시작으로 이웃 정점들의 최소 간선을 갱신하면서 답을 찾아감*시간복잡도: O(V^2 + E)Java code1234567891011121314151617181920212223242526272829303132333435363738394041424344public class Prim { int vertexNum; HashMap[] graph; int prim(){ int[] minWeight = new int[vertexNum]; int[] parent = new int[vertexNum]; HashSet Q = new HashSet(); Q.add(0); minWeight[0]..
Floyd다익스트라 알고리즘은 특정 지점으로 부터 모든 점 까지의 최소 경로를 찾음이를 vertex 갯수 만큼 반복하면 모든 vertex 사이간의 최소 경로를 찾을 수 있으나 복잡함floyd 알고리즘은 아주 간결한 코드로 이를 해결 할 수 있음또한 음수 가중치가 있을 때도 사용 가능(사이클이 없을 경우) 시간 복잡도O(V^3) Java code123456789101112131415public class Floyd { int vertexNum; double adj[][]; void floyd(){ for(int i=0; i
Bellman-Ford다익스트라 알고리즘 보다 느리지만 음수가 있을 때도 사용 가능또한 사이클 여부를 확인 할 수 있음 시간복잡도O(VE) Java code123456789101112131415161718192021222324252627public class BellmanFord { int vertexNum; int edgeNum; HashMap[] graph; //graph[출발지] = HashMap Double[] distance; public double bellmanFord(){ distance[0] = 0.0; for(int i=1; i
Heap sortHeap에다 입력 값들을 넣은 후 루트노드를 하나씩 빼면서 정렬하는 방식 시간 복잡도n*log2(n) 공간 복잡도n : 힙 사이즈=입력 배열 사이즈(Heap을 수정하면 O(1)로 가능) Java 코드12345678910111213141516171819202122public class HeapSort { Heap heap; //정렬에 사용할 힙 int[] arr; //입출력 할 배열 public HeapSort(int[] _inputArr){ heap = new Heap(); arr = _inputArr; } //입력 받은 배열을 힙에 넣은 후 //힙 루트노드를 다시 배열에 넣어서 정렬 public int[] heapSort(){ for(int num: arr) heap.insert(num..
참고https://www.toptal.com/developers/sorting-algorithms/
Merge sort전체를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하며 정렬하는 방식 시간복잡도n*log2(n) 공간복잡도(이 코드의 경우)n Java 코드12345678910111213141516171819202122232425262728293031323334353637383940414243public class MergeSort { int[] arr; //입력 받는 배열 int[] temp; //합칠때 사용 하는 임시 배열 //배열에 입력 받기 public MergeSort(int[] _arr){ arr = _arr; temp = new int[arr.length]; } //low~mid, mid+1~high 정렬 후 병합 public void mergeSort(int low, int high..
Quick sort특정값을 정해서 이 값보다 작으면 왼쪽 크면 오른쪽으로 정렬한 후 좌우로 재귀적으로 정렬해가는 방법 시간복잡도최악: n^2평균: n*log2(n) 재귀 호출 깊이log2(n) Java 코드1234567891011121314151617181920212223242526272829303132333435363738public class QuickSort { int[] arr; //숫자 배열 public QuickSort(int[] _arr){ arr = _arr; //배열 입력 } //sort 함수로 정렬 후 //low~mid, mid+1~high 각각 정렬하기 위해 재귀 호출 public void sortAndDivide(int low, int high){ if(low >= high) ret..