반응형 LCA4 [백준 11438] LCA 2 문제 출처 : https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 앞서 풀어보았던 LCA 문제의 심화 버전 입니다. 입력과 출력의 형식이 똑같지만 주어지는 N과 노드의 쌍 M의 수가 늘어나 있습니다. 따라서 기존의 LCA 문제를 푸는 방식으로는 시간초과가 발생합니다. LCA의 풀이 방법을 생각해 보겠습니다. 두 정점의 깊이를 맞춰 준다. 깊이가 같다면 공통 조상이 나올 때까지 하나씩 위로 올라간다. 이 두 가지 방법으로 LCA를 찾아주었습.. 2023. 11. 15. [백준 11812] K진 트리 문제 출처 : 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 문제 이해하기 최소 공통 조상(LCA)를 찾는 문제 입니다. 다만 일반적인 방법으로 풀 수 없습니다. 왜냐하면 메모리 사용을 최소로 해야 풀리는 문제이기 때문입니다. 그냥 LCA를 푸는 방식으로 풀게되면 메모리 초과를 경험하게 됩니다. 결국 이 문제는 K진 트리의 특성을 이용하여 각 노드의 부모와 깊이를 찾아 해결해야 합.. 2023. 11. 6. [백준 11437] LCA 문제 출처 : https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 가장 기본적인 형태의 LCA 문제 입니다. LCA 알고리즘의 설명은 이전에 게시한 알고리즘 설명으로 대신하겠습니다. 2023.10.06 - [알고리즘 설명] - 최소공통조상(LCA) 최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리.. 2023. 10. 10. 최소공통조상(LCA) LCA란? 최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리즘 입니다. 위와 같은 그래프가 있을 때 6번 정점과 9번 정점의 최소 공통 조상은 3번 입니다. 우리는 눈으로 바로 3번이 최소 공통 조상이라는 것을 찾을 수 있지만 알고리즘으로 이를 찾으려면 쉽지 않습니다. 어떻게 찾을 수 있을지 한번 생각해 보고 다음을 읽어보시기 바랍니다. 알고리즘 이해하기 최소 공통 조상을 찾는 방법은 하나씩 자신의 부모를 타고 올라가다가 공통으로 만나는 첫 번째 정점을 찾는 것입니다. 8번과 9번의 최소 공통 조상을 찾는다고 해보겠습니다. 두 정점의 부모를 찾아 올라갑니다. 먼저 8의 부모인 5와 9의 부.. 2023. 10. 9. 이전 1 다음 반응형
