[알고리즘] 누적합(prefix sum) 이론 및 예제 (코틀린)

알고리즘 첫 번째, 누적합의 이론을 공부하고 예제들을 풀어보려고 한다.

 

누적 합 : 일정 구간의 누적 합을 구하는 문제이다.

일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간 복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(N)으로 해결 할 수 있다.

누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있다.

예를 들어, 크기가 5인 arr배열에서 3번 index와 5번 index 구간의 구간합을 구한다고 가정하면, 누적합은 arr[0~b]까지의 누적합 - arr[0~a-1까지의 누적합]으로 표현 할 수 있다.

b - a 구간의 누적합을 구하기 위해선 b구간까지의 합에서 a-1구간까지의 합을 빼주면 된다.

 

[3,5] 구간의 누적합은?

 

크기가 5인 배열 선언(인덱스 1 ~ 5)

 

인덱스	1	2	3	4	5
값	7	6	3	2	1

 

각 인덱스값에 누적합 저장

인덱스	1	2	3	4	5
배열	7	6	3	2	1
누적합	7	13	16	18	19

 

3번 구간과 5번 구간 사이의 누적합을 구하려면 겹치는 1,2구간을 제외해줘야한다.

즉, 2번 인덱스의 누적합을 빼줘야 한다.

 

l번재 수부터 r번째 수까지 합은 S[ r ] - S[ l - 1 ]과 같다.

• S[ r ] = A[ 1 ] + ... + A[ r ]
• S[ l - 1] = A[ 1 ] + ... + A[ l - 1 ]

따라서 S[ r ] - S[ l - 1 ] = A[ l ] + ... + A[r]이 된다.

예제)

https://www.acmicpc.net/problem/2559

2559번: 수열

N개의 온도 중, 연속적인 M개의 합이 가장 큰 경우의 합을 출력하면 되는 문제이다.

 

S[ n ] - S[ n - m ]

 

풀이

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (size, order) = br.readLine().split(" ").map { it.toInt() }
    val array = IntArray(size + 1)
    val sum = IntArray(size + 1)        //이전 인덱스의 값에 값을 더해서 넣어야하기에 + 1

    with(StringTokenizer(br.readLine())) {
        repeat(size) {
            array[it + 1] = nextToken().toInt()     //각 온도
            sum[it + 1] = sum[it] + array[it + 1]   //온도들의 합
        }
    }

    var max = Int.MIN_VALUE     //음수일 수도 있기에 MIN_VALUE로 처리
    for(i in order .. size) {
        max = max.coerceAtLeast(sum[i] - sum[i - order])
    }


    bw.write("$max")
    bw.flush()
    bw.close()
}

 

누적합을 활용한 기본 문제이다.

 

다른 예제

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

https://www.acmicpc.net/problem/17425

17425번: 약수의 합

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

참고

https://jow1025.tistory.com/47

누적합(prefix sum)

https://book.acmicpc.net/algorithm/prefix-sum

누적 합