[Algorithm] 구간 합

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

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의 합니다.

S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + .... + A[ i-1 ] + A[ i ]

합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) -> O(1) 로 감소합니다.

A[i] 부터 A[j] 까지의 배열 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 -> O(N)입니다.
이런 경우 합 배열을 사용하면 O(1)안에 답을 구할 수 있습니다.

합 배열 S를 만드는 공식 ⭐️

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

이렇게 구현된 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있습니다. i ~ j 까지 구간 합을 구하는 공식은 다음과 같습니다.

구간 합을 구하는 공식 ⭐️

S[ j ] - S[ i-1 ]

다음 그림은 배열 A의 A[2]부터 A[5] 까지의 구간 합을 합 배열을 통해 구하는 과정을 보여줍니다.

A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정

S[ 5 ] = A[ 0 ] + A[ 1 ] + ... + A[ 5 ]
S[ 1 ] = A[ 0 ] + A[ 1 ]
-> S[ 5 ] - S [ 1 ] = A[ 2 ] + A[ 3 ] + A[ 4 ] + A[ 5 ]

---

구간 합 구하기 문제⏱️

시간제한 0.5초 / 백준 온라인 저지 11659번

문제 분석

문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100,000 번 입니다.
그리고 0.5초안에 모든 구간 합 계산을 끝내야 합니다. 이럴 때 바로 구간 합을 이용해야 합니다.

코드 구현

public static void main(String[] args) throws IOException {
public static void main(String[] args) throws IOException {

    //표준 입력 데이터를 읽기 위한 클래스
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    // bufferReader.readLine -> 한 줄을 불러온다.
    // StringTokenizer 는 문자열을 특정 구분자로 쪼개어 토큰화 해주는 클래스
    // 첫 번째 줄에서 suNo quizNo 입력 받기 5,3
    StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
    int suNo = Integer.parseInt(st.nextToken());
    int quizNo = Integer.parseInt(st.nextToken());

    // 배열 S 초기화
    long[] S = new long[suNo + 1];
    st = new StringTokenizer(bufferedReader.readLine());
    for(int i = 1; i <= suNo; i++){
      S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
    }

    // 세번째 네번째 결과 출력
    for(int q = 0; q < quizNo; q++){
      st = new StringTokenizer(bufferedReader.readLine());
      int i = Integer.parseInt(st.nextToken());
      int j = Integer.parseInt(st.nextToken());
      System.out.println(S[j] - S[i - 1]);
    }

  }