코딩테스트2 지수법칙 & 모듈러 연산 알고리즘 문제를 풀다가 지수법칙과 모듈러 연산에 관한 수학적인 문제가 나와 기억하기 위해 작성한다.지수법칙(거듭제곱의 곱)지수법칙은 다음과 같다.$$x^{n} \ast x^{m} = x^{n+m}$$ ex) $x^8$ 지수가 짝수일 때 즉, $x^8 = x^{4+4}$= $x^4 * x^4$= $(x^2 * x^2) * (x^2 * x^2)$= $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x^1 * x^1))$ ex) $x^9$ 지수가 홀수일 때 즉, $x^9 = x^{4+4} * x$= $x^4 * x^4 * x$= $(x^2 * x^2) * (x^2 * x^2) * x$= $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x.. 2025. 2. 13. 누적합(Prefix Sum) 누적합(Prefix Sum)누적합은 요소들의 누적된 합의 의미를 얘기합니다.배열의 첫 번째 0번째 배열의 요소부터 누적시키면서 더한 배열을 활용합니다. 일부 구간에 대한 합을 구하는 문제에서 사용이 됩니다. 단, 배열의 값들이 변하지 않는다는 전제가 필요합니다. $ N = 5 $ 인 N 크기의 정수 배열 arr이 있을 때 여러 개의 구간 [a, b]에 대해 합을 구하려고 합니다. $ 1\leq a\leq b\leq N $$$ arr[a]+arr[a+1]+\cdots+arr[b] $$Index i01234arr[i]16425 간단하게 생각할 수 있는 방법은 반복문을 돌려서 각 요소를 더하는 것입니다. 이 방법은 각 쿼리에 대해 최대 $ O(N) $ 시간 복잡도를 가지고, 만약 M개의 쿼리가 주어지면 시간 .. 2025. 1. 19. 이전 1 다음
