문제 설명
주어지는 정수 배열 arr와 쿼리 배열 queries가 있다. arr의 각 쿼리는
두 개의 인덱스로 이루어져 있으며, 이 인덱스를 통해 arr의 부분 배열의 합을 구해야 한다.
각 쿼리는 (시작 인덱스, 끝 인덱스) 형태로 제공되며, 부분 배열의 합을 빠르게 계산할 수 있는 방법을
구현해야 한다.
입력
- 정수 배열
arr: 길이는 N (1 ≤ N ≤ 100,000) - 정수 배열
queries: 길이는 M (1 ≤ M ≤ 100,000), 각 원소는 (x, y) 형태로 주어짐
출력
queries의 각 쿼리에 대한 부분 배열의 합을 배열로 반환
예제
입력
arr = [1, 2, 3, 4, 5]
queries = [(0, 2), (1, 3), (2, 4)]
출력
[6, 9, 12]
설명
– 첫 번째 쿼리 (0, 2): arr[0] + arr[1] + arr[2] = 1 + 2 + 3 = 6
– 두 번째 쿼리 (1, 3): arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9
– 세 번째 쿼리 (2, 4): arr[2] + arr[3] + arr[4] = 3 + 4 + 5 = 12
문제 해결 과정
문제를 해결하기 위해 먼저 배열의 부분 합을 효율적으로 구할 수 있는 방법을 고민해야 합니다.
각 쿼리가 O(N) 시간에 처리된다면 전체 쿼리를 처리하는 데 O(N * M) 시간이 소요되어 매우 비효율적입니다.
따라서 부분 합을 미리 계산해 두고 사용하는 방법을 고려해야 합니다.
1. 부분 합 배열 만들기
부분 합 배열 prefixSum을 만들어보겠습니다. prefixSum[i]는 arr[0] + arr[1] + ... + arr[i]를 의미합니다.
이를 통해, 주어진 쿼리의 시작 인덱스와 끝 인덱스를 이용하여 간단히 부분 합을 계산할 수 있습니다.
func createPrefixSum(arr: [Int]) -> [Int] {
var prefixSum = [Int](repeating: 0, count: arr.count)
prefixSum[0] = arr[0]
for i in 1..
위의 코드에서, createPrefixSum 함수는 입력 배열 arr를 받아 부분 합 배열을 생성하여 반환합니다.
2. 쿼리에 대한 부분 합 계산
부분 합 배열을 생성한 후, 각 쿼리에 대해 부분 합을 계산하는 함수도 작성합니다.
주어진 쿼리 (x, y)에서 부분 합은 prefixSum[y]에서 prefixSum[x - 1]를 빼면 구할 수 있습니다.
func rangeSum(prefixSum: [Int], queries: [(Int, Int)]) -> [Int] {
var result = [Int]()
for query in queries {
let x = query.0
let y = query.1
let sum = prefixSum[y] - (x > 0 ? prefixSum[x - 1] : 0)
result.append(sum)
}
return result
}
rangeSum 함수는 부분 합 배열과 쿼리 배열을 받아 각 쿼리의 부분 합을 계산하여 반환합니다.
result 배열에 각 쿼리의 결과를 저장한 후, 마지막에 반환합니다.
3. 전체 구현
위의 모든 내용을 종합하여 전체 코드를 작성해 보겠습니다.
func rangeSumQueries(arr: [Int], queries: [(Int, Int)]) -> [Int] {
let prefixSum = createPrefixSum(arr: arr)
return rangeSum(prefixSum: prefixSum, queries: queries)
}
// 예제 사용
let arr = [1, 2, 3, 4, 5]
let queries = [(0, 2), (1, 3), (2, 4)]
let results = rangeSumQueries(arr: arr, queries: queries)
print(results) // [6, 9, 12]
위의 코드에서는 배열과 쿼리를 포함하는 입력을 받아서 부분 합 쿼리를 실행하고
결과를 출력합니다. print(results)를 통해 결과를 확인할 수 있습니다.
최적화 및 변형
현재 알고리즘의 시간 복잡도는 O(N + M)으로 매우 효율적입니다.
그러나 이 외에도 더 많은 변형 및 최적화를 고려할 수 있습니다. 예를 들어, 구간 합의
연산뿐만 아니라 업데이트도 가능하도록 구현할 수 있습니다.
이는 Fenwick Tree(또는 Binary Indexed Tree)나 Segment Tree와 같은 고급 자료구조를
사용하여 수행할 수 있습니다.
이러한 자료구조는 동적 업데이트와 쿼리 연산을 동시에 지원할 수 있어 실시간으로
데이터의 변화를 반영할 수 있게 해줍니다.
이를 통해 좀 더 복잡한 문제를 해결할 수 있는 기반을 제공합니다.
결론
이번 강좌를 통해 기본적인 구간 합 문제를 해결하는 방법에 대해 알아보았습니다.
부분 합 배열을 활용하여 효율적으로 문제를 해결할 수 있었으며,
이를 통해 최적화된 코드를 작성하는 데 필요한 기초를 다졌습니다.
다음 강좌에서는 더 복잡한 문제나 고급 자료구조를 활용한 문제 해결 방법에 대해
다룰 예정입니다.
독자 여러분들이 자신만의 문제 해결 방법과 효율적인 알고리즘을 개발하는 데
많은 도움이 되었기를 바랍니다. 감사합니다.