ps (3) 썸네일형 리스트형 희소 배열 (sparse table) 희소 배열은 특정 구간에 대한 query를 빠르게 처리하기 위한 자료 구조이다. 주로 특정 구간의 최솟값, 최댓값, 합 등을 구할 때 모든 요소를 방문하지 않고 처리하기 위해 사용된다. 예시를 통해 확인해보자. $f_{13}(x)$ 를 생각해보자. $f_{13}(x)$ 를 구하는 가장 쉬운 방법은 $f$ 를 13번 합성하는 것이다. 그러나 이는 쿼리 1개당 시간 복잡도가 $O(n)$ 이고, 전체 시간 복잡도는 $O(nQ)$ 인 비효율적인 방법이다. $f$ 를 13번 합성하는 대신 $f_{13}(x)=f_{8}(f_{4}(f(x)))$ 로 표현할 수 있다. $f_{2^{i}}(x)$ 를 매번 구하면 단순히 $f$ 를 13번 합성하는 것과 같은 시간 복잡도를 갖는다. 그러나 이 값들을 미리 저장을 한 뒤 매.. 행렬로 표현한 피보나치 수열 피보나치 수열이란 첫번째 항과 두번째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 편의상 0번째 항을 0으로 나타내기도 한다. 피보나치 수열을 수식으로 나타내면 아래와 같다. $$F_{0}=0,\;F_{1}=1,\;\;F_{n}=F_{n-1}+F_{n-2}\;(n\geq 2)$$ 이때 점화식 $F_{n}=F_{n-1}+F_{n-2}\;(n\geq 2)$ 을 아래와 같이 행렬로 나타낼 수 있다. $$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} F_{n-2} \\ F_{n-1} \\ \end{bmatrix} = \begin{bmatrix} F_{n-1} \\ F_{n} \\ \end{bmatrix}$$ 또는 2x2 행.. 모듈러 곱셈 역원 기본적으로 모듈러 연산은 곱셈 연산에 대해 다음과 같은 수식이 성립한다. $$ (A \times B)\;mod\;C = (A\;mod\;C\times B\;mod\;C)\;mod\;C $$ 이는 어떤 두 수에 대해서 두 수를 곱한 후 mod 연산을 한 것과 두 수에 mod 연산을 먼저 한 후 곱한 것이 같다는 의미이다. 그러나 나눗셈에서는 곱셈과 같이 모듈러 연산이 닫혀있지 않다. 나눗셈에 대해서 모듈러 연산을 하지 못한다면 큰 수의 나눗셈을 할 때 시간이 매우 오래 걸린다. 따라서 나눗셈에서도 위의 수식과 같은 계산을 하기 위해 필요한 개념이 모듈러 곱셈 역원이다. 기본적인 아이디어는 곱셈과 같은 형태를 만드는 것이다. 먼저 아래의 수식이 성립한다. $$a^{p}\equiv a\;\;\;mod\;p$$.. 이전 1 다음
