Data Structure

그래프는 정점(vertex)와 간선(edge)로 이루어진 한정된 자료구조를 의미한다. 그래프는 인접 리스트와 인접 행렬로 구현할 수 있다. 방향 그래프 : 방향성이 있어 간선이 한방향으로만 이루어져 있다. 무방향 그래프 : 방향성이 없어 간선을 통해 양방향으로 이동할

그래프를 깊이를 우선시하여 탐색하는 알고리즘하나의 정점에서 시작하여 그 정점에서부터 가장 깊은 정점까지 탐색한다. 위의 그래프에서 0부터 시작한다고 하면 0 -> 2 -> 3 -> 4 -> 5 -> 1의 순서로 탐색한다.

그래프의 너비를 우선시하여 탐색하는 알고리즘하나의 정점에서 시작하여 그 정점에 연결된 간선들 모두를 탐색하고 나서 다음 정점을 탐색한다. 큐를 이용해서 발견된 정점들부터 차례로 탐색을 진행한다.

각 노드가 최대 두 개의 자식 노드를 가지는 트리이진 검색 트리의 특징왼쪽을 타고 가면 현재 값보다 작다.오른쪽을 타고 가면 현재 값보다 크다.N의 수가 엄청나게 많다면 벡터나 리스트로 이루어진 구조 O(N)보다 이진 탐색 트리가 훨씬 빠르다. 시간복잡도가 O(log

우선순위 큐 기존의 큐는 FIFO로 먼저 넣은 순서대로 데이터가 나왔지만 우선순위 큐는 각 데이터에 우선순위를 두어 우선순위 순서대로 데이터가 나온다. 우선순위 큐는 힙을 통해 구현할 수 있다. 코드

이진 탐색 트리 각 노드의 왼쪽 서브트리에는

(key, value)로 데이터를 저장한다. 해시 테이블은 각각의 키값에 해시 함수를 적용하여 고유한 인덱스를 생성하고 이 인덱스를 통해 값을 저장하거나 읽는다. 여기서 실제 저장되는 공간을 bucket이라 한다. 추가/탐색/삭제의 시간복잡도가 O(1)로 매우 빠르다

Disjoint Set