[ALGOS STUDY] 2023-SUMMER DAY5 트리, 분리집합, 최소 스패닝 트리

트리

- 개념

• 루트와 루트의 서브 트리로 구성된 계층형 자료구조
• 최소 하나 이상의 노드가 있어야 함.
• 이진트리 : 각 노드가 최대 2개의 자식 노드를 갖는 트리

 

- 트리의 표현 : 배열이나 연결 리스트 이용

 

- 트리의 탐색

• 중위 탐색 (inorder) : 왼쪽 서브트리, 루트 노드, 오른쪽 서브트리 순으로 탐색
• 전위 탐색 (preorder) : 루트 노드, 왼쪽 서브트리, 오른쪽 서브트리 순으로 탐색
• 후위 탐색 (postorder) : 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순으로 탐

- 문제 풀이 예시 : 백준 1991 트리 순회 (https://www.acmicpc.net/problem/1991)

#include <iostream>
using namespace std;

pair<char, char> node[28];
int n;

void preorder(char c)
{
	if (c == '.') return;
	cout << c;
	preorder(node[c - 'A'].first);
	preorder(node[c - 'A'].second);
}

void inorder(char c)
{
	if (c == '.') return;
	inorder(node[c - 'A'].first);
	cout << c;
	inorder(node[c - 'A'].second);
}

void postorder(char c)
{
	if (c == '.') return;
	postorder(node[c - 'A'].first);
	postorder(node[c - 'A'].second);
	cout << c;
}

int main()
{
	cin >> n;
	char p, l, r;
	for (int i = 0; i < n; i++)
	{
		cin >> p >> l >> r;
		node[p - 'A'].first = l;
		node[p - 'A'].second = r;
	}

	preorder('A');
	cout << "\n";
	inorder('A');
	cout << "\n";
	postorder('A');
	return 0;
}

 

분리집합

- 분리집합 : 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

 

- 연산

• union(x, y) : x, y가 속한 집합을 합침
• find(x) : x가 속한 집합의 대표값을 찾아 반환

- 서로소 집합 (Disjoint set)

• 공통원소가 없는 두 집합
• 서로소부분 집합들로 나눠진 원소들의 정보를 저장하고 조직하는 자료구조
• 같은 집합에 속하는 원소들을 트리 형태로 반환
• 각 트리의 루트노드가 트리의 대표값

- 경로압축 : find 연산을 실행할 때마다 해당 노드의 부모 노드를 항상 루트 노드로 만듦.

 

- 문제 풀이 예시 : 백준 1717 집합의 표현 (https://www.acmicpc.net/problem/1717)

#include <iostream>
using namespace std;

int parent[1000001];

int getParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}
void findParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) cout << "YES\n";
    else cout << "NO\n";
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;

    cin >> n >> m;
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 0; i < m; i++) {
        int o, a, b;
        cin >> o >> a >> b;
        if (!o) unionParent(a, b);
        else  findParent(a, b);
    }
    return 0;
}

 

최소 스패닝 트리

- 개념

• 신장 트리 
  • 사이클이 없는 연결그래프
  • 항상 트리의 형태를 나타내며, 유일하지 않다.
• 최소 신장 트리
  • 간선의 가중치 합이 최소가 되는 신장 트리
  • 가중치가 가장 작은 간선을 포함하는 MST가 반드시 존재 

- 최소 신장 트리 구성 방법

• Kruskal의 방법
  1. 네트워크와 간선 없이 정저으로만 이루어진 포리스트에서 시작
  2. 간선비용을 오름차순으로 정렬해 최소 비용 간선부터 검토
  3. 기존 트리에 사이클을 형성하는 간선은 제외, 그렇지 않은 경우에 추가
  4. n-1개의 간선이 포함되면 종료
• Prim의 방법 
  1. 주어진 그래프에서 모든 정점만을 포함
  2. 시작 정점에 인접한 정점 중 최소 비용 간선을 선택해 검토
  3. 사이클을 형성하지 않으면 추가, 그렇지 않으면 제외
  4.  n-1개의 간선이 포함되면 종료 (새로운 트리에서 최소 비용 간선을 선택해 3번 반복)
• Sollin의 방법
  1. 그래프의 간선을 제외하고 n개의 정점에서 시작
  2. 각 트리에서 최소 비용 간선을 각각 선택해 포함 여부를 검토
  3. 중복 선택된 간선은 1회만 선택, 사이클 생성 간선은 제외
  4.  n-1개의 간선이 포함되면 종료 (새로운 트리에서 최소 비용 간선을 선택해 3번 반복)

 

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 일시 자료는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다. 

 

<출처>

[Data Structure] 자료구조 / C++ / 트리 (velog.io)

Introduction to Binary Tree - Data Structure and Algorithm Tutorials - GeeksforGeeks

파이썬으로 배우는 자료구조 프로그래밍 (유석)

 

ALGOS 2023 여름방학 캠프의 경우 저는 주제 총정리 영상을 담당하였습니다. 5일동안의 주제를 간단히 정리하는 영상을 제작하였으며, 해당 글과 발표자료 제작 시 참고한 내용의 출처는 다음과 같습니다.

 

<출처>

https://velog.io/@keum0821/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC

https://velog.io/@mu1616/%EB%B6%84%EB%A6%AC%EC%A7%91%ED%95%A9Disjoint-set

https://4legs-study.tistory.com/94

https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC

파이썬으로 배우는 자료구조 프로그래밍 (유석종)