HwangHub

문제 링크 문제 해석 트리 구조에서 공통된 조상 중 가장 가까운 조상을 찾는 건 그래프 알고리즘 중 유니온파인드 알고리즘의 '파인드' 부분을 활용하면 될 것으로 보았다. 아울러 그 노드 기준으로 자식 노드의 개수를 세는 건 dfs로 간단하게 구현할 수 있다. 문제 풀이 시간복잡도 : DFS를 인접리스트로 구현하였고(O(V+E)), 파인드 로직에서 최소 공통 root 노드를 찾기 위한 로직에서 트리 높이(h)가 최악의 경우 노드 개수(V)에 근사해지므로 O(V + E)이다. package ssafy.사전학습; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..

해석 이 문제는 인접 리스트를 이용하여 relation group의 개수를 묻는 문제이다. 따라서 그래프 탐색을 통해 연관 노드를 한번에 방문하는 방식으로 로직을 전개하면 마을의 개수를 구할 수 있다. 보통 격자 상에서의 그래프 알고리즘이 아닌, 이 문제와 같이 인접 행렬 또는 인접 리스트를 활용하는 그래프 알고리즘의 시간복잡도는 인접 행렬과 리스트 각각 O(v^2), O(v + e)이다. 이는 아래 구현된 로직에서도 확인할 수 있다. 노드의 개수가 최대 100개라고 주어져 있으므로, 인접 행렬이든 리스트든 관련 없이 문제를 풀 순 있었을 것이다. 간선의 개수는 n(n-1)/2개라고 되어있으므로 인접 행렬로 구현하였다. 풀이 DFS package ssafy.사전학습.그래프; import java.io.B..

https://www.codetree.ai/missions/2/problems/puyo-puyo?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드트리 Intermediate Low 단계의 BFS 유형을 모두 푼 김에, DFS의 테스트 문제를 다시 한번 풀어보았다. 오랜만에 푸니까 조금 헤맸지만 그래도 풀어냈음에 의의를 가지고 싶다. 문제 해석 이 문제는 BFS로도 풀 수 있을 것 같은데, 핵심은 그래프 알고리즘으로 푼다는 것이다. 인접한 칸을 하나의 블록으로 인지하는 것이고, 이어..

원래는 파이썬으로 알고리즘을 공부해왔지만, 자바로 언어를 바꿔야 할 것 같아서 풀었던 문제를 언어를 바꿔 다시 풀어보았습니다. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net public class B11724 { static boolean visited[]; static ArrayList[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new..