본문 바로가기

구간합2

[기본] 구간합 응용 들어가며구간합의 중요성을 더 알아보고자 구간합과 관련된 응용문제를 더 풀어보고자 합니다. 지난 구간합보다는 조금 더 어려운 문제를 풀어보려고 합니다. 다시 한 번 구간합을 구해놓는 것이 얼마나 시간복잡도를 낮춰주는 지 체크해보는 시간이 될 것 같습니다. 문제백준 11660: 구간합 구하기 5(링크) 풀이1#include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int size, count; cin >> size >> count; vector> sumMetrix(size + 1); for (int i = 1; i num.. 2025. 3. 13.

[기본] 합배열과 구간 합 구하기 합배열과 구간합합배열은 특정 배열의 누적 합을 저장하는 배열로, 구간합을 빠르게 계산하기 위해 사용됩니다. 배열의 i번째까지의 누적 합을 저장하여, 특정 구간의 합을 O(1) 시간 복잡도로 구할 수 있습니다.합배열 계산배열 A가 주어졌을 때, 합배열 S는 다음과 같이 정의됩니다.S[i]=A[1]+A[2]+...+A[i]즉,S[0]=0 (기본값)S[i]=S[i−1]+A[i]를 만족합니다.예제배열 A=[2,4,5,7,9,12] 가 주어졌을 때, 합배열 S 는 다음과 같습니다.iA[i]S[i]00012224635114718592761239 구간합 계산구간합을 구하는 공식은 매우 쉽습니다. 구간 i에서 j까지의 구간합을 구하는 공식은 다음과 같습니다.S[j] - S[i -1]예: 구간 [2, 5]의 합은 S[5.. 2025. 3. 8.

이전 1 다음

티스토리툴바