sparse table2 [백준 11438] LCA 2 [Java] 문제https://www.acmicpc.net/problem/11438풀이기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java] [백준 11437] LCA [Java]문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1kyr-db.tistory.com각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 .. 2025. 1. 26. LCA, (Lowest Common Ancestor, 최소 공통 조상) 트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다... 2025. 1. 25. 이전 1 다음
