HwangHub

🤔 Intuition 처음에 완탐인 줄 알았다. N과 M이 50 이하이고 시간제한이 2초 이내라서 거의 확신을 했다. 근데, 일단 TC만 맞고 나서, 제출하니까 3%에서 바로 틀렸다. (실전이였다면 맞았다고 착각해서 틀렸을 확률 99.9%) 진실을 아는 사람들이 있는 파티에 참여하는 사람들도 진실을 알게 되는데, 이게 1다리만 계산하면 되는 게 아니라 엮이는 사람 간의 관계 모양이 skewed tree가 될 경우에는 반복수를 감안할 수 없기 때문에 브루트포스로는 반복수의 기준이 명확하지 않다. 즉, 관계성을 계속 저장해둬야 하는 문제였던 거다. 이는 사람간의 그래프를 형성하는 문제라고 볼 수 있으므로, union find로 풀어낼 수 있다. 🔎 Algorithm & Complexity * @algorit..

문제 링크 문제 해석 트리 구조에서 공통된 조상 중 가장 가까운 조상을 찾는 건 그래프 알고리즘 중 유니온파인드 알고리즘의 '파인드' 부분을 활용하면 될 것으로 보았다. 아울러 그 노드 기준으로 자식 노드의 개수를 세는 건 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..