11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 희소 테이블에 대해 모른다면 풀기 어려운 문제 일거 같습니다. 풀기전에 희소 테이블로 워밍업을 하고 천천히 풀어보자. 아래 주소는 희소 테이블에 관한 문제입니다. [Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 (tistory.com) [Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 Sparse Table (스파스 테이블) 특징 방..

Sparse Table (스파스 테이블) 특징 방향 그래프 입니다.모든 점이 목적지가 있습니다.그 점을 타고 새로운 점으로 갑니다.2의 제곱근으로 도착한 점을 저장합니다. (1번, 2번, 4번, 8번 이동에 대한 배열을 모두 저장합니다.) 예제를 풀면서 설명하겠습니다. https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는www.acmicpc.n..