누적합

누적합

배열이나 문자열에서 특정 구간의 합이나 빈도를 빠르게 계산할 때 매우 유용합니다. 특히 다수의 쿼리를 처리하는 문제에서 시간 복잡도를 개선하는 데 큰 효과가 있습니다.

Solution Key:

원본 배열을 기반으로 누적합 배열을 만듭니다.
누적합 배열[i] = 누적합배열[i-1] + 원본배열[i]
구간 합은 Sum[r(종료구간)]- Sum[l-1(시작구간)]으로 빠르게 계산합니다.

1. 구간 합 구하기
   배열에서 여러 쿼리로 [l, r] 구간의 합을 구해야 할 때, 매번 구간의 합을 직접 계산하는 대신 누적합 배열을 미리 계산해두면 각 쿼리를 O(1) 시간에 처리할 수 있습니다.

2. 2차원 배열에서 구간 합 구하기
   2D 그리드에서 구간 합2차원 배열에서 여러 번의 쿼리로 특정 영역의 합을 구하는 문제.쿼리를 O(1)에 처리할 수 있습니다.

Solution Key:

2차원 배열에 대해서도 누적합 배열을 만들고, 특정 영역의 합은 사각형 영역으로 빼고 더하는 방식으로 계산합니다.
예시 문제:

3. 문자열 내에서 특정 문자 개수 세기(==빈도)
   문제 유형: 문자열에서 특정 문자나 문자가 몇 번 나왔는지를 구하는 문제.

4. 빈도 분석 및 데이터 통계 계산
   문제 유형: 데이터가 주어졌을 때, 특정 구간 내에서의 빈도를 계산하거나 특정 값의 등장 횟수를 물어보는 문제.

Solution Key:

해당 구간의 빈도는 미리 계산한 누적합을 활용해 빠르게 구합니다.

5. 연속적인 부분 합이 특정 조건을 만족하는 경우 찾기
   배열에서 연속된 부분 합이 특정 값을 넘거나, 딱 맞는 경우를 찾는 문제.
   연속 부분 배열 중에서 합이 K가 되는 경우의 수를 구하는 문제.
   두 인덱스 사이의 합을 빠르게 계산하거나 특정 조건을 만족하는 부분 배열을 찾습니다.

Solution Key:

투포인터

6. 사이클이나 중복이 있는 구조에서 빠르게 구간 값 찾기
   문제 유형: 사이클이 존재하는 구조에서 특정 구간 내에서 값을 빠르게 찾는 문제
   특정 구간의 데이터를 반복적으로 계산해야 할 때, 누적합을 이용해 이전 계산 결과를 재사용할 수 있습니다.