[코딩테스트 기초 08] 누적 합으로 여러 구간의 합 구하기

같은 리스트에서 여러 구간의 합을 반복해서 구한다면, 매번 구간을 순회하는 대신 앞부분의 합을 저장해 둘 수 있습니다. 이번에는 누적 합을 이용해 구간 합을 구하는 자체 연습 문제를 풀어 봅니다.

특정 코딩테스트 사이트의 문제 원문이나 테스트 데이터를 사용하지 않았습니다. 아래 문제와 예제는 직접 구성했으며 플랫폼 채점 결과를 의미하지 않습니다.

구간의 끝은 포함하지 않습니다

정수 리스트 values와 구간 목록 queries가 주어집니다. 각 구간 (left, right)에 대해 values[left:right]의 합을 반환합니다.

인덱스는 0부터 시작하며, 0 <= left <= right <= len(values)를 만족한다고 가정합니다. 오른쪽 끝은 포함하지 않습니다. 입력값은 정수이고 음수도 허용합니다.

values = [3, -1, 4, 2]
queries = [(0, 4), (1, 3), (2, 2)]
# 기대 결과: [8, 3, 0]

두 번째 구간은 -1 + 4 = 3입니다. 세 번째처럼 시작과 끝이 같으면 빈 구간이므로 합은 0입니다.

앞에서부터 더한 값을 하나 더 저장합니다

prefix[k]를 “처음 k개 원소의 합”으로 정의합니다. 그러면 prefix[0]은 아무것도 더하지 않은 0입니다.

[left, right)의 합은 prefix[right] - prefix[left]입니다. 오른쪽 경계까지의 합에서 왼쪽 경계 앞부분의 합을 빼는 방식입니다.

def range_sums(values, queries):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)

    result = []
    for left, right in queries:
        result.append(prefix[right] - prefix[left])
    return result

맨 앞에 0을 두었기 때문에 0번 인덱스에서 시작하는 구간도 별도 분기 없이 계산할 수 있습니다.

경계와 음수 입력을 함께 확인합니다

assert range_sums([3, -1, 4, 2], [(0, 4), (1, 3), (2, 2)]) == [8, 3, 0]
assert range_sums([], [(0, 0)]) == [0]
assert range_sums([5], [(0, 1), (1, 1)]) == [5, 0]
assert range_sums([-3, -2], [(0, 2)]) == [-5]
assert range_sums([1, 2], []) == []

이 함수는 문제에서 보장한 유효 구간을 입력받는 풀이입니다. 범위를 벗어난 값을 자동으로 보정하지 않으며, 실제 서비스에 사용할 때는 입력 검증을 별도로 설계해야 합니다.

리스트 길이가 n, 질의 수가 q라면 누적 합을 만드는 데 O(n), 각 질의에 O(1)이므로 전체 시간은 O(n + q)입니다. 누적 합에 O(n), 반환 결과에 O(q) 공간을 사용합니다.

구간 합이 한 번만 필요하다면 sum(values[left:right])가 더 간단할 수 있습니다. 누적 합은 원본 값이 바뀌지 않고 여러 구간을 반복 조회할 때 특히 유용합니다. 값이 바뀌면 저장해 둔 누적 합도 더 이상 유효하지 않다는 점을 함께 기억해야 합니다.