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..
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
Heap-최소값, 최대값을 구하는데 최적화된 자료구조-완전 이진 트리로 구현하며 루트노드가 최소 또는 최대임-배열과 연결리스트로 구현할 수 있음-연결리스트의 경우 오른쪽 끝 노드를 접근하기 힘듦-우선 순위 큐로 사용하기 적절함 Java 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071public class Heap { ArrayList tree; //배열을 이용한 트리 int size; //현재 트리 사이즈 public Heap(){ tree = new ArrayList(); tree.add(-1); //트리 시작..