이번 강좌에서는 스위프트를 사용하여 구간 합 문제를 해결하는 방법에 대해 알아보겠습니다.
문제 설명
다음과 같은 문제를 고려해 보겠습니다.
정수 N개로 이루어진 배열 A와, M개의 질의가 주어진다. 각 질의는 두 정수 i, j로 주어지며, A[i]부터 A[j]까지의 합을 구하라.
배열의 크기 N과 질의의 개수 M은 다음과 같다:
- 1 ≤ N, M ≤ 100,000
- -10,000 ≤ A[i] ≤ 10,000
- 1 ≤ i ≤ j ≤ N
입력 예제
입력 형식은 다음과 같다:
5 3
1 2 3 4 5
1 3
2 4
1 5
위의 입력에서 첫 번째 줄은 배열의 크기 N과 질의의 개수 M을 의미합니다. 두 번째 줄은 배열 A의 요소들입니다. 그 이후의 M줄은 각 질의를 나타냅니다.
출력 예제
입력의 각 질의에 대해 합을 출력해야 합니다.
6
9
15
문제 풀이 방법
이 문제를 해결하기 위한 효율적인 방법은 누적 합을 사용하는 것입니다. 즉, 배열 A의 누적 합을 미리 계산해 놓으면 각 질의의 합을 상수 시간에 구할 수 있습니다.
1단계: 누적 합 계산
누적 합 배열 prefixSum을 생성하여, prefixSum[i]는 배열 A의 첫 번째 요소부터 i번째 요소까지의 합을 저장합니다.
let N = 5
let A = [1, 2, 3, 4, 5]
var prefixSum = [Int](repeating: 0, count: N + 1)
for i in 1...N {
prefixSum[i] = prefixSum[i - 1] + A[i - 1]
}
2단계: 질의 처리
질의를 처리할 때는 prefixSum[j] - prefixSum[i - 1]를 사용하여 i부터 j까지의 합을 구합니다. 이를 통해 각 질의의 시간 복잡도는 O(1)이 됩니다.
let queries = [(1, 3), (2, 4), (1, 5)]
for query in queries {
let i = query.0
let j = query.1
let result = prefixSum[j] - prefixSum[i - 1]
print(result)
}
전체 코드
위의 설명을 종합하여 전체 코드는 다음과 같습니다.
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let N = firstLine[0] // 배열의 크기
let M = firstLine[1] // 질의의 개수
let A = readLine()!.split(separator: " ").map { Int($0)! }
var prefixSum = [Int](repeating: 0, count: N + 1)
for i in 1...N {
prefixSum[i] = prefixSum[i - 1] + A[i - 1]
}
for _ in 0..
시간 복잡도
이 알고리즘의 시간 복잡도는 O(N + M)입니다. N은 배열 A의 크기이고, M은 질의의 개수입니다. A의 요소를 모두 더하는 O(N)과 M개의 질의를 처리하는 O(M)이 합쳐졌기 때문입니다.
결론
이번 강좌에서는 구간 합 문제를 해결하기 위해 누적 합을 활용하는 방법을 배웠습니다. 이 방법을 통해 성능을 크게 개선할 수 있습니다. 앞으로 유사한 문제를 해결할 때 이 기법을 활용하시기 바랍니다.