[중급 알고리즘] Union-Find, Heap, BST

Union-Find

- 처음에는 parent[i] = i로 초기화한다.

- find로 조상의 루트로 갱신함과 동시에 리턴한다. 이를 통해 트리의 레벨을 최소화해 시간복잡도를 낮춘다. → 경로 압축

- 그냥 타고타고 올라가서 조상의 번호를 리턴하면 최대 시간복잡도는 $O(N)$이가 되기 때문이다.

- 트리의 랭크는 높이와 같은 의미를 갖지만 경로 압축을 사용하면 높이와 다른 값을 가질 수도 있다. 따라서 높이 대신 랭크라는 표현을 사용한다.

- 랭크가 작은 것을 랭크가 높은 것의 자식으로 만든다.

 

💚 2606 바이러스

- 컴퓨터가 연결된 상태가 주어진다.

- 1번 컴퓨터가 웜 바이러스에 걸렸을 때 웜바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제

 

DFS를 통해 모든 컴퓨터 연결 상태를 탐색할 수 있다. 하지만 유니온 파인드로도 풀 수 있다.

#include <iostream>
using namespace std;
int parent[101];

int Find(int x) {
    if(x == parent[x]) {
        return x;
    }
    return parent[x] = Find(parent[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    
    if(x != y) {
        parent[y] = x;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        parent[i] = i;
    }
    
    while(m--) {
        int x, y;
        cin >> x >> y;
        Union(x, y);
    }
    
    int ans = 0;
    for(int i = 2;i <= n;i++) {
        if(Find(1) == Find(i)) {
            ans += 1;
        }
    }
    
    cout << ans << '\n';
    return 0;
}

Heap

최소/최대값을 찾을 때나 제거할 때 유용하다.

 

힙은 이진 트리(자식의 수가 최대2)

최대 힙

- 부모 노드는 자식 노드에 들어있는 값보다 크다.

 

최대 힙 삽입

- 가장 마지막 위치에 새로운 수를 넣는다.

- 그 수와 부모를 계속해서 비교해가며 루트 < 자식이면 두 수를 바꿔준다.

 

최대 힙 제거

- 자식과 비교하면서 아래로 내려감

- 루트 > 자식이 만족하도록 두 수를 바꿔가며 내려간다.

 

최소 힙

- 부모 노드는 자식 노드에 들어있는 값보다 작다.

 

힙은 완전 이진 트리(Complete Binary Tree)이다. → 높이는 $logN$

C++에서는 priority_queue를 사용하면 된다.

최소 힙을 위해서는 priority_queue<int, vector<int>, greater<int>> q로 사용 가능하다.

 

💚 1655 가운데를 말해요

N개의 수가 주어졌을 때

각각의 수가 주어졌을 때마다 지금까지 나온 수의 중간값을 구하는 문제

N이 10만이라는 점을 고려해야한다.

 

매번 정렬하고 중간값 구하면 $O(N^2logN)$이라는 큰 시간복잡도가 생긴다.

링크드 리스트에 넣어도 매번 정렬할 필요가 없긴 하지만 여전히 시간복잡도는 $O(N^2)$으로 크다.

 

1) 왼쪽에 있는 수보다 오른쪽에 있는 수가 항상 크도록

2) N / 2씩 왼쪽, 오른쪽으로 나눈다. → 왼쪽은 최대힙으로, 오른쪽은 최소힙으로 구현

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int n;
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    // 최대 힙
    priority_queue<int> l;
    
    // 최소 힙
    priority_queue<int, vector<int>, greater<int>> r;
    
    while(n--) {
        int x;
        cin >> x;
        
        if(l.empty() || r.empty()) {
            l.push(x);
        }
        else {
            if(x <= l.top()) {
                l.push(x);
            }
            else {
                if(x <= l.top()) {
                    l.push(x);
                }
                else if(x >= r.top()) {
                    r.push(x);
                }
                else {
                    // 왼쪽보다도 크고 오른쪽보다도 작으면
                    l.push(x);
                }
            }
        }
        // 동일하거나 r이 l보다 1만큼 큰 게 아니라면
        while(!(l.size() == r.size() ||  l.size() == r.size() + 1)) {
            if(l.size() > r.size()) {
                r.push(l.top());
                l.pop();
            }
            else {
                l.push(r.top());
                r.pop();
            }
        }
        
        cout << l.top() << '\n';
    }
    
    return 0;
}

Binary Search Tree(BST, 이진 검색 트리)

- 이진 트리

- 현재 노드의 왼쪽 서브 트리에는 항상 현재 노드의 값보다 작은 값이 들어있고

- 현재 노드의 오른쪽 서브 트리에는 항상 현재 노드의 값보다 큰 값이 들어있다.

 

특징

- 트리를 inorder 순회를 하면 BST에 저장된 값을 오름차순으로 구할 수 있다.

 

삭제의 경우에는 총 3가지 경우의 수가 있다.

1. 자식이 0개인 경우 - 그냥 지운다.

2. 자식이 1개인 경우 - 노드를 지우고 자식을 이어 붙인다.

3. 자식이 2개인 경우- 지우려는 노드의 값을 Inorder successor 노드의 값으로 바꿔준 다음 inorder successor 노드를 지운다.

Node *inorder_successor(Node *node) {
	Node *p = node;
    while(p -> left != NULL) {
    	p = p -> left;
    }
    
    return p;
}

 

Node *remove(Node *node, int data) {
	if(node == NULL) {
    	return node;
    }
    
    if(data < node -> data) {
    	node -> left = remove(node -> left, data);
    } else if(data > node -> data) {
    	node -> right = remove(node -> right, data);
    } else {
    	if(node -> left == NULL) {
        	Node *temp = node -> right;
            node = NULL;
            return temp;
        } else if(node -> right == NULL){
        	Node *temp = node -> left;
            node = NULL;
            return temp;
        }
        // 2개인 경우
        Node *temp = inorder_successor(node -> right);
        node -> data = temp -> data;
        node -> right = remove(node -> right, temp -> data);
        
    }
    
    return node;
}

이진 검색트리의 경우 같은 데이터도 어떤 순서로 넣냐에 따라 트리의 형태가 달라지게 된다.

BST의 삽입/삭제/검색은 시간복잡도가 $O(h)$가 된다.

높이의 최대값은 N이 될 수 있기 때문에, $O(N)$이 될 수 있다.

따라서 균형이 맞춰진 트리를 사용하는 것이 좋다.(Balanced BST)

- AVL 트리

- Red-black Tree

- Splay Tree

- Treap

 

그런데 이건 구현하는 데 오래 걸린다.

그래서 구현하지 않고 있는 걸 쓰자!

💥C++의 경우에는 set, map을 사용한다. 정렬된 상태가 필요없다면 C++은 unordered_set, unordered_map을 사용한다.

✨Java의 경우에는 TreeSet, TreeMap을 사용하고, 정렬된 상태가 필요없으면 HashSet, HashMap을 이용할 수 있다.