[Algorithm/Kotlin] 백준 11659번 구간 합 구하기 4: 누적 합(Prefix Sum)을 활용한 풀이법

문제 설명

주어진 수열에서 특정 구간 [i, j]의 합을 여러 번 구해야 하는 문제입니다. 입력으로 N개의 수와 M개의 구간이 주어집니다. 각 구간에 대해 빠르게 합을 구하는 프로그램을 작성해야 합니다.

 

제한 사항

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N
• 각 숫자는 1,000 이하의 자연수

---

문제 해결 아이디어

1. 기본 접근법 (O(N × M), 시간 초과 가능)
   •    M개의 구간 합을 구하기 위해 for 루프를 사용해 N개의 값을 더하면 O(N × M) 시간이 걸립니다.
   •    N, M이 최대 100,000일 경우 10^10 이상의 연산이 발생하여 비효율적입니다.
2. 누적 합(Prefix Sum) 기법 (O(N + M), 효율적)
   •    먼저 누적 합 배열을 생성하여 O(N) 시간에 각 위치까지의 합을 저장합니다.
   •    이후 각 구간 [i, j]의 합을 O(1) 시간에 구할 수 있습니다.
   •    총 시간 복잡도는 O(N + M)로 최적화됩니다.

단순히 반복문을 사용해 합을 구하면 O(N × M)의 시간 복잡도가 발생하여 시간 초과가 발생합니다. 이를 해결하기 위해 누적 합(Prefix Sum) 개념을 사용합니다.

 

누적 합(Prefix Sum) 방식이란?

누적 합 배열을 사용하면 특정 구간의 합을 빠르게 구할 수 있습니다. 예를 들어, 아래와 같은 수열이 있다고 가정합니다.

nList = [3, 2, 7, 5, 1]

 

이때, 누적 합 배열을 만들면 다음과 같습니다.

prefixSum = [0, 3, 5, 12, 17, 18]

 

각 값의 의미는 다음과 같습니다.

• prefixSum[1] = 3
• prefixSum[2] = 3 + 2 = 5
• prefixSum[3] = 3 + 2 + 7 = 12
• prefixSum[4] = 3 + 2 + 7 + 5 = 17
• prefixSum[5] = 3 + 2 + 7 + 5 + 1 = 18

이제 특정 구간 [i, j]의 합을 구하고 싶다면?

prefixSum[j] - prefixSum[i-1]

 

예를 들어, [2, 4] 구간의 합을 구하면:

prefixSum[4] - prefixSum[1] = 17 - 3 = 14

 

이는 실제 계산 (2 + 7 + 5 = 14)과 동일한 값입니다.

---

구현 코드

시간 초과 발생 (반복문 이용)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (_, m) = br.readLine().split(" ").map { it.toInt() }
    val nList = br.readLine().split(" ").map { it.toInt() }
    val mList = Array(m) { br.readLine().split(" ").map { it.toInt() } }

    for (item in mList) {
        var sum = 0
        for (i in item[0] - 1 until item[1]) {
            sum += nList[i]
        }
        bw.write("$sum\n")
    }

    bw.flush()
    bw.close()
}

• 각 구간 [i, j]에 대해 for 루프로 직접 합을 구하면 최악의 경우 O(N × M) 연산이 발생하여 시간 초과가 발생합니다.

누적 합(Prefix Sum) 적용 (O(N + M), 최적화)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (_, m) = br.readLine().split(" ").map { it.toInt() }
    val nList = br.readLine().split(" ").map { it.toInt() }

    val prefixSum = IntArray(nList.size + 1) { 0 }
    for (i in nList.indices) {
        prefixSum[i + 1] = prefixSum[i] + nList[i]
    }

    repeat(m) {
        val (l, r) = br.readLine().split(" ").map { it.toInt() }
        bw.write("${prefixSum[r] - prefixSum[l - 1]}\n")
    }

    bw.flush()
    bw.close()
}

• 누적 합 배열(prefixSum)을 미리 계산하여 O(N) 시간에 생성합니다.
• 각 구간 합 [i, j]는 prefixSum[j] - prefixSum[i-1]로 O(1) 시간에 구할 수 있습니다.
• 총 시간 복잡도: O(N + M) (빠르게 처리 가능!)

---

 

시간 복잡도 분석

1. 누적 합 배열 생성 → O(N)
2. 각 쿼리 처리 → O(M) (각 쿼리당 O(1) 연산)
3. 전체 시간 복잡도 → O(N + M)

단순히 반복문을 사용한 방식(O(N × M))보다 압도적으로 빠름!

---

결론

• 단순한 for 루프 방식은 O(N × M)으로 비효율적이며 시간 초과가 발생할 가능성이 큽니다.
• 누적 합(Prefix Sum) 을 사용하면 O(N + M) 으로 최적화할 수 있으며, 대량 데이터에도 빠르게 동작합니다.

---

문제링크: https://www.acmicpc.net/problem/11659