알고리즘/개념

알고리즘 문제를 풀다가 큰 수를 거듭제곱하게되면 시간초과 문제에 봉착하게 되는 데 이때 모듈러 연산을 사용하면 오버플로우없이 빠르게 값을 구할 수 있다. 모듈러 연산이란 나눗셈을 표현하는 식으로 A/B를 계산했을 때 몫을 Q, 나머지를 R이라 한다면 A mod B = R로 표현할 수 있다. (=A 모듈로 B는 R과 같다) 모듈러 거듭제곱 A^B mod C = ( (A mod C)^B ) mod C B의 값이 조금만 커져도 A^B의 값이 겁나게 커져서, A^B mod C를 시도하면 시간초과가 발생한다. ex) 2^90 = 1,237,940,039,290,000,000,000,000,000 왜 빠른가? 분할 정복 알고리즘을 사용하여 거듭제곱을 계산해서이다. p^n을 계산하는 대신 (p^n/2)*(p^n/2)..

요소들의 누적된 합. 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서(PSum) 이를 활용하는 것을 의미 (↔ Suffix Sum 뒤에서부터 더함) - PSum[n] 에는 배열의 n번째 인덱스의 값까지 합한 값이 들어감 - 누적합 배열을 만들 때는 0번 index를 비우고 1번부터 값을 받는 게 편하다. 활용 방법 구간쿼리 중 배열의 요소가 변하지 않는 정적배열에서 구간의 합을 구하는 데 사용함 n개의 숫자가 있고 합을 구해야할 구간이 m개 주어질 때, 매번 더하는 게 아니라 누적합 배열을 구해놓고 마이너스 연산으로 값을 구함 ex: [3,5] 구간의 합 → PSum[5] - PSum[2] - 시간복잡도: O(n*n) → O(n) *반복문으로 매번 구하면 O(n*n)..