algorithm/이론 (5) 썸네일형 리스트형 서로소 집합(Disjoint Set, Union-Find) 서로소 집합 교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조 2가지 연산으로 이루어져 있습니다 Union 연산 - 어떤 두 원소 a, b 에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산 - a ∈ A, b ∈ B 에 대해서, union(a, b)는 A∪B 이다. Find 연산 - 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환 - a ∈ A 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환 서로소 집합 표현 배열(Array) 초기화 자기 자신의 부모를 자기 자신으로 초기화 i 1 2 3 4 5 U[i] 1 2 3 4 5 Union 연산 시간복잡도 : O(N) union(1, 3) unio.. 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(Minimum Spanning Tree) Spnning Tree란? 사진 첨부 정의 그래프 내의 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 말합니다. 특징 Spanning Tree = 신장 트리 n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필역적으로 트리형태가 됩니다. 이를 Spanning Tree라 고 합니다. 즉 Spaaning Tree는 그래프에 있는 n개의 정점을 (n-1)개의 간선으로 연결한 트리입니다. 신장 트리를 구하는 방법은 여러가지 입니다. (Kruskal, Prim 등..) DFS, BFS를 이용하여 그래프에서 Spanning Tree를 찾을 수도 있습니다. Minimum Spa.. (C++ STL) priority_queue priority_queue priority_queue 란? 힙 이론을 통해 우선순위 큐를 구현한 것 입니다. 자료형으로는 변수, 클래스 등 다양한 것들을 넣을 수 있습니다. 구현체는 기본적으로 vector를 사용하지만 deque를 사용하는 것도 가능합니다. 비교 연산자는 기본적으로 greater 오름차순, less 내림차순으로 정의하지만 비교연산자를 지정 해줄 수도 있습니다. queue 헤더 안에 존재합니다. priority_queue 함수 priority_queue.empty() 우선 순위 큐가 비었는지 확인하는 함수입니다. 비어있다면 True, 아니면 False를 반환합니다. priority_queue.size() 우선 순위 큐의.. (C++ STL) lower_bound, upper_bound lower_bound( begin(), end(), value); upper_bound( begin(), end(), value); lower_bound 란? begin()에서 end()의 범위 중에서 value값 이상이 나타나는 가장 작은 이터레이터를 반환하는 것입니다. value가 존재 하지 않는다면 value보다 큰 값중 가장 작은 값이 나타나는 이터레이터를 반환합니다. algorithm 헤더 안에 존재합니다. [코드] #include #include #include using namespace std; vector v; int main() { v.push_back(10); v.push_back(20); v.push_back(20); v.push_back(30); v.push_back(40); in.. 이분 탐색 이분 탐색 이분 탐색은 탐색 기법의 하나입니다. 탐색 범위를 두 부분으로 분할 하며 탐색한다 하여 이분 탐색이라고 이름 지어졌습니다. 이분 탐색의 핵심은 왼쪽 경계, 오른쪽 경계, 가운데를 어떻게 두느냐가 핵심입니다. 설명의 편의를 위해 left(=왼쪽 경계) , right(=오른쪽 경계) , mid(=가운데) 라고 하겠습니다. 탐색 방법은 아래와 같습니다. 1. left 값을 탐색 범위의 최소 인덱스로 지정합니다. 2. right 값을 탐색 범위의 최대 인덱스로 지정합니다. 3. mid의 값을 (left + right)/2로 지정합니다. 4. 찾으려는 값이 mid와 같은지 비교해줍니다. (같을 시 반복 종료) 5. 찾으려는 값이 mid보다 높다면 left = mid + 1로 초기화한 후 1 ~ 4의 s.. 이전 1 다음
