[Algorithm]구간합 구하기

코딩 테스트 연습을 하다보면 많이 접하게 되는 문제가 일정 구간의 합을 구하는 것이다.

 

단순히 반복문을 통해 합을 구하는 방법도 있겠지만, 그렇게 되면 시간 복잡도 면에서 제한에 걸리게 되는 경우가 많다.

 

이럴 때 구간합 배열을 생성하여 해결할 수 있다.

 

1) 1차원배열

일반 배열이 [5, 4, 3, 2, 1] 이라면

구간합 배열은 [5, 9, 12, 14, 15] 로 나타낼 수 있고

이를 코드로 표현하면..

------------------------------------------------------------------

for(숫자 개수만큼 반복) {

   sum[i] = sum[i-1] + arr[i]

}

------------------------------------------------------------------

생성된 합배열을 활용하여, 구간의 합을 구한다.

구하려는 구간의 시작과 끝을 값(i, j)으로 받아

------------------------------------------------------------------

sum[j] - sum[i-1] 로 구간합을 출력한다.

------------------------------------------------------------------

 

2) 2차원배열

2차원 배열의 경우 합배열을 생성할때 기본 배열생성 후.. (x, y 인덱스 1부터시작, 0번 배열은 0으로 초기화됨)

위와 같은 로직을 통해 합배열을 생성해줄 수 있다. 그리고 구간합을 구할 인덱스(x1,y1,x2,y2)를 입력해주면..

위의 로직을 통해 합을 구할 수 있다. 즉 합계산 구간을 제외한 합계지점을 빼준 후, 중복으로 빠진 지점([xy-1[y1-1]) 지점을 더하는 방식으로 값을 구할 수 있다.