안녕하세요! 이번 포스트에서는 코틀린으로 구간 합 구하기 문제를 해결하는 방법에 대해 자세히 알아보도록 하겠습니다.
구간 합 문제는 프로그래밍 대회나 코딩 테스트에서 자주 출제되는 유형이며, 이를 효율적으로 해결하는 방법을 알고 있다면
여러 문제를 빠르게 풀 수 있는 능력을 키울 수 있습니다.
문제 설명
배열이 주어졌을 때, 특정 구간의 합을 구하는 문제입니다. 주어진 배열과 여러 쿼리에 대해
각 구간의 합을 구하는 문제를 해결하는 것입니다. 예를 들어, 배열 A가 다음과 같다고 가정합니다:
A = [10, 20, 30, 40, 50]
이때 사용자가 원하는 구간 (i, j)에서의 합을 구하는 쿼리 쿼리를 받았을 때,
그에 대한 합을 반환해야 합니다.
입력 형식
첫 번째 줄에는 배열의 크기 N과 쿼리의 개수 M이 주어집니다.
그 다음 N개의 정수가 주어져 배열 A를 구성합니다.
다음 M개의 줄에는 각 줄마다 두 개의 정수 i와 j가 주어지고,
이는 구간 A[i]부터 A[j]까지의 합을 구하는 쿼리를 의미합니다.
출력 형식
각 쿼리에 대한 구간의 합을 출력합니다.
예제 입력
5 3
10 20 30 40 50
1 3
2 4
1 5
예제 출력
60
90
150
문제 풀이 접근
이 문제를 해결하기 위해서는 두 가지 방법이 있습니다.
첫 번째는 단순히 매 쿼리에 대해 반복문을 돌면서 합을 구하는 것이고,
두 번째는 구간 합 배열을 활용하는 것입니다.
두 번째 방법이 훨씬 더 효율적이므로 이를 중심으로 설명하겠습니다.
구간 합 배열
구간 합 배열을 이용하면 쿼리 1개당 O(1) 시간복잡도로 구간 합을 구할 수 있습니다.
구간 합 배열을 계산하는 시간이 O(N)이므로,
총 시간복잡도는 O(N + M)입니다.
이는 쿼리의 개수가 많을수록 더 효율적입니다.
구간 합 배열의 정의
구간 합 배열은 주어진 배열의 접두사 합을 저장하는 배열입니다.
즉, 배열 A의 i번째 인덱스까지의 합을 저장하는 배열 S를 정의합니다.
S[i] = A[0] + A[1] + ... + A[i-1]와 같습니다.
구간 합 계산 방법
구간 A[i]부터 A[j]까지의 합은 다음과 같이 구할 수 있습니다:
sum = S[j+1] - S[i]
여기서 S[j+1]는 A[0]부터 A[j]까지의 합이고,
S[i]는 A[0]부터 A[i-1]까지의 합입니다.
따라서 S[j+1]에서 S[i]를 빼면 A[i]부터 A[j]까지의 합이 됩니다.
코드 구현
이제 코틀린을 이용하여 이 문제를 해결하는 코드를 작성해 보겠습니다.
코틀린 코드
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val a = readLine()!!.split(" ").map { it.toInt() }
val s = IntArray(n + 1)
for (i in 1..n) {
s[i] = s[i - 1] + a[i - 1]
}
repeat(m) {
val (i, j) = readLine()!!.split(" ").map { it.toInt() }
println(s[j] - s[i - 1])
}
}
코드 설명
1. 첫 줄에서 N과 M을 입력받습니다.
2. 두 번째 줄에서 배열 A를 입력받습니다.
3. 구간 합 배열 S를 초기화합니다. 크기는 N + 1입니다.
4. 반복문을 통해 구간 합 배열 S를 계산합니다.
5. 쿼리에 대해 반복하며 각 구간의 합을 계산하고 출력합니다.
결론
구간 합 구하기 문제는 다양한 문제에 응용될 수 있는 유용한 기법입니다.
코틀린을 이용하여 구간 합 배열을 사용하면 훨씬 빠르게 문제를 해결할 수 있습니다.
이 강좌를 통해 여러분들이 구간 합 구하기 문제에 대한 이해를 높이고,
코딩 테스트에서 유용하게 활용할 수 있기를 바랍니다.
다음 포스트에서는 구간 합을 확장하여 다른 유형의 문제를 다뤄보도록 하겠습니다.
계속해서 학습을 지속하세요!