10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 분석 (A+B)%C = ((A%C)+(B%C))이므로 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일 구간 합 배열을 이용한 식 S[i]-S[j]는 원본 리스트의 j+1부터 i까지의 구간 합이므로 합배열의 나머지 값이 같으면 두개 뽑아서 합배열 값-합배열 값으로 나누어떨어지는 구간 찾을 수 있음 S[i]%M의 값과 S[j]%M의 값이 같다면 (S[i]-S[j])..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 분석 2차원 합배열 채우기 : d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1] + a[i][j] 2차원 구간합 구하기 : d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1] 풀이 import sys input=sys.stdin.readline n,m = map(int, input().split()) # 리스트 a=[[0]*(n+1)] # 합배열 d=[[0..

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 분석 합 배열 공식 : S[i] = S[i-1] + A[i], 구간합 공식 : S[j] - S[i-1] 세그먼트 트리 : 2023.03.23 - [Algorithm PS/Tree] - 세그먼트 트리, 인덱스 트리, 구간합 풀이 import sys input=sys.stdin.readline n,k = map(int, input().split()) list = list(map(int, input().split())) # 구간합 배열 sumLi..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 1. 트리 초기화하기 ➔ setTree(idx) 트리 크기(treeSize) = 2^(K+1) ..

1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 모든 값을 update 해야함 ➔ 느림 데이터의 업데이트가 빈번하게 일어나게 되면 합배열 성능 측면에서 안좋음 ➔ 속도유지를 위해 세그먼트 트리 사용 2. 원리 1) 트리 초기화 하기 ⓪ 샘플데이터 {5, 8, 4, 3, 7, 2, 1, 6} ① 리스트 길이 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듬 2ᵏ≥ N을 만족하는 𝑘의 최솟값을 구한 후 2ᵏ * 2 N=8이므로 2³ ≥ 8 ➔ 2³ * 2 = 16 ② 시작 노드 : 2ᵏ ➔ 2³ = 8 ③ 리프 노드에 원본 ..