algoqna

20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net Disjoint-Set (상호 배타적 집합) - 트리 이용 Union-Find 1) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 ● 0 ~ n-1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만들어야 함 = 배 kkalgo.tistory.com Disjoint-Set에 대해 모른다면 위의 링크를 참조하셔도 괜찮습니다. - 전형적인 Disjoint-Set 문제 : Union-Find 이용해서 사이클..

Union-Find 1) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 ● 0 ~ n-1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만들어야 함 = 배열 선언 2) 필수적인 세 가지 연산 ● 초기화 : n개의 원소가 집합에 포함되어 있도록 초기화 ● Union(a,b) : 원소 a와 b를 하나로 합친다 == 두 집합을 하나의 집합으로. ● find(a) : 원소 a가 속한 집합을 반환한다. 3) 트리를 이용한 상호 배타적 집합 ● 한 집합에 속하는 원소들을 '하나의 트리'로 묶는다 ● 그리하여 상호 배타적 집합은 '트리들의 집합' ● 어떤 정점 v와 u가 같은 집합인지 알고싶다? * 정점 v와 u가 '같은 루트' 를 공유하고 있나를 확인한다...