prefix sum
-
[백준] 10986번 나머지 합문제 풀이 2020. 8. 1. 13:56
10986 나머지 합 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이)update 쿼리가 없고, 구간 합만 구해서 나머지를 확인하면 되는 문제라segment tree 가 아니고 prefix sum 을 이용한 문제다.그리고 모든 ..
-
Prefix sum알고리즘 2020. 8. 1. 12:34
Prefix sum (구간합) Algorithm - 구간 합이란? 배열 전체 값 중 L ~ R 번째 원소 구간의 합을 의미 - 구현 방법 : Prefix sum algorithm은 데이터 원소들을 누적해서 합한 값을 이용한다. a1, a2, ..., aN 전체 N개의 숫자들이 있을 때 prefix sum의 i번째 값을 구하면 Pi = a1 + a2 + a3 + ... + ai ex) 숫자 5개가 있다고 하자. {1,2,3,4,5}; 그러면 prefix[6] = {0,1,3,4,10,15}; 만약 1번째부터 3번째까지 합을 구하고 싶다면 : prefix[3] - prefix[1-1] = 4 - 0 = 4 이런식으로 계산. => prefix sum의 차로 구간합을 계산한다. L ~ R까지 합을 구하고 싶으면..