Union-Find공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들을 저장, 조작하는 자료구조 Java code1234567891011121314151617181920212223242526272829303132333435public class UnionFind { int[] root; int[] rank; public UnionFind(int N){ root = new int[N]; rank = new int[N]; for(int i=0; i rank[b]){ //항상 높이가 작은걸 큰것에 붙임 int temp = a; a = b; b = temp; } root[a] = b; if(rank[a] == rank[b]) rank[b]++; return b; }}Colored by Color Scr..
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
BufferReader기존의 Scanner를 이용한 입력과 비교하지 못 할 만큼 빠름 사용 방법/** Class for buffered reading int and double values */static class Reader { static BufferedReader reader; static StringTokenizer tokenizer; /** call this method to initialize reader for InputStream */ static void init(InputStream input) { reader = new BufferedReader( new InputStreamReader(input) ); tokenizer = new StringTokenizer(""); } /** g..
단일 스레드자바의 메인 스레드만을 이용함 멀티 스레드메인 스레드 이외의 추가 스레드를 생성 및 사용 사용 방법1>Runnable 인터페이스class Task implements Runnable { public void run() { // Code }}Thread thread = new Thread(new Task());thread.start(); //Thread 시작 2>Thread 상속public void workingThread extends Thread { @Override public void run() { // Code }}Thread thread = new workingThread();thread.start(); 3>익명 구현 객체 사용Thread thread = new Thread(new R..
Comparable기본 정렬기준을 구현하는데 사용. java.lang패키지public interface Comparable{ public int compareTo(Object o);} Comparator기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용 java.util패키지public interface Comparator{ int compare(Object o1, Object o2); boolean equals(Object obj);} 참고https://brunch.co.kr/@kd4/7
Binary Search Tree-왼쪽 자식은 자기보다 작은 값들이고 오른쪽 자식은 자기보다 큰값들인 이진 트리-이진 탐색을 하는데 최적화 Java 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102public class BinarySearchTree { BTNode root; public BinarySearchTree(){ root = null; } //자기보다 작으면 왼쪽, 크면 오른쪽으로 이동 /..
Queue선입선출(First in First out) 즉 먼저 들어간 데이터가 먼저 나오는 자료구조 Java 코드12345678910111213141516171819202122232425262728public class Queue{ Node head; Node tail; public Queue(){ head = null; tail = null; } public void enQueue(int data){ Node item = new Node(data); if(head == null){ head = item; tail = head; } else{ tail.next = item; tail = tail.next; } } public int deQueue(){ if(head == null) return -1; N..
Stack후입선출(Last in First out) 즉 마지막에 들어간게 먼저 나오는 자료구조 Java 코드1234567891011121314151617181920public class Stack{ Node top; public Stack(){ top = null; } public void push(int data){ Node item = new Node(data); item.next = top; top = item; } public int pop(){ if(top == null) return -1; Node item = top; top = top.next; return item.data; }}cs