[알고리즘] 01. 누적합 with Swift

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

해당 문제를 풀면서 누적합을 처음 접했다. 

문제를 보고 값을 계산해서 저장해서 꺼내서 사용하면 될 것 같다는 생각은 들었는데, 정확한 해결방법이 누접합!인지는 몰랐다..!

 

누적합에 대해 알아보자!

---

누적합

특정 구간의 합을 찾는데 유용한 알고리즘

 

누적합 알고리즘은 연속된 원소들의 합을 빠르게 계산하는 알고리즘입니다. 배열과 같은 시퀀스 데이터에서 일부 구간의 합을 찾는 데 사용됩니다. 이 알고리즘은 전체 배열을 반복해서 덧셈을 수행하는 방식보다 빠른 계산을 가능하게 합니다.

 

누적합 알고리즘 작동 방식

1. 누적 배열 생성: 원래의 배열과 같은 길이를 갖는 배열을 만듭니다. 이 배열의 각 인덱스는 원래 배열의 인덱스까지의 합을 저장합니다.
2. 누적 배열 값 갱신: 누적 배열을 구성할 때, 각 원소는 해당 인덱스까지의 합을 나타냅니다. 예를 들어, 누적 배열의 i번째 항목은 원래 배열의 0번째부터 i번째까지의 합을 나타냅니다.
3. 특정 구간 합 계산: 구간[i, j]의 합은 누적합[j]에서 누적합[i-1]을 빼면 쉽게 구할 수 있습니다. 이로써, 배열의 특정 구간의 합을 계산하는 데 시간 복잡도 O(1)에 구할 수 있습니다.

func calculatePrefixSum(_ arr: [Int]) -> [Int] {
    var prefixSum = [Int](repeating: 0, count: arr.count)
    
    // 첫 번째 원소는 자기 자신이므로 원래 배열의 첫 번째 값으로 초기화
    prefixSum[0] = arr[0]
    
    // 누적합 배열 구성
    for i in 1..<arr.count {
        prefixSum[i] = prefixSum[i - 1] + arr[i]
    }
    
    return prefixSum
}

func cal(_ start: Int, _ end: Int) -> Int {
    if start == end { return arr[start] }
    if start == 0 { return prefixSumArray[end] }
    return prefixSumArray[end] - prefixSumArray[start-1]
}

// 예시 배열
let arr = [3, 1, 7, 5, 2, 4]

// 누적합 계산
let prefixSumArray = calculatePrefixSum(arr)
print("누적합 배열: \(prefixSumArray)")

// 구간 인덱스[2, 4]의 합
let result = cal(2, 4) // 인덱스에 유의