Segment Tree 구간 트리(Segment Tree)는 저장된 자료의 특정 구간 질의를 빠르게 대답하기 위해 저장된 자료를 전처리한 트리를 말한다. 흔히 구간 트리는 일차원 배열의 특정 구간 질의를 빠르게 대답하는데 사용된다. 예를 들어 [1, 7, 5, 3, 2] 라는 일차원 배열이 있을 때 [1, 2] 구간의 최소치를 찾는 연산을 해야 한다. 이를 연산하는 간단한 방법은 구간의 시작부터 끝까지 순회하면서 최소치를 찾으면 되며 시간 복잡도는 O(N)이 된다. 반면 구간 트리를 한 번 만들어두면 위 연산을 O(log N)으로 할 수 있다. 구간 트리의 핵심 아이디어는 배열 구간에 대한 이진 트리를 만드는 것이다. 구간 트리의 노드는 구간을 표현한다. 루트 노드는 항상 배열의 전체 구간 [0, n-1..
Binary Search Tree (BST) 데이터 탐색 알고리즘으로 이진 탐색 알고리즘이 있다. 탐색 범위를 반으로 줄이면서 탐색하는 알고리즘이다. 정렬된 배열에서 이진 탐색 알고리즘을 적용해 O(log N)의 시간복잡도로 탐색할 수 있지만 배열의 원소를 추가, 삭제하는데 O(N)의 시간복잡도가 든다는 단점이 있다. 이를 극복하기 위해 BST를 사용한다. 균형 잡힌 BST(BBST)라면 탐색, 삽입, 삭제의 시간 복잡도를 O(log N)으로 만들 수 있다. BST는 이진 트리에 속하며 이진 탐색을 목적으로 하는 트리다. BST의 모든 노드는 아래의 규칙을 갖는다. 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 ..
트리 트리는 계층 구조를 표현하는 자료구조이다. 트리는 다양한 목적으로 사용되어 다양한 종류의 트리들이 등장했다. 현실 세계 계층 구조 표현 이진 검색 트리 힙 세그먼트 트리 유니온-파인드 트라이 등등 트리 용어 node(노드) : 트리 구성 요소 edge(간선) : 노드와 노드를 연결한 선 parent : 두 노드가 간선으로 연결되었을 때 상위 노드 child : 두 노드가 간선으로 연결되었을 때 하위 노드 sibling : 같은 부모를 가지는 자식 노드들 ancestor : 부모 노드와 그 부모 노드의 상위 노드들 descendant : 자식 노드와 그 자식 노드의 하위 노드들 root : 부모가 없는 최상위 노드 leaf : 자식이 없는 노드 Internal : 리프 노드가 아닌 노드 depth :..
LinkedList LinkedList는 리스트의 한 종류이다. 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만 노드가 다음 노드로 갈 수 있는 포인터를 가짐으로써 노드들이 논리적으로 연속되어 있다. 연결 리스트에서 하나의 원소를 노드라고 한다. 노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드는 리스트에 저장될 원소의 값을 저장하며 링크 필드는 다음 노드의 참조값을 저장한다. 연결리스트의 가장 큰 장점은 원소의 삽입, 삭제의 시간복잡도가 O(1)이다. 때문에 원소의 삽입, 삭제가 빈번하면 연결 리스트 사용을 고려할만하다. 단점은 특정 위치의 원소를 찾아가는 시간 복잡도가 O(N)이다. 배열(배열 기반 리스트)와 달리 랜덤 엑세스가 안되기 때문이다. 연결 리스트의 종류 연결 리스트는 총 세..
List 리스트는 데이터를 일렬로 저장하는 선형 자료구조이다. 리스트는 배열 기반 리스트(동적 배열)와 연결 리스트로 나뉜다. 배열 기반 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있다. 연결 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만, 노드 안에는 다음 노드로 갈 수 있는 포인터가 있다. 또한 리스트로 비선형 자료구조를 표현할 수 있다. 연결 리스트로 트리 구현, 배열로 그래프 구현, 배열로 이진 트리 구현 등이 그 예시이다. 배열 기반 리스트 배열의 가장 큰 문제점은 한번 할당받은 후 배열의 크기가 변하지 않는다는 점이다. 이를 극복하기 위해 배열 기반 리스트를 사용한다. 배열 기반 리스트는 배열에 노드를 저장하며 배열 크기를 조절하는 resize 연산을 추가했다..
Disjoint Set 분리 집합 또는 서로소 집합은 각각의 집합이 공통 원소를 가지고 있지 않은 집합이다. 즉 전체집합 U에 대해, U의 분리 집합 A ,B는 다음 조건을 만족한다. A, B는 U의 부분 집합이다. A, B는 공통 원소를 가지지 않는다. (A ∩ B = Ø) A, B의 합집합은 전체 집합 U이다. (A ∪ B = U) 위 조건은 분리 집합이 개수가 3개 이상일때도 만족한다. Union-Find Union-Find는 분리 집합을 구현하고 조작하는 자료구조이다. 분리 집합을 합치는 연산인 union 연산과 임의의 원소가 어떤 집합에 속하는지 찾는 find 연산을 제공한다해서 union-find 자료구조라 불린다. Union-Find를 구현하기 위해선 아래 3가지 연산을 구현해야한다. 초기화..
그래프 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하는 자료 구조, 즉 정점(vertext)의 집합 V와 간선(edge)의 집합 E로 구성된 자료 구조이다. 도로망, 네트워크 망 부터 먹이 사슬, 사람들 간의 짝사랑 관계, 하루 동안의 도시 간 인구 이동 관계 등을 그래프로 표현할 수 있다. 그래프의 종류 그래프가 가지는 특징과 형태에 따라 여러 종류로 나눌 수 있다. 방향 그래프 (directed graph) : 각 간선이 방향을 가지는 그래프, 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다. 무향 그래프 (undirected graph) : 각 간선이 방향을 가지고 있지 않은 그래프 가중치 그래프 (weighted graph) : 각 ..
