본문 바로가기

분류 전체보기702

Disjoint Set & Union-Find 목차 Disjoint Set (서로소 집합, 분리 집합) - Time Complexity 구현 - MakeSet(n) - find(x) - union(x, y) 최적화 - Path Compression - Path Halving - Path Splitting - Union by Rank - Union by Size Disjoint Set (서로소 집합, 분리 집합) 원소들의 모임을 표현하는 자료구조로, 각각의 집합은 공통된 원소가 없다. 주로 서로 다른 원소들이 동일한 집합에 속하는지 여부를 판별하는데 사용된다. Time Complexity 경로 압축과 트리 깊이 제어를 하는 로직이 없다면 선형 구조와 같은 예시에서 하나의 작업이 최대 O(N)이 될 수 있다. 하지만, 최적화를 위한 로직을 적용했다면, .. 2023. 7. 2.
[백준 4375] 1 [Java] 풀이 입력받은 정수 n의 배수 중 1로만 이루어진 배수를 찾아 자릿수를 출력하면 되는 문제다. 간단하게 1부터 시작해서 n으로 나누어 떨어질때까지 숫자 뒤에 1씩 붙여주면 된다. 뒤에 숫자 1을 붙일 때 마다 자릿수를 한 개씩 증가시켜 주자. 소스코드 소스코드 보기 출처 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 2023. 6. 29.
[백준 4195] 친구 네트워크 [Java] 풀이 입력받은 이름에 대해 공통 부모를 갱신하며, 집합의 크기를 출력해야 되는 문제다. 공통 부모와, 집합의 크기를 저장할 parents, count 배열을 선언해주자. 문제에서 입력받은 친구 관계 F에 대해 입력받은 이름의 수는 최대 2F가 될 것이다. 때문에 위에서 선언한 배열의 크기 또한 2F로 할당받아야 한다. 모든 집합은 자기 자신에 대해 크기가 1이기에 count 배열은 1로 초기화 해주면 된다. 알다시피 parents 배열은 int형을 저장하는 배열이다. 때문에 입력받은 String형에 대해서는 Disjoint Set 구현이 불가능하다. 또한, parents 배열의 초깃값 설정을 할 때 자기 자신의 번호로 초기화를 해야하므로 String형 parent로 선언한다 하더라도 입력을 모두 받은 후.. 2023. 6. 29.
[백준 1976] 여행 가자 [Java] 풀이 이전에 풀었던 문제의 확장판이다. [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] 풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호 kyr-db.tistory.com 입력에 따라 union을 해주고, 최대 1000개 까지 주어지는 최대 200이하의 도시에 대해 여행계획이 가능한지, 즉 공통 부모가 다르지 않은지 확인하는 문제다. 입력받은 i번째 줄의 j번이 1이라면 i 에서 j는 연결된 도시이다. 마지막에 입력되는 여행 계획은 결국 도시들이 하나로 연결이 되어있는지 여부에 따라 여행 가능 여부가 결정된다. 즉, 공통.. 2023. 6. 29.
[백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] 풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호가 적혀있을 것이다. 반복문을 돌며, 부모 집합의 번호가 다르다면 두 집합은 연결되어 있지 않으므로 두 집합을 연결할 수 있도록 번호를 출력해주면 되는 문제다. 소스코드 소스코드 보기 출처 2023. 6. 29.
[백준 1717] 집합의 표현 [Java] 풀이 대표적인 Disjoin Set 문제이다. 일전에도 기본 Set이 아닌 Disjoin Set을 이용해 문제를 푼 경험이 있다. [백준 1043] 거짓말 [Python] 풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(peop kyr-db.tistory.com 문제에서 주어진 n + 1개의 집합은 Disjoin Set을 이용할 때 기본적으로 자신의 부모는 자신임을 나타내는 과정이다. 때문에 n + 1의 인덱스에 대해 자신의 인덱스로 초기화를 해주면 된다. 그 이후로는 문제에서 주어진대로 집합 a, b에 대해 입력을 받아 공통 부모를 갱신하거나.. 2023. 6. 28.

티스토리툴바