디스조인트-셋 자료구조는 유니온-파인드(Union-Find) 자료구조라고도 불리며 번역하면 서로소 집합(disjoint-set), 합집합-찾기(union-find) 자료구조이다. 이 자료구조는 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 트리 형태의 원소들로 구성된 포레스트(forest)이다. 각각의 원소는 숫자 ID로 표현되며 랭크(rank)와 부모에 대한 포인터를 가진다.또한 다음과 같은 연산을 지원한다. 자료구조가 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되며, 각각의 원소는 하나의 트리를 나타낸다. 이 자료구조는 다음과 같은 3가지 연산을 지원한다. make-set(x): x를 ID로 가지는 원소를 추가한다. find(x): 원소 x가 속한 트리..

해싱(hashing) - 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 작업. 해시 함수(hash function) - 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수. 모듈로 함수(modulo funcion) - 가장 간단한 해시 함수로 큰 범위의 정수를 인자로 받아 정해진 정수(n)로 나눈 나머지를 반환. 보통 % 기호로 표시. ex) 숫자 x를 입력하면 (x % n)가 연산의 결과로 반환. x를 배열에서 (x % n)의 위치에 삽입. 해시 값(hash value) - 위의 예시처럼 해시 함수에 의해 반환되는 값. 충돌(collision) - 설고 다른 데이터의 대해 같은 해시 값을 반환..

그래프의 종류 비가중 그래프(unweighted gragh) 그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장, 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있음. 이러한 그래프를 비가중 그래프(unweighted gragh)라고 함. 가중 그래프(weighted gragh) 에지에 가중치와 같이 더 많은 정보를 부여할 수도 있음. 예를 들어 노드와 노드 사이의 거리를 저장. 이러한 그래프를 가중 그래프(weighted gragh)라고 함. 무방향 그래프(undirectec gragh) 에지가 양방향인 그래프 방향 그래프(directec gragh) A에서 B 또는 B에서 A 한쪽으로만 이동 가능한 그래프 그래프의 노드가 N개 있을 때, 이 그래프를 N*N 크기의..

힙은 다음과 같은 시간 복잡도를 만족해야 한다. O(1): 최대 원소에 즉각적으로 접근 O(log N): 원소 삽입에 대한 시간 복잡도 O(log N): 최대 원소 삭제에 대한 시간 복잡도 또한 이를 위해서는 완전 이진 트리(complete binary tree)를 사용해야 한다. 완전 이진 트리란 각 노드가 위쪽과 왼쪽부터 순서대로 채워진 이진 트리를 말한다. 완전 이진 트리를 벡터에 저장한 경우, 만약 부모 노드가 i번째 배열 원소로 저장되어 있다면 자식노드는 2*i+1또는 2*i+2번째 인덱스로 접근하면 된다. 최대 원소에 즉각적으로 접근 가능한 힙을 최대 힙(max heap)이라 하며 이를 위해 부모 노드를 두 자식 노드보다 크도록 한다. 반대로 최소 원소에 즉각적으로 접근 가능한 힙을 최소 힙(..

이진 검색 트리는 일반적인 이진 트리와 같이 하나의 부모 노드에 최대 두개의 자식 노드를 가지는 트리이다. 일반적인 이진 트리와 다른 점은 왼쪽 자식 노드의 값은 부모 노드의 값보다 작거나 같고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 크거나 같다. 이러한 구조 덕분에 부모 노드보다 작은 원소는 항상 왼쪽에 위치하고, 큰 노드는 오른쪽에 위치한다. 따라서 원소를 검색 할 때 한 단계마다 이론적으로 검색 범위가 절반으로 줄게 된다. #include struct node{ int value; node* first; node* second; }; struct bst { node* root = nullptr; node* find(int input) { return find_impl(root, input);..

덱(deque)은 양방향 큐(double-ended queue)의 약자이다. push_front(), push_back()으로 이름처럼 양방향으로 확장이 가능하다. 또한 리스트와는 다르게 원소에 임의 접근이 가능하다. 중간에 원소를 삽입하면 가까운 끝 방향으로 원소들을 이동한다. (이는 최대 n/2 시간 복잡도를 가짐) #include #include int main() { std::deque dq; dq = { 1, 2, 3, 4,5 }; dq.push_front(0); // 0, 1, 2, 3, 4,5 dq.push_back(6); // 0, 1, 2, 3, 4, 5, 6 dq.insert(dq.begin() + 4, 9); // 0, 1, 2, 3, 9, 4, 5, 6 dq.pop_back(); /..