구간 합(Prefix Sum)

Mention : 구간 합을 구하기 위해선 합 배열을 먼저 만들어야한다➕ 효과는 굉장하다!

구간 합 (Prefix Sum)

• 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

합 배열

• 기존의 배열을 전처리한 배열
  • ex) S[i] = A[0] + A[1] + A[2] + …… + A[i-1] + A[i]
  • ex) S[3] = A[0] + A[1] + A[2] + A[3]
  • 기존 배열의 일정 범위의 합을 구하는 시간복잡도 O(N) → O(1)

  인덱스	0	1	2	3	4
  배열 A	6	8	5	7	6
  합 배열 S	6	14	19	26	32

• 합 배열 S를 만드는 공식
  • S[i] = S[i-1] + A[i]

구간 합

• 구간 합을 구하는 공식

  | 인덱스 | 0 | 1 | 2 | 3 | 4 | | — | — | — | — | — | — | | 배열 A | 6 | 8 | 5 | 7 | 6 | | 합 배열 S | 6 | 14 | 19 | 26 | 32 |

  • S[j] - S[i-1]
  • ex) 1번째부터 4번째부터의 구간 합을 구해라
    • S[4] - S[0] = 26
  • 합 배열을 미리 구해 두면 구간 합은 한 번의 계산으로 구할 수 있다.

Reference 📚

Do it! 알고리즘 코딩 테스트 참조