0과 1의 쉼터

문제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를 탐색하는 ..

문제https://www.acmicpc.net/problem/3584풀이문제에서 주어지는 간선이 부모-자식 관계를 나타내고 있기 때문에 별도의 알고리즘 없이 dfs으로 선형탐색하면 된다. 우선 정점 u에 대해 루트 노드까지 탐색하며 방문 표시를 해주자.정점 v에 대해 루트 노드까지 방문하지 않은 노드까지 탐색하면 된다.소스코드보기

트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다...

문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1번이라 언급되어 있으니, 1번 정점부터DFS를 통해 모든 노드의 부모 노드와, 깊이를 구해주면 된다.이제 LCA를 구해야 하는 두 노드 u, v에 대해 깊이가 다르다면 부모 노드로 올라가며 깊이를 맞춰주고,깊이가 동일한 두 노드의 부모노드가 같을 때까지, 즉 LCA를 찾아주면 된다.소스코드보기

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기