코틀린 코딩테스트 강좌, 구간 합

1. 서론

안녕하세요. 이번 시간에는 코틀린으로 구간 합을 효율적으로 구하는 방법에 대해 알아보겠습니다.
코딩테스트에서 자주 등장하는 문제 중 하나로, 주어진 수열의 특정 구간에 대한 합을 구하는 문제입니다.
이 과정을 통해 구간 합을 해결하기 위한 다양한 방법과 그에 따른 시간 복잡도에 대해 논의하도록 하겠습니다.

2. 문제 설명

주어진 수열 A와 쿼리 Q가 있을 때, 각 쿼리는 두 정수 L과 R로 주어집니다.
우리는 L부터 R까지의 합을 빠르게 구해야 합니다.

입력

첫 번째 줄에는 수열의 크기 N과 쿼리의 개수 M이 주어집니다.
두 번째 줄에는 N개의 정수가 주어져 수열 A를 이룹니다.
다음 M개의 줄마다 L과 R이 주어집니다.

출력

각 쿼리에 대한 결과를 한 줄에 하나씩 출력합니다.

제한

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
-1,000,000,000 ≤ A[i] ≤ 1,000,000,000

3. 접근 방법

구간 합을 구하는 여러 가지 방법이 있지만, 기본적인 접근 방법은 다음 두 가지입니다.

3.1. 단순 반복

가장 직관적인 방법은, 각 쿼리에 대해 정의된 범위에서 직접 합을 계산하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(N)이고, 최대 쿼리가 100,000개일 경우 최악의 경우 O(N * M) = O(10^10)로 매우 비효율적입니다.

3.2. 누적 합 배열(Cumulative Sum Array)

아래의 방법론을 사용하여 효율적으로 구간 합을 계산할 수 있습니다.

누적 합 배열은 특정 위치까지의 합을 미리 계산해 두는 배열로, 선형 시간 O(N)으로 배열을 만듭니다.
이렇게 하면 각 쿼리를 O(1)로 처리할 수 있게 됩니다. 따라서 전체 시간 복잡도는 O(N + M)입니다.

4. 구현

누적 합 배열을 사용한 구간 합 계산 알고리즘을 코틀린으로 구현해 보겠습니다.


fun main() {
    val reader = System.`in`.bufferedReader()
    val (n, m) = reader.readLine().split(" ").map { it.toInt() }

    val array = reader.readLine().split(" ").map { it.toInt() }.toIntArray()
    val sumArray = IntArray(n + 1)

    // 누적 합 배열 생성
    for (i in 1..n) {
        sumArray[i] = sumArray[i - 1] + array[i - 1]
    }

    val result = StringBuilder()
    // 쿼리 처리
    repeat(m) {
        val (l, r) = reader.readLine().split(" ").map { it.toInt() }
        val sum = sumArray[r] - sumArray[l - 1]
        result.append(sum).append("\n")
    }

    println(result)
}

위의 구현에서 핵심은 sumArray를 통해 각 쿼리를 O(1)로 처리할 수 있다는 점입니다.
구간 [L, R]의 합은 sumArray[R] - sumArray[L-1]로 쉽게 구할 수 있습니다.

5. 시간 복잡도 분석

이 알고리즘의 시간 복잡도를 분석해보면 다음과 같습니다.

누적 합 배열을 만드는 과정: O(N)
쿼리 처리: O(M)
총 시간 복잡도: O(N + M)

따라서 주어진 제약 조건 하에서 우리는 효율적으로 구간 합을 계산할 수 있게 됩니다.

6. 예제

6.1. 입력 예시

6.2. 출력 예시


6
14
15

위 예제에서 입력으로 주어진 쿼리의 결과는 1부터 3까지의 합은 6, 2부터 5까지의 합은 14,
전체 1부터 5까지의 합은 15로 계산됩니다.

7. 결론

이번 강좌에서는 구간 합을 계산하는 다양한 방법과 그에 따른 정확한 구현을 살펴보았습니다.
특히, 누적 합 배열을 사용하여 효율적으로 구간 합을 계산하는 방법에 대해 깊이 있게 논의했습니다.
이 알고리즘은 많은 코딩 테스트 문제와 실무에서 유용하게 사용될 수 있습니다. 다음 시간에는 더 복잡한 데이터 구조와 알고리즘에 대해 알아보도록 하겠습니다.