합성함수와 쿼리 (1) 썸네일형 리스트형 [백준] 17435. 합성함수와 쿼리 풀이. sparse table이라는 자료구조를 이용해야한다. sparse table은 정적 구간 질의를 처리할 수 있는 자료구조인데 대부분의 구간 질의를 O(log n)시간에 처리하지만 특정한 연산에 대해서는 O(1)의 시간 복잡도를 가지는 특징을 가지고 있다. sparse table로 구간 질의를 처리하기 위해서는 배열이 정적이어야한다. 해당 문제를 살펴보면 f2(1) = f(f(1)), f4(1) = f2(f2(1))과 같은 구조로 되어있다. 즉 sparse table에는 2의 제곱으로 늘어나는 값들을 저장해서 풀면된다. 아직 확실히 이해가 되지 않아서 다시 풀어보아야 할 것 같다. 소스코드. 이전 1 다음
