LCA
-
(라이님 블로그 대회 알고리즘 따라잡기 30) LCA(Lowest Common Ancestor)PROGRAMMING/알고리즘 2024. 7. 29. 11:58
오늘은 LCA를 배워보았다. 그 전에 Sparse Table에 대해 알아두면 좋을 것 같아 Sparse Table에 대해서도 공부해보았다. 라이님 LCA 포스팅을 보다보니 Sparse Table이 나왔는데 전에 본 적이 없어서 이 참에 공부! Sparse Table에 대한 설명은 블로그를 참고하고, 아래는 아주 조금 보기 쉽게 고친 코드이다.#include using namespace std;const int MAX = 500001;const int MAX_D = 19; // 2^k >= MAX인 최소의 kint main() { // next의 크기가 너무 클 경우 vector>로 정의 int M, next[MAX][MAX_D]; // 정점 입력 scanf("%d", &M); for..