개발자공부일기

https://www.acmicpc.net/problem/1717기본적인 유니온 파인드를 사용해서 푸는 문제입니다. 첫째줄에 n,m이 주어지고 n개의 원소의 집합이 있으며 m개의 줄만큼 명령이 주어집니다.0 a b는 union을 1 a b는 두 수가 같은 집합에 속하는지 판별하는것을 의미합니다.우리는 vector로 "arr[n] = 대표 노드" 이렇게 표현할겁니다. 초기 상태모든 노드가 자기 자신을 대표 노드로 가집니다.즉, arr[i] = i 입니다.12345671234567집합 상태: {1}, {2}, {3}, {4}, {5}, {6}, {7}1단계: 0 1 3 (union(1,3))1의 루트 = 1, 3의 루트 = 3 → 3을 1의 대표로 연결.12345671214567집합 상태: {1,3}, ..

유니온 파인드(Union-Find) 알고리즘은 여러 원소들을 몇 개의 그룹(집합)으로 나누고, 다음 두 연산을 빠르게 수행하는 데 목적이 있는 서로소 집합(Disjoint Set Union, DSU)을 효율적으로 관리하기 위한 자료구조이자 알고리즘입니다.핵심 연산Find(찾기)어떤 원소가 속한 집합(대표자, 루트 노드)을 찾는 연산.보통 트리 구조로 구현되고, 루트 노드가 그 집합의 대표자가 됩니다.경로 압축(Path Compression) 기법을 쓰면 시간 복잡도를 크게 줄일 수 있습니다.Union(합치기)두 원소가 속한 집합을 하나로 합치는 연산.두 집합의 대표자를 찾아서 하나로 연결해 줍니다.보통 "랭크(rank) 기반 합치기" 또는 "사이즈 기반 합치기"를 사용해서 트리가 한쪽으로 치우치지 않게 ..

https://www.acmicpc.net/problem/2251 세 개의 물통 A, B, C가 있다. A, B, C 물통의 용량이 주어지고, 처음에는 C 물통에만 물이 가득 차 있다.이때 A 물통이 비어 있을 때, C 물통에 담겨 있을 수 있는 물의 양을 모두 구하는 문제다. 물이 다양하게 담겨있는 여러가지 경우의 수 를 따지는 BFS(너비 우선 탐색) 방법을 이용하는 문제다.핵심 아이디어상태 표현(A, B, C) 세 물통에 들어 있는 물의 양으로 상태를 표현한다.하지만 세 개 다 저장할 필요는 없다.왜냐하면 C = 전체 물의 양 - (A+B)로 항상 계산할 수 있기 때문이다.따라서 (A, B) 두 값만 저장하면 충분하다.상태 전이(물 붓기)물을 옮기는 경우의 수는 6가지다.A→B, A→C, B→A, ..