서로소 집합(Disjoint Set)서로소 집합(Disjoint Set)이란?서로 공통된 원소를 갖고 있지 않은 두 개 이상의 집합즉, 교집합이 없는 집합들을 관리하는 자료구조이다. 서로소 집합 자료구조는 서로 다른 원소들이 같은 집합에 속해있는지를 판단하기 위해 사용하는 자료구조이다.서로소 집합엔 MakeSet, Find, Union 세 가지 연산이 있다.MakeSet새로운 집합(parent 배열)을 생성하는 연산 처음 집합을 생성할 때 각 노드는 부모 노드가 없기 때문에 자기 자신을 가르키는 parent 배열을 생성한다.int n = 10; // 노드의 개수int[] parent = new int[n];// 처음 parent 배열을 초기화 할 때는 각 노드가 자기 자신을 가르키도록 설정한다.for (..

그래프(Graph)란?그래프는 여러 개의 노드(node)(정점(vertex))와 이를 연결하는 간선(Edge)로 이루어진 비선형 자료구조이다.비선형 구조: 데이터를 일렬으로 구성하지 않고, 자료 순서나 관계가 복잡한 자료구조그래프 용어용어정점(Vertice)노드(node)라고도 하는 데이터가 저장되는 그래프의 기본 원소간선(Edge)정점을 연결하는 선인접 정점(Adjacent Vertex)특정 정점에 간선으로 직접 연결되어 있는 정점단순 경로(Simple-path)시작 정점에서 끝 정점까지 가는 경로 중 어떤 정점도 두 번 이상 방문하지 않는 경로차수(Degree) - 무방향 그래프에서 하나의 정점에 인접한 정점의 수(위 사진에서 3의 정점은 3(1, 4, 5와 연결됨))진출 차수(Out-degree)..

우선순위 큐(Priority Queue)란?큐(Queue)는 FIFO(First In First Out) 구조로 먼저 들어온 데이터가 먼저 나가는 선형 자료구조이다.반면 우선순위 큐(Priority Queue)는 들어온 순서에 상관 없이 우선순위가 높은 데이터부터 나가는 구조이다.우선순위 큐 표현 방법3가지 방법이 있고 이중 JAVA의 PriorityQueue는 힙을 이용한 우선순위 큐이다.배열을 이용한 우선순위 큐연결리스트를 이용한 우선순위 큐힙을 이용한 우선순위 큐시간복잡도 비교표현방법삽입삭제순서 없는 배열O(1)O(n)순서 없는 연결 리스트O(1)O(n)정렬된 배열O(n)O(1)정렬된 연결 리스트O(n)O(1)힙O(log₂n)O(log₂n)힙을 이용한 우선순위 큐가 삽입, 삭제 연산에서 모두 O(l..

해시(Hashing)란?임의의 값을 해시 알고리즘을 사용하는 해시 함수를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 해싱을 사용하여 데이터를 저장하는 자료 구조를 해시 테이블이라고 하며 이진 탐색 트리나 배열에 비해 훨씬 빠른 속도로 탐색, 삽입, 삭제를 할 수 있다.해시 함수(Hash Function) / 해시 테이블(Hash Table)특정 키 값을 해시 함수를 통해 해시 값으로 산출한다.산출된 해시 값을 인덱스로 하여 해당 데이터를 해시 테이블에 저장한다.위 그림은 해시 함수를 통해 키 값이 해시 값으로 변환되는 과정이다. "바나나"를 해싱하여 해시 값 04로 변환한다. 해시 값인 04가 해시 테이블의 인덱스 값이 되고 인덱스가 가리키는 곳 HashTable[4]에 바나나의 가격인 18..