오블완5 유니온 파인드 유니온 파인드 알고리즘은 두 노드가 하나의 집합에 속하는지 판별하고 싶을때 매우 유용하게 사용되는 방법이다. 노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다. 이렇게 복잡한 그래프에서는 빠른 시간 안에 두 노드가 연결되어 있는지 판별하는 게 힘들다.바로 이런 경우에 두 노드가 연결되어 있는지, 끊어져 있는지를 판별하는 방법이 "유니온 파인드" 이다. 두 노드가 연결되어있는지 판단하는 방법은 , 두 노드가 하나의 집합 안에 포함되는지 확인하면 된다. 그렇게 하기 위해서는 먼저 연결되어있는 노드들을 하나의 집합으로 만드는 과정이 필요하다. 바로 이 과정이 Union (유니온) 이다. 예를들어, 1호선이 지나가는 역들은 모두 남색선으로 표시하였다. 이것이 바.. 2024. 11. 23. [백준] 1707 이분 그래프 자바 🐙 문제 https://www.acmicpc.net/problem/1707 이 문제는 " 이분 그래프 " 의 뜻을 잘 이해해야한다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 라 부른다. 쉽게 설명하자면, 그래프의 노드들을 바구니 A와 바구니 B에 나눠서 담는다고 하자. 이때 같은 바구니에 담긴 노드들끼리는 인접하면 안된다는 의미이다. 그래프가 예시로 주어졌을때, 노드를 번갈아 바구니 A,B에 나누어서 담아보면 된다. [입력예시] 2 // 테스트 케이스 개수 3 2 // case1 : 노드의 개수, 엣지의 개수 1 32 34 4 // case2 : 노드의 개수, 엣지의 개수 1 22 3.. 2024. 11. 22. 그래프를 구현하는 방법 그래프 정리 비선형 자" data-og-host="velog.io" data-og-source-url="https://velog.io/@kwontae1313/%ED%8A%B8%EB%A6%AC%EC%99%80-%EA%B7%B8%EB%9E%98%ED%94%84%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90" data-og-url="https://velog.io/@kwontae1313/트리와-그래프에-대해-알아보자" data-og-image="https://scrap.kakaocdn.net/dn/bjE8n0/hyXzWTzIHq/EgmXpWGjqYENTCR0HpnMHk/img.png?width=781&height=535&face=0_0_7.. 2024. 11. 20. [백준] 1929 소수 구하기 자바 문제 [백준] 1929번 소수구하기 문제 방법1- 일반적인 소수 구하는 방법으로 풀기 import java.io.*;import java.util.StringTokenizer;public class Main { static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer.. 2024. 11. 19. [백준] 11047 동전0 자바 문제 https://www.acmicpc.net/problem/11047 동전의 종류와 금액이 주어질때, 해당 동전들을 가지고 금액을 만들기 위한 동전의 최소 개수를 구하는 문제이다. 동전의 개수가 최소가 되어야하므로 가장 큰 값들로 먼저 계산하면 최솟값을 구할 수 있을것이다. import java.io.*;import java.util.StringTokenizer;public class P32_동전개수의최솟값 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWr.. 2024. 11. 18. 이전 1 다음
