디스조인트-셋
-
백준 4195번 친구 네트워크 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 12. 20:48
이 글은 백준 알고리즘 문제 4195번 "친구 네트워크" 를 풀이한다.풀이 방법으로는 디스조인트-셋을 통해 진행된다.문제 링크 - https://www.acmicpc.net/problem/4195디스조인트 셋 이해 - http://mygumi.tistory.com/246 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 노드를 친구로, 간선을 친구 관계라고 생각할 수 있다.친구 관계라는 것은 같..
-
백준 9938번 방 청소 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 9. 20:55
이 글은 백준 알고리즘 문제 9938번 "방 청소" 를 풀이한다.풀이 방법으로는 디스조인트-셋 자료구조를 이용한다.개인적으로 보면, 굉장히 어려운 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/9938디스조인트 셋 이해 - http://mygumi.tistory.com/246 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.은기는 술병을 1번부터..
-
백준 1717번 집합의 표현 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 22:23
이 글은 백준 알고리즘 문제 1717번 "집합의 표현" 을 풀이한다.문제는 디스조인트-셋(disjoint-set)을 이용하여 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/1717디스조인트-셋 이해 - http://mygumi.tistory.com/246 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 이 문제는 디스조인트-셋에 대해 기초를 다지기 위한 가장 기본적인 문제가 된다.0일 때, 유니온(union) 을 호출하고, 1일 때, 파인드(find) 를 호출하면 된다. 다음 예제를 통해 ..
-
디스조인트-셋(disjoint-set) :: 마이구미알고리즘 2017. 11. 5. 17:27
이 글은 디스조인트-셋(disjoint-set) 자료구조를 다룬다.유니온-파인드(union-find) 라고도 불리고, 머지-파인드-셋이라고도 불리는 자료구조이다.위키백과 - 디스조인트-셋 디스조인트-셋은 해석하면 서로소 집합이라고 표현할 수 있다.서로소 집합이란, 공통된 원소가 없는 집합으로써, 교집합이 공집합인 집합이라고 보면 된다. 디스조인트-셋을 활용하기 위해서는 다음과 같은 정의를 확실히 이해해야한다. 많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조. "상호 배타"와 "독립"을 혼동해서는 안된다.독립은 집합으로 표현하면 다음과 같다. A ∩ B = 0, A ∪ B = U A와 B 사이에는 어떠한 관계도 존재하지 않다는 것을 알 수 있다.상호 배타는 다음과 같..