Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

36. 최소 공통 조상

트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.

2. 합성함수와 쿼리

17435번

효율적인 LCA 구현을 위해 필요한 sparse table 자료구조를 배워 봅시다.

이번 문제는 n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하는 문제이다.

Sparse table이란?
조건 1. array에 저장된 값이 변하지 않는다.
조건 2. f(a, b, c) = f(a, (b, c)) = f(f(a, b),c)로 결합 법칙이 성립한다.
위 조건을 만족할 때 쿼리를 O(lgN) 만에 처리할 수 있는 자료 구조이다. 전처리 과정을 통해 배열 내 구간의 쿼리를 빠르게 수행할 수 있도록 하는 자료구조라고 볼 수 있다. 2의 거듭제곱인 범위의 구간값을 미리 계산해 저장해놓고 이용하는 방식이다.
시간복잡도를 O(log n)까지 줄일 수 있다.

Java / Python

• Java

import java.io.*;
import java.util.*;

public class Main {
	private final static int log = 19;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int M = Integer.parseInt(br.readLine());
		int[][] dp = new int[log + 1][M + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i < M + 1; i++) {
			dp[0][i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i < log + 1; i++) {
			for (int j = 1; j < M + 1; j++) {
				dp[i][j] = dp[i - 1][dp[i - 1][j]];
			}
		}

		int Q = Integer.parseInt(br.readLine());
		while (Q-- > 0) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			for (int b = 0; b < log; b++) {
				if ((n & (1 << b)) > 0) {
					x = dp[b][x];
				}
			}
			sb.append(x).append("\n");
		}

		bw.write(sb.toString() + "\n");

		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
input = sys.stdin.readline

log = 18
M = int(input())
f = [0]+list(map(int,input().split()))
dp = [[f[i]] for i in range(M+1)]

for j in range(1, log + 1):
    for i in range(1, M + 1):
        dp[i].append(dp[dp[i][j-1]][j-1])

Q = int(input())
for _ in range(Q):
    n,x = map(int, input().split())
    for b in range(log, -1, -1):
        if n >= 1 << b:
            n -= 1<<b
            x = dp[x][b]
    print(x)