Algorithm/트리 (3) 썸네일형 리스트형 Segment Tree Segment Tree 세그먼트 트리(Segment Tree)란 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법에 관한 것입니다. 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조입니다. Ex) 3번 인덱스에서 8번 인덱스까지의 합을 구하는 방법은? 설계 방법 1. 배열을 이용해 무식하게 구하기 단순히 선형적으로 구하는 방법을 생각해봅시다. 인덱스 3부터 8까지 데이터의 범위를 하나씩 다 더하는 방법. 이러한 방식을 고려했을 때 앞에서 하나씩 더해가므로 데이터의 개수가 N이면 시간 복잡도는 $ O(N) $이 나옵니다. 따라서 구간 합을 N번 구해야한다면 시간복잡도는 $ O(N^2) $ 가 걸리고 이는 매우 불편한 복잡도이기 때문에 더 좋은 알고리즘이 필요합니다... Union-Find 알고리즘 Union Find 상호 배타적 집합, Disjoint-set. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. Find: 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union: 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 구현 초기화 // parent[i] : i 노드의 부모 노드, parent[i] = i 인 경우 i는 루트 노드 int parent[100]; for (int i = 0; i < 100; i++) parent[i] = i; find int find(int x){ if (x == parent[x]) return x; else return find[parent[x]]; } x .. MST (최소 신장 트리) MST (Minimum Spanning Trees) 선수지식: Disjoint-set, union-find 신장 트리란? : 그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리 문제 : Connected, Undirected, Weighted 그래프에서 가중치가 가장 적게 신장 트리를 만드는 문제 N개의 정점을 모두 포함하며 (Connected) Cycle이 없게 하려면 필요한 간선의 최소 갯수는 N-1개이다. 모델 설계, 의사코드 GENERIC-MST(G, w) { // G: graph, w: weight // 아무 간선도 없는 빈 트리 A를 하나 만든다. Tree A = null; // A에 safe한 간선을 한 개씩 추가함으로서 MST를 구성한다. while (A != a spanning tre.. 이전 1 다음