Algorithm29 [야매 알고리즘] Disjoint-set(Union-find) 야매 알고리즘? 더보기 알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다. 전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다. 개요 Disjoint-set: 서로 겹치지 않는 부분 집합들로 이루어진 데이터를 다루기 위한 자료구조. union, find 연산으로 주어진 데이터를 disjoint-set으로 만들어 다룰 수 있다. Disjoint-set은 forest 형태로 표현할 수 있는데, 같은 부분 집합에 있는 원소들이 하나의 tree를 이루는 형태이다. 위 그림의 각 tree가 겹치지 않는 하나의 .. 2021. 8. 24. [백준] 공장(7578) Java 문제 링크 https://www.acmicpc.net/problem/7578 문제 요약 더보기 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다 또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉, 각 열에 있는 N개의 기계끼리는 서로 다른 식별번호를 가지고 있으며, 반대쪽 열에 있는 같은 식별번호를 가진 기계와 케이블로 이어져 있다. 기계들은 아래 그림과 같이 식별번.. 2021. 8. 24. [백준] 단절선(11400) Java 문제 링크 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 문제 요약 더보기 그래프가 주어졌을 때, 단절선(bridge)을 모두 구해 출력하는 프로그램을 작성하시오. 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 입력 더보기 첫째 줄에 두 정수 V(1≤V≤100,000),.. 2021. 8. 13. [백준] 할로윈 묘지(3860) Java 더보기 https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 문제 요약 더보기 할로윈에 할짓이 없는지 묘지 탐험을 하는 상근이. 입구로 들어가서 출구로 최대한 빨리 나오는 것이 목표. 묘지는 W × H 크기의 그리드 형태. 묘지의 입구는 (0, 0)이고, 출구는 (W-1, H-1)이다. 상근이는 최대한 빨리 묘지를 나가려고 한다. 그리고 상근이는 이동하던 도중 출구에 도달하면 그 즉시 묘지를 빠져나간다. 상근이는 현재 있는 칸과 동, 서, 남, 북으로 인.. 2021. 8. 11. 이전 1 ··· 3 4 5 6 다음
