문제 풀이/백준 (BOJ)

[백준/BOJ] 4195번: 친구 네트워크 ( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/4195 풀이이 문제는 주어진 두 사람이 친구 관계를 맺었을 때, 이 두 명이 속한 친구 집합의 인원수를 출력하는 문제입니다. 여기서는 Union-Find 알고리즘을 사용해서 문제를 풀었습니다.Union-Find은 분리 집합들을 결합하고, 주어진 원소가 속한 집합을 찾아내는 방법에 관한 알고리즘입니다. Union-Find 알고리즘은 여기에 정리하였습니다. [C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘분리 집합( Disjoint Set )이란분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집합들을 말합니다. 예를 들면, SNS에서 A란 사람과 친구 관계를 가진..

2024. 7. 4.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1717번: 집합의 표현 ( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1717 풀이이 문제는 원소 a, b가 같은 집합에 포함되어 있는지, 아닌지를 출력하는 문제입니다. 얼핏 보면 굉장히 간단한 문제 아닌가 하는 생각이 들 수 있는데,완전히 복잡하지는 않지만, 그렇다고 직관적으로 접근하면 시간을 잡아먹을 수도 있는 문제입니다. 여기서는 Union-Find 알고리즘을 사용했습니다.이 알고리즘은 여기에서 볼 수 있습니다. [C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘분리 집합( Disjoint Set )이란분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집합들을 말합니다. 예를 들면, SNS에서 A란 사람과 친구 관계를 가진 사람..

2024. 7. 3.

알고리즘

[C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘

분리 집합( Disjoint Set )이란분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집합들을 말합니다. 예를 들면, SNS에서 A란 사람과 친구 관계를 가진 사람들 집합과, 아무런 관계가 없는 사람들 집합으로 나누면, 이 집합들이 분리 집합입니다. 이 집합들을 가지고 하고자 하는 것은, 두 원소를 선택했을 때, 이 두 원소가 같은 집합에 속하는지, 그렇지 않은지를 알고 싶은 것입니다. 이를 해결하는 가장 간단한 방법은 각 원소에, 그 원소가 속한 집합의 이름을 적어놓는 것입니다.  만약, 2와 5의 원소가 같은 집합 이름을 갖고 있다면, 두 원소는 같은 집합에 속해 있다는 것을 바로 알 수 있을 것입니다.이 경우엔, 2와 5는 같은 집합에 속해 있지 않습니다. 그런데, 분리 집합을 ..

2024. 7. 1.