구간 합

구간합은 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 코딩테스트에 출제되는 빈도가 높다고 하여 한 번 정리하고 가겠습니다.

구간 알고리즘의 핵심은 배열을 초기화하면서 합 배열을 구하는 것입니다. 이렇게 실제로 합을 구하기 전에 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 대폭 감소합니다.

예를들어, 위와 같이 배열A에서 구간의 합을 구해야 할 때, 합 배열을 구해놓으면, 실질적으로 합 계산을 수행할 때, 시간을 단축시킬 수 있습니다. 

[합 배열 안 구한 경우]

(최악) O(N) -> idx 0 ~ 5까지의 합을 구하시오

 for(int i=0; i<A.length;i++){

    sum += i;

}

위와 같이 A의 배열의 길이만큼 총 N번의 연산을 수행합니다.

 

[합 배열을 구한 경우] 

(최악) O(1) -> idx 0 ~ 5까지의 합을 구하시오

S[5] - S[0]

단 한번의 연산으로 합을 구할 수 있습니다.

 

[합 배열을 구하는 공식] 

(0부터 n까지의 합) = (0부터 n-1까지의 합) + n에서의 값 

S[n] = S[n-1] + A[n]

[구간 합을 구하는 공식] n에서 m까지의 구간 합

(0부터 m까지의 합) - (0부터 n-1까지의 합)

S[m] - S[n-1]

공식을 보기 편하게 도식화하면 다음과 같습니다.

 

그렇다면 한 단계 업그레이드 해서 1차원이 아니라 2차원 배열을 보겠습니다. 다음의 그림을 보면서 공식을 설명하겠습니다. 기본적으로 다음과 같은 가정하에 합 배열을 구하겠습니다. 

D[X][Y] = 원본배열의 (0,0)부터 (x,y)까지의 사각형 영역 안에 있는 수의 합

아래 그림에는 인덱스로 적어두었지만, 실제로 필자가 배열을 만들때는 원본 배열의 크기보다 +1해서 만들것입니다. 

그러면 0행 0열은 모두 기본값인 0으로 초기화 될 것이고. 뒤에 나올 공식을 이해하는데 도움이 될 것입니다.

원본배열

위의 원본 배열에 대한 합배열을 먼저 1행과 1열에 대해서만 다음과 같이 구합니다. 주석과 이미지를 보시면 이해할 수 있습니다.

 

여기서는 조금 헷갈릴수 있으니 집중해주세요. 그렇다면 2행 2열은 어떻게 구할 수 있을까요?

위의 가정에 의하면, D[2][2]는 (0,0)부터 (2,2)까지의 사각형안에 있는 수의 합을 구하는 것이라고 했습니다. 즉 1 + 2 + 2 + A[2][2]를 계산해주면 되는데 다음과 같은 식으로 계산할 수 있습니다.

구간 합을 구하여 값을 채우는 위의 공식을 일반화 하면 다음과 같습니다. 

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

위의 공식으로 구간 합 배열을 완성하면 다음과 같습니다. 

구간 합 배열

 

마지막으로 (2,2)에서 (3,4)까지의 구간 합을 구하는 공식을 확인하고 마무리 하겠습니다.

(3,4)구간 합에서 (1,4) 구간 합과 (3,1)구간합을 빼 다음 중복하여 뺀 (1,1)구간 합을 더하면 됩니다. 

(X1, Y1)에서 (X2, Y2)까지의 구간 합을 구하는 공식을 일반화하면 다음과 같습니다.

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]

D[1][1]은 어떻게 구할까?

위에서 정리한 식대로 보면 D[1][1] = D[0][1] + D[1][0] - D[0][0] + A[1][1]입니다. 

이는 0 + 0 - 0 + A[1][1]입니다. 위에서 이차원 배열을 설명하기 전에 잠깐 언급했지만, 원본배열보다 행과열을 +1하고 (1,1)부터 값을 채워나가면, 초기화 하지 않은 0행과 0열은 자동으로 기본값인 0으로 초기화됩니다. 따라서 일반화된 식을 위처럼 만족하여 오류가 없습니다. 

 

[정리]

1차원 배열

1. 합배열 : S[n] = S[n-1] + A[n]
2. 구간합 : S[m] - S[n-1]

2차원배열

1. 합배열 : D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
2. 구간합 : D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]