츈츈's Spring

유니온 파인드 알고리즘은 두 노드가 하나의 집합에 속하는지 판별하고 싶을때 매우 유용하게 사용되는 방법이다. 노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.   이렇게 복잡한 그래프에서는 빠른 시간 안에 두 노드가 연결되어 있는지 판별하는 게 힘들다.바로 이런 경우에 두 노드가 연결되어 있는지, 끊어져 있는지를 판별하는 방법이  "유니온 파인드" 이다.  두 노드가 연결되어있는지 판단하는 방법은 ,  두 노드가 하나의 집합 안에 포함되는지 확인하면 된다. 그렇게 하기 위해서는 먼저 연결되어있는 노드들을  하나의 집합으로 만드는 과정이 필요하다.  바로 이 과정이 Union (유니온) 이다.  예를들어, 1호선이 지나가는 역들은 모두 남색선으로 표시하였다. 이것이 바..

🐙 문제 https://www.acmicpc.net/problem/1707 이 문제는 " 이분 그래프 " 의 뜻을 잘 이해해야한다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 라 부른다.  쉽게 설명하자면,  그래프의 노드들을 바구니 A와 바구니 B에 나눠서 담는다고 하자. 이때 같은 바구니에 담긴 노드들끼리는 인접하면 안된다는 의미이다.   그래프가 예시로 주어졌을때,  노드를 번갈아 바구니 A,B에 나누어서 담아보면 된다.   [입력예시] 2 // 테스트 케이스 개수 3 2 // case1 : 노드의 개수, 엣지의 개수 1 32 34 4 // case2 : 노드의 개수, 엣지의 개수 1 22 3..

그래프 정리   비선형 자" 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://blog.kakaocdn.net/dna/bjE8n0/hyXzWTzIHq/AAAAAAAAAAAAAAAAAAAAACfpRH4I7TUqc4Qdqy6QaLOR0CyKo_MrtNh-tMLre6P3/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1753973999&allow_ip=&allow_referer=&signature=2IepkiJ3qpe6b26PLh8CFncnmyk%3D

문제  [백준] 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..

문제 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..