안녕

0. 문제 링크 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 풀이 방법 일단 딕셔너리를 사용해서 B의 부모에 A를 넣었다. 이를 이용해서 각자 자신의 부모를 저장할 수 있게 만들어놓았다. 마지막에 내가 찾고자 하는 a와 b가 있다고 가정하자. a의 부모를 루트 노드 전까지 계속해서 참조하면서 부모들을 집합에 넣었다. 마지막으로 b를 계속해서 루트 노드로 올라가면서 부모들을 집합에 있는..

0. 문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1. 풀이 방법 문제를 보고 이건 탐색 기법을 써야겠다고 생각을 했다. 문제 무작정 DFS, BFS를 쓰는 건 좀 아닌 것 같았다. 왜냐면 모든 노드에서 다른 노드를 탐색하는 방법을 사용하면 n^2이 될 것 같았기 때문이다. 어떻게 최장거리를 탐색할 것인가에 대해 고민을 했다. 방금 글 쓰면서 떠오른건데 TSP를 조금 손 봐서 최장거리를 찾아낼 수 있을 것 같다..