트리3 유니온파인드(Union-Find) Union-Find 에 대한 이해 - 공통 원소가 없는, "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. - 원소들이 어떠한 집합에 포함되어있을 때, 특정 원소가 포함되어있는 집합을 찾는 Find 연산을 지원한다. - 두 원소들이 속한 집합이 다를 때, 두 집합을 하나의 집합으로 합치는 Union 연산을 지원한다. 트리 형태로 표현되어있는 원소들간의 서로소 집합을 살펴보자. 위의 그림에서 원소들의 상호 배타적 집합은 총 4개이다. 각 원소들은 하나의 집합에 포함되어있고, 같은 집합에 포함되어있는 원소들은 같은 루트 노드를 공유한다. 예를 들어, 노드 2번과 노드 4번은 같은 집합에 포함되어 하나의 트리로 연결되어있고 루트 노드 1번을 공유한다. 노드 6번과 노.. 2022. 3. 3. 트리_그래프가 트리인지 확인하는 방법 그래프가 트리인지 확인하는 방법 - 트리는 노드 N개, 간선 N-1개를 가지면서 사이클이 없는 특징을 가진다. - 따라서 사이클이 있다면(탐색하는 과정에서 부모 이외의 이전에 방문했던 노드를 또 방문하게 된다면) 이는 트리가 아닌 그래프이다. #include #include #include using namespace std; int N, M; vector graph(15, vector(0)); vector visited(15, false); vector parent(15, 0); void setGraph() { scanf("%d %d", &N, &M); for (int i=0; i 2022. 2. 28. 이진트리순회_레벨순회(level)/전위순회(preorder)/중위순회(inorder)/후위순회(postorder) 트리 자료구조란 - 무방향이면서 사이클이 없는 연결그래프(즉, 트리는 그래프의 일종) - N개의 노드와 N-1개의 간선을 가짐 - 이진트리란, 트리 중 각 노드의 자식들이 2개 이하인 트리 - 이진트리를 순회하는 방식은 크게 레벨순회, 전위순회, 중위순회, 후위순회가 있음 레벨 순회(Level Order Traversal) - 트리의 루트부터 리프까지 계층적으로 순회하는 방식 - 가장 높은 층을 먼저 순회하며 큐로 구현 - 그래프에서의 bfs와 동일하게 구현하나, 사이클이 없기 때문에 이전에 방문한 노드를 별도로 체크해줄 필요가 없음(부모 노드만 기록) #include #include #include using namespace std; int N; vector graph(10, vector(0)); v.. 2022. 2. 27. 이전 1 다음