NAN-NOO

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net [코딩 테스트/개념] - 구간 합 # 1

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [코딩 테스트/개념] - 구간 합 # 1

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [코딩 테스트/개념] - 구간 합 # 1

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘 배열의 데이터 변경이 적을 때 활용 -> 많을 땐? index tree 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함 합 배열 S S[i] = A[0] + A[1] + ... + A[i - 1] + A[i] S[i] = S[i - 1] + A[i] 합 배열을 구해 놓으면 기존 배열의 일정 구간 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감 구간 합 공식(인덱스 i에서 j까지 합) S[j] - S[i - 1]