안녕하세요! 오늘은 코틀린을 이용한 코딩테스트 문제 중 “구간 합 구하기 3″에 대해 다뤄보겠습니다. 이 문제는 주어진 배열의 특정 구간에 대한 합을 효율적으로 계산해야 하는 문제입니다. 특히, 반복적으로 구간 합을 계산해야 할 때, 이러한 효율적인 알고리즘이 매우 중요합니다.
문제 설명
여러분에게 N개의 정수로 이루어진 배열 A와 Q개의 쿼리가 주어집니다. 각 쿼리는 두 개의 정수 L과 R을 포함하고 있으며, 이는 배열 A의 L번째 인덱스부터 R번째 인덱스까지의 합을 계산하는 것입니다. 단, 배열은 1번 인덱스부터 시작합니다. 여러분은 모든 Q개의 쿼리에 대해 결과를 출력해야 합니다.
입력 형식
첫 번째 줄: N (1 ≤ N ≤ 100,000)
두 번째 줄: N개의 정수 (각각의 정수는 -10,000,000 ≤ A[i] ≤ 10,000,000)
세 번째 줄: Q (1 ≤ Q ≤ 100,000)
이후 Q개의 줄에는 각 쿼리가 L R의 형태로 주어짐.
출력 형식
Q개의 각 줄에 대해 구간 합을 출력합니다.
접근 방법
기본적인 방법은 주어진 L과 R에 대해 직접적으로 배열을 순회하며 합을 계산하는 것입니다. 그러나 이는 시간 복잡도가 O(Q * N)으로, Q와 N이 최대 100,000일 때 최악의 경우 10억 번의 연산이 이루어질 수 있습니다. 그러므로 이것은 비효율적입니다. 이 문제는 전처리를 통해 O(1)의 시간 복잡도로 쿼리를 처리하는 방법이 필요합니다.
구간 합 구하기 문제를 해결하기 위한 효율적인 방법 중 하나는 누적 합 배열을 사용하는 것입니다. 누적 합 배열을 사용하면 특정 구간 L ~ R의 합을 쉽게 계산할 수 있습니다.
누적 합 배열
누적 합 배열 P를 정의합니다. P[i]는 배열 A의 첫 번째 원소부터 i번째 원소까지의 합을 저장합니다.
P[i] = A[1] + A[2] + ... + A[i]
그러면 구간 L ~ R에 대한 합은 다음과 같이 계산할 수 있습니다:
sum(L, R) = P[R] - P[L - 1]
이 방법은 O(N)으로 누적 합 배열을 구할 수 있고, 이후 각 쿼리에 대해 O(1)로 결과를 얻을 수 있습니다. 전체 시간 복잡도는 O(N + Q)가 됩니다.
코드 구현
코틀린 코드
fun main() {
val reader = System.`in`.bufferedReader()
val n = reader.readLine().toInt()
val a = reader.readLine().split(" ").map { it.toInt() }
val q = reader.readLine().toInt()
// 누적 합 배열 초기화
val p = LongArray(n + 1)
// 누적 합 계산
for (i in 1..n) {
p[i] = p[i - 1] + a[i - 1]
}
val result = StringBuilder()
for (i in 0 until q) {
val (l, r) = reader.readLine().split(" ").map { it.toInt() }
// 구간 합 계산
result.append(p[r] - p[l - 1]).append("\n")
}
// 결과 출력
println(result.toString())
}
코드 설명
위의 코드는 코틀린으로 작성된 “구간 합 구하기 3” 문제의 해결 방법입니다. 각각의 부분을 설명하겠습니다.
1. 입력 처리
먼저 N, A, Q 값을 입력받습니다. N은 배열의 크기를 의미하고, A는 정수 배열, Q는 주어진 쿼리의 수를 의미합니다.
2. 누적 합 배열 생성
누적 합 배열 P를 생성합니다. P[0]는 0으로 초기화되고, P[1]부터 P[n]까지 누적 합을 계산합니다. 이는 배열 A의 각 원소를 더한 결과를 저장하게 됩니다.
3. 쿼리 처리
각 쿼리에 대해 L과 R 값을 입력받아, 누적 합 배열을 이용하여 O(1) 시간 내에 구간 합을 계산합니다. 이 결과는 StringBuilder에 추가되어 마지막에 출력됩니다.
결론
“구간 합 구하기 3” 문제를 통해 누적 합 배열 활용의 중요성을 배웠습니다. 이 기법을 이용하면 대량의 데이터에서도 효율적으로 쿼리를 처리할 수 있다는 것을 알게 되었습니다. 알고리즘 문제를 풀 때는 항상 시간 복잡도를 고려하여 최적의 방법을 찾아야 합니다. 여러분의 코딩테스트 준비에 도움이 되길 바랍니다.
더 알아보기
다음 강좌에서는 더 다양한 알고리즘 문제를 다뤄보겠습니다. 계속해서 코팅 테스트를 준비하시고 많은 연습 하시길 바랍니다. 감사합니다!