Set

[알고리즘] 유니온-파인드 (Union-Find) (자바 Java)

목차 유니온 파인드 (Union-Find) 서로소 집합(Disjoint-sets) 서로 중복 포함된 원소가 없는 집합들 → 교집합이 없다 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라고 함 연산 Make-Set(x): 원소 x로만 구성된 집합을 만든다 Find-Set(x): 원소 x를 가진 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다 표현 방법 연결 리스트, 트리 1. 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표원소로 삼음 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 2. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모노드를 ..

[백준] 1764 - 듣보잡

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 듣도 못한 사람의 HashSet 하나와, 보도 못한 사람의 HashSet 하나를 선언하여 각각 값을 ..