[Swift] 누적 합 / Prefix Sum / Cumulative Sum

알고리즘 문제풀이에서의

누적 합은 말 그대로 구간의 누적합을 구하는 문제입니다.

---

누적 합

 

BOJ Book을 Swift 코드에 맞춰서 다시 읽어보고 이해해 보려고 합니다.

---

 

 

 

int ans = 0;
for i in l..<r {
    ans += a[i];
}

 

소스 1의 시간 복잡도는 O(N)입니다. 문제에서는 연산을 최대 M번 수행해야 한다고 했으니, 총 시간 복잡도는 O(NM)이 됩니다.

 

 

 

 

for i in 1..<n+1 {
    s[i] = s[i-1] + a[i]
}

 

배열의 시작 인덱스

위의 설명에서 배열 A의 시작 인덱스는 1로 사용했습니다. 그 이유는 S[l−1] 때문입니다. 시작 인덱스가 1이면 l의 최솟값은 1이고, 여기서 l−1은 0입니다. 만약, 시작 인덱스가 0이었다면, l의 최솟값은 0이고, 이때 l−1은 −1입니다.

배열의 인덱스로 음수를 사용할 수 없기 때문에, 1부터 시작하는 것으로 정했습니다. 물론 0부터 시작해도 누적 합을 사용할 수 있습니다. 하지만, 뒤에 배열 한 칸이 더 필요합니다.

11659 - 구간 합 구하기 4

11659번: 구간 합 구하기 4

구간 합 구하기 기본

let NM = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (N, M) = (NM[0], NM[1])

let a = [0]+readLine()!.split{$0==" "}.map{Int(String($0))!}
var s = a

for i in 1...N {
	s[i] = s[i-1] + a[i]
}

for _ in 0..<M {
	let ij = readLine()!.split{$0==" "}.map{Int(String($0))!}
	let (i, j) = (ij[0]-1, ij[1])
	let sum = s[j]-s[i]
	print(sum)
}

Swift에서 reaLine을 위와 같은 식으로 구현하기 위해서 [0] 배열에 map을 넣어서 처리해주었습니다.

연습 문제

• 2559 - 수열
• 17425 - 약수의 합
• 10986 - 나머지 합

 

2259 

let NK = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (N, K) = (NK[0], NK[1])
let INF = -9876543210
let a = [0]+readLine()!.split{$0==" "}.map{Int(String($0))!}
var s = a
var maxSum = INF

for i in 1...N {
	s[i] = s[i-1] + a[i]
}

for i in 0...N-K {
	let sum = s[i+K]-s[i]
	maxSum = max(sum, maxSum)
}

print(maxSum)

 

17425

var div = Array(repeating: 0, count: 1000001)
var sum = Array(repeating: 0, count: 1000001)

for i in 1...1000000 {
	var j = 1
	while i*j <= 1000000 {
		div[i*j] += j
		j += 1
	}
}
sum[1] = div[1]
for i in 2..<div.count {
	sum[i] = sum[i-1] + div[i]
}

let T = Int(String(readLine()!))!

for _ in 0..<T {
	let num = Int(String(readLine()!))!
	print(sum[num])
}

 

10986

누적 합의 나머지가 같다는 점을 나머지의 빈도 계산에 이용할 수 있다는 점을 활용하여 풀어낸 문제.

import Foundation

let NM = readLine()!.split(separator: " ").map{ Int($0)! }
let (N, M) = (NM[0], NM[1])
let a = readLine()!.split(separator: " ").map{ Int($0)! }

var remainderCount = [Int](repeating: 0, count: M)
remainderCount[0] = 1

var sum = 0
var count = 0

for i in 0..<N {
	sum = (sum + a[i]) % M
	count += remainderCount[sum]
	remainderCount[sum] += 1
}

print(count)