구간 합 알고리즘 동작 방법, 정의

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

 구간 합 알고리즘

  구간 합 문제 : 연속적으로 나열된 n개의 수가 있을 때 '특정 구간의 모든 수를 합한 값을 계산'하는 문제
 예를 들어 5개의 데이터로 구성된 수열 {10,20,30,40,50}이 있다고 가정한다.
  - 두 번째 수부터 네번 째 수까지의 합은 20+30+40 = 90 임.

 

 구간 합 빠르게 계산하기.
  n개의 정수로 구성된 수열이 있다.
  m개의 쿼리 정보가 주어진다.
   - 각 쿼리는 Left와 Right로 구성된다.
   - 각 쿼리에 대해 [Left, Right] 구간에 포함된 데이터들의 합을 출력해야 함.
  수행 시간 제한은 O(N+M)이다.

 
 ▶문제 해결 아이디어
 접두사 합 : 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓음.
 접두사 합을 활용한 알고리즘은 다음과 같음.
  -N개의 수 위치 각각에 대해 접두사 합을 계산하여 P에 저장함.
  -매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P{Left-1] 입니다.
 
    [10 , 20 , 30 , 40, 50]                  1) left = 1, right=3 => p[3]-p[0]= 60
        ↓prefix Sum                           2) left = 2, right=5 => p[5]-p[1]= 140
 [ 0 , 10 , 30 , 60 , 100 , 150]        M) left = 3, right=4 => p[4]-p[2]= 70
 p[0] p[1] p[2] p[3] p[4] p[5] 

 

=> 내가 생각한 이해하기,

p[3] ~ p[5] = ( p[0] ~ [5] ) - ( p[0] ~ [2] ) 와 같다고 생각하면 편하다.

 

---