날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 2. 풀이 : Union-Find 3. 시간복잡도 : O(logN) 4. 설명 입력값으로 들어오는 사용자ID(String)를 숫자(Integer)로 변경하여 Union-Find를 사용한다. 첫번째 줄의 입력값 Fred(0)와 Barney(1)을 union하면 그림[1]과 같고, 두 사람의 친구 네트워크에는 2명이 존재한다. 두번째 줄의 입력값 Barney(1)와 Betty..

Algorithm/Union-Find 2021. 6. 6. 00:03

1. 문제 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 2. 풀이 : Union-Find 3. 시간복잡도 : O(logN) 4.설명 최초 각 원소는 자기 자신을 대표값으로 갖는 집합으로 그림[1]과 같이 표현된다. 2번 원소 집합을 1번 원소 집합의 대표값에 연결하여 집합을 합치면 그림[2]와 같이 표현된다. (2번 원소 집합의 대표값을 1로 변경) 그림[2]에서 1번 원소 집합의 대표값(1)과 ..

Algorithm/Union-Find 2021. 5. 29. 01:11