매맹이의 기록

문제 풀이 순서는 아래와 같다.1. 데이터의 개수 N과 질의 개수 M 입력2. 구간 합을 구할 대상 배열 입력3. 구간 i,j 입력4. 출력 이전 글에 구간 합에 대한 내용을 정리했으니참고하길 바란다.https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한binaryroot.tistory.com 글을 확인했다면, 풀이를 시작해보자.  N과 M 입력int n,m;cin >> n >> m; 배열은 100000를 넘을 수 없으니const로 미리 선언해주기const int NMAX = 100020;int a..

구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.배열 A가 있을 대 합 배열 S는 아래와 같이 정의할 수 있다.S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]    // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이다.합 배열을 미리 구해 놓으면 일정 범위의 합을 구하는 시간 복잡도가 줄어든다. 어떻게 줄어드나요?--> O(N)에서 O(1)이라는 선형 시간으로 줄어들게 됩니다 :) A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우,최악의 경우를 생각해보자.i가 0이고 j가 N인 경우일 것이고,..