상호배타적 집합(Disjoint Set)은 유니온 파인드(Union Find) 자료구조로도 불리며어떤 두 부분집합 사이에도 교집합은 없고 모든 부분집합의 합집합은 전체 집합인 자료를 표현합니다.이 자료구조는 아래의 2가지 함수를 지원합니다. 1. find(u) : 노드 u가 속해있는 집합의 루트를 반환한다.2. merge(u, v) : 노드 u가 속해있는 집합과 노드 v가 속해있는 집합을 합친다. find함수로 find(u)와 find(v)의 값이 같다면 u와 v는 같은 집합, 다르다면 다른 집합에 있는 정보를 얻을 수 있으며다른 집합에 있을 경우 merge함수를 이용하여 두 집합을 합칠 수 있습니다.추후 그래프파트의 최소 스패닝 트리에서 이 자료구조를 사용하기에 알아두면 좋은 자료구조입니다. 기본 문제..
LCA(Lowest Common Ancestor)는 최소 공통 조상이라고도 불리며트리에서 두 노드 u와 v를 모두 자손으로 갖는 노드 중 가장 아래에 있는 노드를 구하는 기법입니다.기본적으로 아래의 과정을 진행하여야 합니다. 1. u보다 v가 더 깊이(depth)가 더 깊을 경우 v를 부모노드로 올린다.2. 이제 u와 v의 깊이가 같아졌을 경우 u와 v를 같이 부모노드로 올린다.3. 2번 과정을 u와 v가 같은 노드를 가리킬 때까지 진행한다. 하나하나 부모노드로 올려 진행하였을 때 최악의 경우에는 O(N)의 시간복잡도로 LCA를 구하게 되는데앞서 배운 DP와 비트마스크 기법을 이용하여정점의 2^k번째 부모를 부분문제로 저장하여 O(lgN)만에 구할 수 있습니다.이는 트리 상에서 두 정점의 거리를 빠르게 ..
구간트리(Segment Tree)는 저장된 자료들을 적당히 전처리하여특정 구간에 대한 질의를 빠르게 대답할 수 있도록 하게 하는 기법입니다.보통 원소의 값 변경이 자주 일어나며 구간 원소의 합, 곱, 최댓값, 최솟값을 반복적으로 구해야 할 때 사용합니다.구간에 대한 질의를 답할 때의 시간복잡도는 O(lgN), 원소 하나의 값이 변경 되었을 때의 시간복잡도는 O(lgN)이며길이가 K인 구간의 원소의 값이 변경 되었을 경우의 시간복잡도는 O(KlgN)입니다.이를 O(lgN)만에 하게 하기 위하여 레이지 프로퍼게이션(Lazy Propagation)기법을 사용합니다.또한 앞서 배운 비트마스크 기법을 응용하여 짧고 간단하게 구간 합을 구할 수 있는 팬윅트리(Fenwick Tree)를 이용하여 구간 합을 응용하여 ..