매일 조금씩

#문제 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #풀이 LCA 알고리즘을 이용해 풀었다. 입력 시 parent, child 관계를 명시해주기 때문에 인접 노드 리스트에 정보를 양쪽으로 넣어주지 않았다. child 방향으로 인접 노드 리스트가 구성되었기 때문에, depth 갱신 시 계산된 node에 대해 calculated 여부를 체크하지 않았다. parent 정보가 이미 있기 때문에 d..

#문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #풀이 트리의 두 노드가 주어지고 최소 공통 조상을 찾는 문제이다. (Lowest Common Ancestor) 입력받은 노드의 연관 관계를 인접 노드 리스트로 저장해둔다. root node를 시작으로 dfs로 모든 node의 parent와 depth를 갱신한다. 그리고 입력 받은 두 점의 depth를 비교하여 depth의 차이가 있을 경우 depth가 더 큰 node 값을 해당 no..