최소 공통 조상2 [LCA] 백준 13116번 30번 (Swift 풀이) 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net [문제] 혹시 2007학년도 대학수학능력시험 수리영역 가형 이산수학 30번 문제를 아는가? 여러분은 수능을 치는 수험생의 마음으로 이 문제를 해결해야만 한다. 하지만 우리는 저작권 위반으로 판사님을 뵙고 싶지 않았기 때문에 이 문제를 직접 수록할 수는 없었다. 아래 링크 중 하나를 클릭해서 pdf 파일을 내려받아 가장 마지막 페이지를 보면, 위의 그림과 아주 유사한 문제가 하나 있을 것이다. 여러분은 바로 그 문제를 해결해야만 한다... 2021. 4. 21. LCA (Lowest Common Ancestor) LCA는 이름에서 알 수 있듯이 두 정점 A와 B에서 가장 가까운 공통된 조상을 찾는 알고리즘입니다. 여기에는 2 가지 방법이 있는데요, 하나씩 조상 노드를 살펴보는 방법과 DP를 사용하는 방법이 있습니다. 트리의 depth를 H라고 할 때, 조상 노드를 하나씩 살펴보는 방법으로는 보통 시간복잡도가 O(H)가 나오지만, 최악의 경우 O(N)이 걸릴 수 있습니다. 하지만 DP를 사용하게 된다면? 보통 O(log H)가 걸리지만, 최악의 경우 O(log N)이 걸립니다. DP를 사용하는게 훨씬 빠르죠? 그래서 노드의 개수가 매우 많고, 검사해야할 노드가 매우 많은 경우에 DP를 사용한 방법을 활용하면 빠르게 답을 찾을 수 있습니다! 먼저, 조상 노드를 하나씩 살펴보는 방법은 사실 간단해요. 두 정점 A와 B.. 2021. 4. 1. 이전 1 다음
