프로그래밍 공부 노트

배열의 [a, b] 구간의 합을 구할 때, 구간에 속하는 값을 각각 더하는 연산은 시간 복잡도 O(n)으로 매우 느리다. 크기가 작은 구간합을 한 번만 구하는 경우에는 문제가 없지만, 크기가 크거나 구간합을 여러 번 구할 경우 매우 느리기 때문에 다른 방법을 사용해야 한다. 배열의 0번째 성분부터 k번째 성분을 더한 값을 sum[k]라고 하자. 구간 [a, b]의 합은 곧 a부터 b까지 더한 값이므로, 1부터 b까지 더한 값에 1부터 a - 1까지 더한 값과 같다. 이 값은 sum[b] - sum[a - 1]과 같으므로, 구간 [a, b]에서의 합은 곧 sum[b] - sum[a - 1]과 같다. 이 방법을 사용하면 sum을 만들 때의 시간복잡도가 O(n)이 되지만, 이후 구간합을 구할 때의 속도가 O(..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 각 구간의 합을 sum에 저장한 뒤, 각 테스트 케이스에서 구간에 맞는 합을 출력한다. #include using namespace std; #define MAX_N 1024 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // N: 표의 행과 열의 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 첫 번째 수부터 i번째 수까지의 합을 각각 배열 sum에 저장한 뒤, 각 테스트 케이스에서 sum[j] - sum[i - 1]을 출력한다. #include using namespace std; #define MAX_N 100000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NU..

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 입력받은 두 배열의 모든 부분합을 구한 뒤, A의 각 부분합 a에 대해 T - a를 B에서 찾아 그 횟수를 계산하면 된다. #include #include using namespace std; #define SUM_LEN 500500 int A[SUM_LEN], B[SUM_LEN]; // 배열을 입력받아 모든 부분합을..