재원블로그 재원블로그

유니온 파인드는 집합간의 합집합을 나타낼 때 사용하는 자료구조이다. A[] = { 0, 1, 2 }, B[] = { 1, 2, 3 } 이라고 하고, B 배열이 A 배열로 합쳐진다고 가정하면 union 연산을 수행한 후에는 A[] = { 0, 1, 2, 3 } 이 되는 것이다. 유니온 파인드에서는 두 가지의 연산을 수행할 수 있는데, 한 집합의 대표를 리턴하는 find 와 두 집합을 합치는 union 연산이 있다. 초기 상태에는 한 원소가 하나의 집합이 되고, 그 원소가 그 집합의 대표가 된다. C++로 구현한 기본적인 유니온 파인드는 다음과 같다. vector parent; void init(vector p) { for (int i = 0; i < parent.size(); i++) { parent[i]..

세그먼트 트리는 구간 합을 구할 때 사용할 수 있다. 구간 합을 단순 반복문으로 linear하게 계산하면 O(N) 시간이 소요된다. 세그먼트 트리를 사용하면 O(log N) 시간에 구할 수 있어 더 빠르다. 위 사진은 0부터 5까지의 인덱스를 가진 배열, 즉 6개의 숫자가 들어있는 배열을 세그먼트 트리로 만든 것이다. 이진 탐색(Binary Search)의 메커니즘을 이용하여 트리를 만든다. 세그먼트 트리는 배열을 이용한 트리 구현 방법을 사용하는 것이 편하다. 이 때, 트리의 인덱스를 1부터 시작하게 만들면 index * 2 는 왼쪽 자식 노드를 가리키고, index * 2 + 1 은 오른쪽 자식 노드를 가리키게 되어 간편하다. 참고로 입력받을 배열도 인덱스를 1부터 시작하게 만드는 것이 구현하기 더 ..