문제https://www.acmicpc.net/problem/4195 사용 알고리즘Union-Find 풀이고려사항1. 친구 리스트에 존재 여부2. 친구 연결 후기1. 이 문제의 keypoint는 union-find를 딕셔너리를 통해 진행하는 것이다.보통은 숫자로 진행했지만, 이 문제의 경우 문자열로 받기 때문에 딕셔너리를 통해 진행했다. 2. 우선 친구 딕셔너리(parents)에 존재 여부를 확인 후 존재하지 않는다면root를 자신으로 친구 딕셔너리에 등록, size 딕셔너리에 1로 세팅한다. 3. 이후 기존 union-find 알고리즘을 진행한다.- 현재 분리 집합의 root를 find 함수를 통해 구해준 후- 서로 같은 집합이 아닐 경우 union을 통해 서로 분리 집합을 합쳐준다.4. 이때 실시간으..

문제https://www.acmicpc.net/problem/1043 사용 알고리즘Union-Find 풀이고려사항1. 해당 파티에 진실을 아는 사람이 존재하는지- 기존 진실을 아는 사람- 기존 진실을 아는 사람이 참여한 파티에 참여한 사람들 후기1. 이 문제의 keypoint는 리스트 형태를 Union-Find 진행하는 것이다.이런 형태는 기준이 있으면 좋겠다고 판단했다.때문에 기준(root)을 진실을 알고있는 가장 첫번째 사람으로 정하고 시작했다. 2. 진실을 알고 있는 사람이 0명일 경우 모든 파티에서 거짓말을 할 수 있다.하지만, 1명 이상일 경우 Union-Find를 시작한다.3. 우선 진실을 알고 있는 사람들을 하나의 집합으로 묶는다.이때 위의 기준을 정한대로 가장 첫번째 사람을 기준으로 나머지..

문제https://www.acmicpc.net/problem/24542 사용 알고리즘Union-Find 풀이고려사항1. 분리 집합 만들기- 중간에 root가 변경 될 수 있기 때문에 다 만들고 최종 갱신 필요2. 집합 별 인원 수 확인 후기1. 이 문제는 Union-Find의 가장 기초 문제로 생각된다.2. 부모(root) 리스트를 만들어주고 배열 합칠 때 성능 향상을 위한 size 리스트를 만들어준다.3. 이후 M개의 숫자 쌍을 입력받으면- Find : 부모를 확인하여 같은 집합인지 확인 후- Union : 같은 집합이 아닐 경우 서로 집합을 합치며 부모를 갱신한다.- 이때 작은 집합을 큰 집합에 합침으로  집합 간의 균형을 맞추고 트리의 높이를 최소화하여 성능을 향상시킨다. 4. 이후 경우의 수는 해..

알고리즘 개념유니온 파인드(Union-Find) 알고리즘은 분리 집합을 관리하는 알고리즘으로그래프 형태의 자료들의 연결 정보를 알고 싶을 때 사용된다.이 알고리즘의 핵심 목표는 합치기(Union)와 찾기(Find) 작업을 효율적으로 수행하는 것이다.주로 그래프에서 연결된 컴포넌트 관리 나 사이클 검출에 활용된다.    - 집합 소속 여부 판단 & 사이클 검출 : 임의의 두 노드의 연결 여부(집합 소속 여부) 확인        - 단, 무방향 그래프에서만 적용 가    - 경로 압축 : 그래프 내 노드 간의 경로 최적화  위의 경우 3과 5가 같은 그룹인지 알려면왼쪽의 경우 자신의 부모만 기록되어 있으므로 연결여부 확인이 따로 필요하다.이때 재귀 호출을 통해 루트 노드를 찾을 때 탐색 시간이 소요된다.un..