분리 집합12 [자바] 백준 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. [자바] 백준 28276 - Yawned-Zoned (java) 목차 문제 : boj28276 필요 알고리즘 이분 탐색(binary search), 매개 변수 탐색(parametric search) 이분 탐색을 응용한 매개 변수 탐색 알고리즘 문제이다. 흔히 결정 문제라고 부르는 형태의 문제이다. 물론 결정 문제로 어떻게 만들지는 아이디어가 떠올라야 하긴 하다. 분리 집합(disjoint set) 결정 문제로 풀고자 할 경우, 분리 집합을 써야 효율적으로 짤 수 있다. 애초에 시간 제한이 빠듯한 문제라 다른 방법으론 통과가 힘들 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보.. 2023. 7. 18. [자바] 백준 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. [자바] 백준 2162 - 선분 그룹 (java) 문제 : boj2162 필요 알고리즘 개념 분리 집합 그룹의 개수 및 그룹의 크기를 구하기 위해 분리 집합 알고리즘을 알고 있으면 좋다(안써서 푼 사람들도 있긴하다). 선분 교차 판정 (기하학, CCW) 선분 교차 판정 알고리즘으로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 union-find를 쓸 때, 코드상의 parents 배열 기준으로 그룹의 메인 번호는 음수, 나머지는 양수로 메인 번호를 나.. 2022. 11. 26. [자바] 백준 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. 이전 1 2 다음
