disjoint set9 [자바] 백준 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. [자바] 백준 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. [자바] 백준 3197 - 백조의 호수 (java) 문제 : boj3197 필요 알고리즘 개념 너비 우선 탐색 (bfs) 만날 수 있는 시간을 구해야 하므로 너비 우선 탐색으로 탐색하는 것이 적합하다. 분리 집합 (disjoint set) 분리 집합 알고리즘 (유니온 파인드)를 사용해 두 백조가 서로 만날 수 있는 구한다면 매번 백조가 만날 수 있는지 dfs 등을 통해 확인하지 않아도 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS에 대해 잘 모른다면 이 글.. 2022. 9. 17. [자바] 백준 20955 - 민서의 응급 수술 (java) 문제 : boj20955 필요 알고리즘 개념 트리 트리의 특징에 대해 알고 있어야 이 문제를 풀 수 있다. 분리 집합 (disjoint set) 혹은 유니온 파인드 (union-find) 분리 집합 알고리즘인 유니온 파인드를 알고 있으면 간단하게 이 문제를 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서는 정점의 개수가 주어지고(N), M개의 간선 정보가 주어진다. 그럼 다음의 입력값을 생각해보자. .. 2022. 7. 31. 백준 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. 백준 10542 자바 - 마피아 게임 (BOJ 10542 JAVA) 문제 : https://www.acmicpc.net/problem/10542 오랜만에 엄청 재밌는 문제였다. 그다지 복잡한 알고리즘적 지식을 요구하지 않으면서도 이렇게 난이도도 어느정도 있으면서 재밌게 낸것도 모자라서, 심지어 예제 입력들도 풀이를 생각하기 편하게 잘 내줬다. 출제자 멋져 AD-HOC 문제로, 딱 이거다! 하는 해법 없이 논리적으로 맞다고 생각하는 방식들을 찾아 적용하며 풀어야 하는 문제이다. 일단 풀이과정은 한가지 확실한 조건(이하 '1'이 이에 해당함)에서 시작하면 판정을 위한 다른 방식들로 생각을 이어갈 수 있다. 1. 문제에서 제시된 '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라, 일단 맨 처음에 들어온 입력에서 한 번이라도 지목을 당.. 2021. 11. 18. 이전 1 다음
