union-find15 [자바] 백준 22956 - 소나기 (java) 목차 문제 : boj22956 필요 알고리즘 분리 집합 (union-find) 분리 집합을 활용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀기위해 알 수 있어야 하는건 말로하면 간단하다. 인접한 비가 내렸었던 땅들의 그룹들이 있다. 그리고 어딘가 비가 내렸다면, 상하좌우 인접한 비가 내렸던 땅들의 그룹을 합친다. 그리고 그 그룹들에서 가장 높이가 낮은 칸 또는 여러개라면 그 중 가장 .. 2023. 11. 24. [자바] 백준 23040 - 누텔라 트리 (Easy) (java) 목차 문제 : boj23040 필요 알고리즘 분리 집합 (union-find), 그래프 탐색 (bfs, dfs 등), 트리 (tree) 그래프 탐색과 분리 집합에 대한 개념이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 만약 서로 붙어 있는 빨간 정점 그룹들의 갯수를 알고 있다고 해보자. 그럼 간단하게 모든 검정 정점들에서 간선 1개로 갈 수 있는 모든 정점 중 빨간 정점 그룹의 수를 모두 세주면 끝나는 .. 2023. 11. 22. [자바] 백준 28251 - 나도리합 (java) 목차 문제 : boj28251 필요 알고리즘 수학, 분리 집합 (disjoint set, union-find) 기본적인 아이디어는 수학적 직관이 좀 필요하고, 그 직관을 구현하기 위해 분리 집합 알고리즘을 사용해야 하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 4개의 수 a,b,c,d가 있다고 해보자. a와 b를 합치면 ab, c와 d를 합치면 cd가 필요하다. 그 후 ab와 cd를 합쳐보면 아래처럼 식이 나.. 2023. 8. 11. [자바] 백준 20303 - 할로윈의 양아치 (java) 문제 : boj20303 필요 알고리즘 개념 분리집합 또는 dfs 또는 bfs DP로 실제 답을 구하는 로직 이전에 아이들의 그룹을 만들기 위해 분리집합 알고리즘(union-find) 혹은 그래프 탐색이 필요하다. 이하 풀이는 분리집합으로 풀었다. DP (Knapsack) DP 활용법 중 유명한 냅색류의 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 연결된 아이들의 그룹별로 선택할 수 밖에 없다. 따라서 만약.. 2023. 1. 11. [자바] 백준 2843 - 마블 (java) 문제 : boj2843 필요 알고리즘 개념 오프라인 쿼리 (offline query) 쿼리(질의)의 순서를 변경해서 푸는 아이디어를 생각해낼 수 있어야 한다. 분리 집합 (disjoint set) 분리 집합 개념과, 분리집합에서 집합이 합쳐지는 방향을 강제할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서는 조약돌이 멈추는 정점을 묻는 쿼리와 간선을 지우는 쿼리가 존재한다. 일반적으로 간선을 지우.. 2023. 1. 2. [자바] 백준 23324 - 어려운 모든 정점 쌍 최단 거리 (java) 문제 : boj23324 필요 알고리즘 개념 분리 집합 (disjoint set) 그룹의 갯수를 알아야 풀 수 있으므로 내 경우엔 분리 집합 알고리즘을 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 풀이는 금방 생각나긴했지만 가중치가 1과 0이라는 점과, 실제로 탐색을 통해 모든 정점에서 최단 거리를 판단할 경우 무조건 시간초과가 발생하도록 문제가 세팅되었다는 점에서 출제 아이디어가 좋다고 생각했다. 그래프쪽.. 2023. 1. 1. 백준 20156 자바 - 기왕 이렇게 된 거 암기왕이 되어라 (BOJ 20156 JAVA) 문제 : boj20156 구현도 빡쌘편이고 함정카드도 꽤 생각하기 힘든 녀석이었다. 역시 항상 20퍼대 이하의 정답률 문제들은 항상 뭔가가 있다. 그리고 요즘 스트릭만 채운다고 실버위주로 풀다가 오랜만에 플래 풀어보니 체감이 확 된다 ㅋㅋㅋ 1. 우선 다른거 다 빼고 동일 스터디 그룹인지 어떻게 알 수 있을지 생각해보자. 이 부분은 간단하다. union-find를 사용해 disjoint set을 파악하면 된다. 입력으로 받은 B와 C가 동일한 그룹인지 확인하려면, B와 C가 같은 그룹내에 속한지 판단만 하면 알 수 있다(일반적으로 union-find를 사용했다면 결국 find(B) == find(C) 라면 동일 그룹이다). 2. 그룹이 해제는 어떻게 해요? 생각할게 너무 많아요! 그룹을 해제하는건 어렵지.. 2022. 3. 8. 백준 15352 자바 - 욱제와 그의 팬들 (BOJ 15352 JAVA) 문제 : boj15352 1. 우선 '행동 2'만 존재할 경우 어떻게 풀 수 있을지 확인해보자. 입력으로 주어진 N개의 A값들에 대해 좌우로 인접한 항목이 같은 팬클럽 번호라면 그룹을 지어보자. 이 때, union-find를 사용하고 부모가 되는 노드에 차수를 입력해둔다고 한다면 '행동 2'에 대해 O(1)로 부모의 차수를 출력하는 것 만으로 결과를 낼 수 있다. 예를들어 parents[a]에 대해 parents[a] >= 0일 경우 부모의 번호, parents[a] < 0일 경우 부모 중 하나이며, 그 부모에 그룹지어져 있는 노드의 개수라고 하면 예제 입력 1은 다음과 같이 나타낼 수 있다. union-find의 사용방법은 다양한 편이므로, 어쨌든 해당 그룹에 포함된 개수를 한방에 알 수만 있도록 짜면.. 2022. 2. 4. 백준 20040 자바 - 사이클 게임 (BOJ 20040 JAVA) 문제 : boj20040 N개의 정점이 있는 그래프에 대해 M개의 간선을 순서대로 연결하면서 사이클이 언제 생기는지 파악하면 된다. 즉, 간선을 연결하는 중에 사이클 판정만 할 수 있다면 풀 수 있다. 내 경우엔 union-find를 사용해 disjoint set(분리 집합)에 대해 판단했다. 새로운 간선을 연결했을 때, 연결한 두 정점이 동일한 그룹이라면 사이클이 생긴 경우이므로, 현재까지 연결한 간선의 개수를 카운팅한걸 답으로 출력하면 된다. 모든 간선을 연결해도 사이클이 생기지 않았다면 0을 출력하면 된다. 코드 : github import java.io.DataInputStream; import java.io.IOException; import java.util.Arrays; public clas.. 2022. 1. 24. 백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12. 이전 1 2 다음
