본문 바로가기

Algorithm/Dis-Joint Set

Baekjoon 2463 비용 2019. 2. 13. Link https://www.acmicpc.net/problem/2463 소스결과 3948 KB / 44 ms 출처 Baekjoon, 한국정보올림피아드 지역본선 2001 중/고등부 언어 C++ 17 분류 Disjoint-Set 설명 정점과 가중치가 있는 간선으로 이루어져있는 그래프에서 특정 방식으로 된 연산을 진행 할 때 연산의 총 합을 구하는 프로그램을 작성하자 처음에 봤을 때 이해가 조금 안됬던 문제. 연산은 쉽게 이해가 가지만 총 합이라는 의미가 이해가 잘 안갔었다. 결론은 주어지는 모든 정점 중 2개의 점을 선택하는 경우에 대한 연산의 총 합을 구하는 문제. 앞 문제와 같이 해결 방식을 순차적 방법으로 해결 하는 것 보다 역순으로 가중치 총합을 이용하는 방법으로 해결 했다. 또한 역순으로 진행 ..
Baekjoon 13306 트리 2019. 2. 13. Link https://www.acmicpc.net/problem/13306 소스결과 10180 KB / 132 ms 출처 Baekjoon, KOI 2016 중등부 언어 C++ 17 분류 Disjoint-Set 설명 그래프의 정보가 주어지고, 그래프의 일부 내용이 변경 되었을 때 주어지는 질의에 대해서 답을 출력해주는 프로그램을 작성한다. 여태껏 문제와는 문제를 보는 방식이 조금 달랐던 문제. 좋은 내용을 배웠다. 주어지는 질의에 대해서 질의를 역순으로 해결해 나가면서 정답은 질의 순으로 제출하는 방법이다. 결과적으로 질의가 시작되기 전의 그래프는 주어진 그래프의 모습일테니 거꾸로 생각해서 풀어도 문제가 없다. 출력만 유의하면 될 뿐 Disjoint-Set의 기본 골격을 유지하고 질의를 거꾸로 풀어나가보..
Baekjoon 4195 친구 네트워크 2019. 2. 13. Link https://www.acmicpc.net/problem/4195 소스결과 4360 KB / 132 ms 출처 Baekjoon, Waterloo's local Programming Contest, 27 September, 2008 언어 C++ 17 분류 해싱, 최소 스패닝 트리, 강한 연결 요소, Disjoint-set, 최대 독립 집합 설명 친구를 모으는 것이 취미인 민혁이가 자신의 친구 관계를 줄 때, 두 사람의 친구 네트워크에 현재 몇명이 있는지 구하는 프로그램을 만들어주자. Disjoint-Set을 이용하여 친구 관계를 Tree형태로 저장한다, 또한 입력되는 순서에 따라 결과 값이 다르게 저장된다. 자료형을 직접 String으로 저장하면 비교 연산에서 오랜 시간이 필요하게 된다. 친구이름..
BaekJoon 1717 집합의 표현 2019. 2. 13. Link https://www.acmicpc.net/problem/1717 소스결과 5896 KB / 40 ms 출처 Baekjoon 언어 C++ 17 분류 Disjoint-set 설명 0 ~ n 까지 총 n + 1개로 구성된 집합이 합 연산과 두 원소가 같은 집합에 속해 있는지 구하는 연산을 진행 할 때 같은 집합에 속하는지 확인 하는 연산에 대해서 결과 값을 출력해주어야 한다. Dis-Joint Set에 대한 기초적인 문제, 추가로 위 문제에서는 높이를 최대 2로 낮추는 작업을 해주어야 시간제한에 걸리지 않는다. 합집합을 구하는 연산을 진행 할 때 부모를 찾는 작업을 진행 해야 하는데 그 과정에서 높이를 압축시키는 과정이 진행 된다. 스터디를 진행 하면서 푸는 문제이기에 DIs-Joint Set을 클..

티스토리툴바