최소공통조상2 [백준 Gold 3] 11812 K진 트리 - Java 문제링크 : https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 접근 과정 : 트리에서 부모 인덱스로 자식 인덱스를 계산하고, 자식 인덱스로 부모 인덱스를 계산하는 방식을 사용했다. 흔히 이진트리에서는 자식/2가 부모 인덱스가 되는 것처럼 이를 이용해 계산하려고 했다. 자식 인덱스를 보고 부모의 인덱스를 계산할 수 있는 방식이 필요했다. 나는 여려 계산 끝에, 부모 = (자식+K-2)/.. 2022. 1. 3. [백준 Gold 4] 3584 가장 가까운 공통 조상 - Java 문제링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 접근 과정 : 부모 - 자식 관계가 주어지고 두 노드가 주어졌을 때, 그 두 노드의 가장 가까운 공통 조상을 찾으면 된다. 저장한 부모-자식 관계를 따라서 노드 A의 조상을 체크한다. DFS로 B의 조상을 탐색하면서 A의 조상체크가 되어있는 조상을 발견하면 리턴한다. 소스 코드 및 결과 : package BOJ; /* 가장 가까운 공.. 2022. 1. 2. 이전 1 다음
