2023-12-03 PS 공부
오늘부터 PS 공부일지를 써 보려고 한다! 입시가 끝나서 PS를 자유롭게 할 수 있는 몸이 되었으므로,,, 앞으로 꾸준히 글을 쓸 예정이다. 오늘은 LCA 알고리즘과 희소 테이블을 공부했다. 15480번: LCA와 쿼리(P2) 케이스 분류가 정말 빡센 문제였다. 쿼리로 들어오는 두 정점이 일직선 상에 있는지 아닌지를 우선 나누고, 일반적인 트리의 형태를 그려서 각 정점별로 답이 될 수 있는 값을 찾는다. 이 때 판단의 기준을 1번 정점, u, v, lca(u, v), 그리고 각 정점의 depth 값으로 한다. 13511번: 트리와 쿼리 2(P3) lca, 그리고 희소 테이블(binary shifting)을 이용하는 문제이다. 1, 2번 쿼리 모두 lca를 찾는 과정에서 만든 이동 배열을 재사용해서 해결할..