[Data Structure / Algorithms] Perfix Sum

전성훈·2023년 11월 21일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

35/35

주제: 누적 합 구하기

구간 합

구간 합은 배열이나 리스트와 같은 데이터 구조에서 특정 구간에 있는 요소들의 합을 의미합니다. 이 개념은 다양한 알고리즘과 데이터 처리 문제에서 매우 중요합니다.
구간합의 계산으로 데이터 분석, 이미지 처리에서의 픽셀 값 계산 등 다양한 분야에서 응용됩니다.
만약 연속적으로 나열된 N개의 수가 있을 때, 특정 구간을 합한다고 하면 특정 구간을 Left와 Right로 구성할 수 있습니다.
만약 특정 구간에 대해 M개의 구간이 주어졌을 때 해당 구간들을 계산하는 알고리즘의 시간복잡도는 $O(NM)$ 의 시간 복잡도를 가집니다.
왜냐하면, M개의 쿼리가 수행될 때마다 전체 리스트의 구간 합을 전체 리스트의 구간 합을 모두 계산하라고 요구할 수도 있기 때문입니다.
그렇다면 N = 1,000,000이고,M = 1,000,000인 상황처럼 데이터의 개수가 매우 많을 때, $O(NM)$ 의 시간 복잡도로 동작하는 알고리즘은 문제를 해결할 수 없을 것 입니다.
항상 우리가 알고리즘을 설계할 때 고려해야 할 점은, 여러 번 사용될 만한 정보는 미리 구해 저장해 놓을수록 유리하다는 것 입니다. 확인해보면 구간은 M개이지만 N개의 수는 한 번 주어진 뒤에 변경되지 않습니다.
따라서 N개의 수에 대해서 어떠한 처리를 수행한 뒤에 나중에 M개의 쿼리를 각각 주어질 때마다 빠르게 도출할수있습니다.
어떠한 처리가 Perfix sum(누적합) 알고리즘 입니다.

부분 합(누적 합) 알고리즘(Perfix Sum)

누적 합은 배열에서 각 위치에 대해 해당 위치까지의 모든 요소의 합을 나타내는 개념입니다. 이는 데이터의 연속적인 부분 구간에 대한 합을 효율적으로 계산하기 위해 사용됩니다.

특징

누적 합 배열은 원본 배열의 각 위치까지의 합을 순차적으로 저장한 배열입니다. 예를 들어, 원본 배열이 [1,2,3,4]라면, 누적 합 배열은 [1, 3, 6, 10]이 됩니다.
구간 합 문제, 구간 내 평균 계산, 특정 범위 내의 데이터 처리 등에 널리 사용됩니다.
시계열 데이터나 누적 데이터 통계에서 중요한 역할을 합니다.
픽셀 값의 누적 합을 이용해 이미지의 특정 영역에 대한 처리를 빠르게 수행할 수 있습니다.

구현 방법

원본 데이터를 포함하는 배열을 준비합니다.
누적 합을 저장할 배열을 생성합니다.
원본 배열의 각 요소에 대해. 이전 요소들의 합을 더하여 누적 합 배열에 저장합니다.

복잡도

누적 합 배열이 이미 계산되어 있다면, 어떤 구간의 합을 구하던지 $O(1)의 시간 복잡도가 걸립니다.
위 문제에 대해서는 전체 구간 합을 모두 계산하는 작업은 $O( N + M)$ 의 시간 복잡도를 가집니다.

구현

1차원 누적합

// Perfix Sum 1차원 구하기 
func cumulativeSum(_ arr: [Int]) -> [Int] { 
	var cumSum = arr
	for i in 1..<arr.count { 
		cumSum[i] += cumSum[i - 1]
	}
	return cumSum
}

// Perfix Sum 1차원 구하기 
func cumulativeSum2(_ arr: [Int]) -> [Int] { 
	var cumSum = Array(repeating: 0, count: arr.count + 1)
	
	for i in 0..<arr.count { 
		cumSum[i + 1] = cumSum[i] + arr[i]
	}
	
	return cumSum
}

let arr = [1,2,3,4,5]
print(cumulativeSum(arr))
// [1, 3, 6, 10, 15]

2차원 누적합

각 셀의 누적 합은 위쪽 셀의 누적 합 + 왼쪽 셀의 누적 합 - 대각선 위 셀의 누적합 + 현재 셀의 값으로 계산할 수 있습니다.
이러한 계산은 중복으로 더해진 영역을 제거하기 위함입니다.

func cumulativeSum2D(_ arr: [[Int]]) -> [[Int]] {
    let rows = arr.count
    let cols = arr[0].count
    var cumSum = Array(repeating: Array(repeating: 0, count: cols + 1), count: rows + 1)

    for r in 1...rows {
        for c in 1...cols {
            cumSum[r][c] = cumSum[r - 1][c] + cumSum[r][c - 1] - cumSum[r - 1][c - 1] + arr[r - 1][c - 1]
        }
    }

    return cumSum
}

let arr3 = [
    [0, 1, 2],
    [5, 6, 7],
    [10, 11, 12]
]
print(cumulativeSum2D(arr3))

[[0, 0, 0, 0], [0, 0, 1, 3], [0, 5, 12, 21], [0, 15, 33, 54]]