Algorithm/희소 테이블
-
희소 테이블(Sparse Table)Algorithm/희소 테이블 2020. 3. 20. 03:41
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.net 위의 문제를 풀기위해 사용되는 테크닉 입니다. 합성함수를 해결하기 위해 n번 반복하는 것이 아닌 미리 테이블을 만들어 특정원소에서 1번 갔을때, 2번갔을때, 4, 16, 32 ...... 와 같이 이진수의 자리수만큼 이동했..