SubTotal 부분합 = 전체합 - (부분-1)

어떤 배열이 주어졌을 때, 

 

int[ ]  array = { 5, 4, 3, 2, 1 }; 

 

이 배열에서 2번째 수 부터 4번째 수까지의 합을 구하자면 

4 + 3 +2 = 9  가 된다. 

 

이게 말그대로 부분합이다. 

 

i 번째 부터 j 번째 까지 부분합을 구하라고 하면 

어떻게 구할까 

 

 

1. 반복문

 

간단하게 반복문을 사용하면 구해지긴 한다. 

 

int sum = 0;
for (int a = i - 1; a < j; a++) {

    sum += array[a];
}

 

근데 이게 배열이 5개짜리가 아니라 십만개짜리라고 생각해보자. 

7만번째부터 8만번째까지 더해라. 

 

반복문이 돌때마다  

array배열에서 7만번째 값~8만번째 값을 "조회" 해야 한다.  

배열은 조회할 때, 0번째부터 쭉 올라가서 7만번째까지 도착하는 식으로 조회하는

Linear search 방식이기 때문에, 

이렇게 조회할 데이터가 많아질 수록, 걸리는 시간도 비례해 늘어나게 된다.  

 

 

2. Map

이걸 Map 처럼 key : value 값으로 묶어서 걸어두면

시간복잡도는 아무리 데이터가 들어나도 0(1) 로 동일하다.  

Map을 사용하면 데이터를 조회하는데 드는 시간은 줄일 수 있다.  

 

 

하지만 결국엔 7만번째부터 8만번째까지 값을 

(빠르긴하지만) 조회하며 더해야 하기 때문에 시간초과가 난다. 

 

 

그럼 어떻게 할까 

 

3. 부분합 알고리즘 

 

조회를 10000번이나 하지 않게끔 하는 방법

 

위의 1, 2 번 방법은 먼저  

배열이든, map이든 거기에 데이터를 집어넣는 과정은 당연히 필수적으로 있었다.

 

부분합을 구하는게 목적이라면

이 집어넣는 과정에서, 각 데이터를 하나하나 넣는게 아니라 

첫번째 데이터부터해서 더해가면서 그 값을 넣어둔다면, 

 

즉 5 4 3 2 1 을 넣는게 아니라 

 

5 9 12 14 15 

 

이렇게 전 항을 더해가면서 전체합을 넣어둔다면 

 

3번째 숫자까지 더한값을 주세요 => 3번째 값만 조회해서 주면 되고

( 조회 3번 VS 조회 1번 ) 

 

3번째 숫자부터 5번째 숫자까지 더한값을 주세요 

A  : 5번째 숫자까지 더한값에서, 

B  : 2번째 숫자까지 더한값을 빼면 

 

A  : { 5 4 3 2 1 }  - 

B  : { 5 4 }     

= { 3 2 1 } 

3번째부터 5번째 숫자까지 더한 값이 나온다. 

 

이게 30000번째 숫자부터 50000번째 숫자까지 더한값 주세요 라고 한다면 

조회수는 

20001 번  VS  2번 

차이가 나게 되는 것이다. 

 

int[] arr = new int[n + 1];

        StringTokenizer tk2 = new StringTokenizer(br.readLine());
        for (int a = 1; a <= n; a++) {
            arr[a] = arr[a - 1] + Integer.parseInt(tk2.nextToken());
        }

        for (int b = 0; b < m; b++) {
            StringTokenizer tk3 = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(tk3.nextToken());
            int j = Integer.parseInt(tk3.nextToken());

            sb.append((arr[j] - arr[i - 1])+"\n");
        }

        System.out.println(sb);
    }
}

=> j번째 값에서  i 보다 "한번 전에 값" ( i -1 ) 을 빼야,  i 번째부터 j 번째까지의 합이다. 

 

 

" 매장에서 올해 매출 데이터가 쭉 있는데 

여기서 2~9월까지 매출만 더해라 " 

 

부분합을 구해야 하는 경우는 단순히 테스트 용도가 아니라

현실에서도 많이 사용될 것 같다. 

 

 

어짜피 데이터를 받아와서 배열에 넣고 조회를 하며 계산해야 하는 상황이라면 

배열에 넣을 때, 누적 합으로 넣고 

그걸 이용해 부분합을 계산하는 방법을 사용해야 겠다.