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

코딩 테스트에서 다루어지는 여러 알고리즘 중에서 ‘구간 합’ 문제는 빈번하게 출제됩니다.
이 포스트에서는 구간 합 구하기 2라는 주제로 문제를 풀어보도록 하겠습니다.
특히 코틀린 프로그래밍 언어를 활용하여 작성할 예정입니다.

문제 설명

여러 개의 정수가 주어질 때, 특정 구간의 합을 효율적으로 계산하는 방법을 제시하는 문제입니다.
다음은 문제의 정의입니다:

정수 N과 M이 주어질 때, 
N개의 정수가 주어지며, 
M개의 질의가 주어질 것입니다. 
각 질의는 두 정수 i와 j로 구성되어 있으며, 
i와 j사이의 정수 합을 계산해야 합니다.

입력 형식:
- 첫 번째 줄에 N(1 ≤ N ≤ 100,000)과 M(1 ≤ M ≤ 100,000) 이 주어진다.
- 두 번째 줄에 N개의 정수가 주어진다. 각 정수는 1,000,000을 넘지 않는다.
- 이어지는 M개의 줄에 걸쳐 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

출력 형식:
- 각 질의에 대해, i번째 수부터 j번째 수까지의 합을 출력합니다.

문제 해결 과정

이 문제를 해결하기 위해서는 효율적인 알고리즘이 필요합니다. 단순히 각 질의에 대해 루프를 돌며 합을 계산하는 것은 O(N*M)의 시간 복잡도를 가지게 되어, 입력값이 큰 경우에는 시간 초과로 실패할 수 있습니다.

1. 누적 합 배열 사용하기

체크하는 관점에서 모든 합을 매번 계산하는 대신, 누적 합 배열을 사용하는 방법이 있습니다. 누적 합 배열을 활용하면, 특정 구간의 합을 O(1)의 시간 복잡도로 구할 수 있습니다.

누적 합 배열 prefixSum를 정의하면, prefixSum[k]는 배열의 처음부터 k번째 수까지의 합을 나타냅니다.
따라서 다음과 같은 관계를 가집니다:

prefixSum[k] = prefixSum[k-1] + array[k-1] (1 ≤ k ≤ N)

이때, 특정 구간의 합은 다음과 같이 구할 수 있습니다:

sum(i, j) = prefixSum[j] - prefixSum[i-1]

2. 알고리즘 구현하기

이제 이러한 아이디어를 토대로 코드를 구현해 보겠습니다.
다음의 코드는 코틀린을 사용하여 문제를 풀이하는 예제입니다:


fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val numbers = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val prefixSum = LongArray(n + 1)

    for (i in 1..n) {
        prefixSum[i] = prefixSum[i - 1] + numbers[i - 1].toLong()
    }

    for (j in 0 until m) {
        val (i, j) = readLine()!!.split(" ").map { it.toInt() }
        println(prefixSum[j] - prefixSum[i - 1])
    }
}

3. 코드 설명

위 코드를 통해 어떤 방식으로 구간 합을 구하는지 설명하겠습니다:

  • val (n, m) = readLine()!!.split(" ").map { it.toInt() }:
    첫 번째 줄에서 N과 M을 입력받습니다.
  • val numbers = readLine()!!.split(" ").map { it.toInt() }.toIntArray():
    두 번째 줄에서 N개의 정수를 입력받고 배열로 변환합니다.
  • val prefixSum = LongArray(n + 1):
    누적 합을 저장할 배열을 생성합니다. (0번째 인덱스는 0으로 초기화)
  • for (i in 1..n):
    반복문을 사용하여 누적 합을 계산합니다. prefixSum[i]에 i번째 수까지의 합을 저장합니다.
  • for (j in 0 until m):
    각 질의에 대해 입력을 받아 구간 합을 계산합니다.
  • println(prefixSum[j] - prefixSum[i - 1]):
    i번째 인덱스부터 j번째 인덱스까지의 합을 출력합니다.

복잡도 분석

위 코드의 시간 복잡도는 다음과 같습니다:

  • 누적 합 배열을 생성하는 과정: O(N)
  • M개의 질의에 대해 각각 O(1)로 구간 합을 구하는 과정: O(M)

따라서 전체 시간 복잡도는 O(N + M)입니다. 이는 주어진 문제의 구간 합을 효과적으로 처리할 수 있는 좋은 방법입니다.

결론

이번 강좌에서는 구간 합 구하기 2라는 문제를 통해 누적 합을 사용하여 효율적으로 문제를 풀어보았습니다.
이와 같은 방식은 많은 알고리즘 문제에서 유용하게 활용될 수 있으니, 다양한 문제에 적용해 보시기 바랍니다.

우리는 여러 개의 정수로 이루어진 배열에서 특정 구간의 합을 빠르고 효율적으로 계산하는 문제를 다루었습니다.
코틀린의 배열, 리스트와 같은 자료구조를 이용하여 다양한 알고리즘 문제를 해결할 수 있다는 것을 알 수 있었습니다.

추가 연습 문제

아래의 문제들을 추가로 연습해보시기 바랍니다:

  • 다양한 질의 형태에서의 구간 최소값, 최대값 구하기
  • 이상한 구간 합 구하기: 특정 조건을 만족하는 구간만 합산하기
  • 다차원 배열의 구간 합 구하기

이 포스트가 여러분의 코딩 테스트 준비에 도움이 되길 바랍니다.
감사합니다!