Running Sum of an Array

Q: 배열의 누적 합이란 무엇인가요?

첫 번째 배열에서 같은 위치까지의 모든 요소를 더한 값이 각 요소인 두 번째 배열입니다. 이를 접두사 합 또는 누적 합이라고도 합니다. [3, 1, 4, 1, 5] 의 누적 합은 [3, 4, 8, 9, 14] 입니다.

Q: 누적 합계를 계산하는 시간 복잡도는 얼마인가요?

왼쪽에서 오른쪽으로 전체 합계를 하나 유지하면서 시간은 O(n) 이고, 답을 제외한 추가 공간은 O(1) 입니다. 각 접두사를 시작부터 다시 계산하면 O(n²) 입니다.

Q: 누적 합을 제자리에서 계산할 수 있나요?

네. 인덱스 1부터 끝까지 순회하면서 nums[i] += nums[i-1] 를 설정하세요. 그때쯤이면 nums[i-1] 에는 이미 해당 위치까지의 모든 값의 합이 들어 있으므로, 각 요소는 최종적으로 자신의 누적 합이 됩니다. 원래 값은 잃게 됩니다.

Q: 접두사 합은 구간 합 쿼리에 어떻게 도움이 되나요?

슬라이스 nums[l..r] 의 합은 prefix[r] - prefix[l-1] 이며, l = 0 일 때는 prefix[r] 입니다. [3, 4, 8, 9, 14] 에서 인덱스 2부터 4까지의 합은 14 - 4 = 10 입니다. 한 번의 O(n) 순회 후 각 쿼리는 O(1) 이 걸립니다.

입문누적 합

+10

정수 배열 nums가 주어집니다. 길이가 같은 새 배열을 반환하세요. 이 배열의 인덱스 i에 있는 원소는 처음 i+1개의 수의 합인 nums[0] + nums[1] + ... + nums[i]입니다.

함수

runningSum(nums: integer-array) → integer-array

numsinteger-array: 왼쪽에서 오른쪽으로 더할 숫자들
반환값integer-array: nums의 각 요소에 대해 하나씩 계산한 누적 합계

제약 조건

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
모든 누적 합계는 32비트 부호 있는 정수에 들어갑니다.

예제

입력: nums = [3, 1, 4, 1, 5]
출력: [3, 4, 8, 9, 14]
설명: 계속 더합니다: 3, 다음으로 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9, 그리고 9 + 5 = 14. 각 합계는 마지막으로 더한 숫자의 인덱스에 들어갑니다.

입력: nums = [-2, 5, -3]
출력: [-2, 3, 0]
설명: 음수는 합계를 낮춥니다: -2, 그다음 -2 + 5 = 3, 그다음 3 + (-3) = 0.

입력: nums = [7]
출력: [7]
설명: 숫자 하나에는 그 숫자 자체라는 누적 합계가 하나 있으므로, 답은 [7]입니다.

후속 질문

각 셀이 왼쪽 위 모서리부터 해당 셀까지의 직사각형 영역의 합계를 담도록 그리드에서도 같은 것을 만들 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

각 답은 nums의 접두사 합이며, 이웃한 접두사는 원소 하나만큼 차이가 납니다. 각 접두사를 처음부터 다시 계산하면 거의 모든 작업을 반복하게 됩니다. 대신 합계를 하나씩 계속 이어 가면 각 답을 구하는 데 덧셈 한 번만 하면 됩니다.

각 접두사의 값을 처음부터 다시 더하기

핵심 아이디어

정의를 따르세요. 모든 인덱스 i에 대해 합계를 0으로 시작하고, nums[0]부터 nums[i]까지 더한 다음 저장합니다. 각 답이 정의된 그대로 계산되므로 올바릅니다.

인덱스 i에는 i+1번의 덧셈이 필요하므로 배열에는 n(n+1)/2번의 덧셈이 필요합니다. 즉, n = 5000일 때 약 1.25 × 10^7번의 덧셈이 필요하며, 5000이면 충분합니다.

알고리즘

길이가 n인 answer 배열을 만듭니다.
각 인덱스 i에 대해 total = 0으로 설정합니다.
0부터 i까지의 모든 j에 대해 nums[j]를 total에 더합니다.
answer의 인덱스 i에 total을 저장하고, 마지막 인덱스 이후에 answer를 반환합니다.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

누계를 유지하기

핵심 아이디어

처음 i+1개 숫자의 합은 처음 i개의 합에 nums[i]를 더한 값입니다: result[i] = result[i-1] + nums[i]. 따라서 한 단계보다 더 거슬러 올라갈 필요가 없고, 변수 total 하나면 충분합니다. [3, 1, 4, 1, 5]의 경우 결과는 3, 4, 8, 9, 14가 되며, 이것이 정답입니다.

각 요소마다 덧셈 한 번이 필요하므로 시간은 O(n)이고, 정답 외에 추가로 사용하는 공간은 O(1)입니다.

알고리즘

길이가 n인 답변 배열을 만들고 total = 0으로 설정합니다.
인덱스를 왼쪽에서 오른쪽으로 순회하며 nums[i]를 total에 더합니다.
답변 배열의 인덱스 i에 total을 씁니다.
답변을 반환합니다.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

함정과 경계 사례

루프 안에서 total을 재설정하는 경우. 각 답이 nums[i] 하나만 남게 되어 [3, 1, 4]가 변경되지 않은 채 돌아옵니다.
i = 0일 때 result[i-1]을 읽는 경우. 대부분의 언어에서는 인덱스 범위를 벗어나지만, Python에서는 마지막 요소를 읽으므로 제자리에서 수정하는 버전은 마지막 숫자를 첫 번째 숫자에 더합니다.
브루트 포스의 내부 루프를 j < i에서 멈추는 경우. nums[i]가 빠지므로 모든 답에서 숫자가 하나씩 부족합니다.
R에서 result <- c(result, total)로 답을 늘리면 매 단계마다 벡터가 복사되어 빠른 접근 방식이 2차 시간이 됩니다. 먼저 전체 길이만큼 공간을 할당하세요.
C에서 *returnSize = numsSize를 빠뜨리는 경우. 그러면 호출자는 합계를 몇 개 읽어야 하는지 알 수 없습니다.

자주 묻는 질문4

배열의 누적 합이란 무엇인가요?

첫 번째 배열에서 같은 위치까지의 모든 요소를 더한 값이 각 요소인 두 번째 배열입니다. 이를 접두사 합 또는 누적 합이라고도 합니다. [3, 1, 4, 1, 5]의 누적 합은 [3, 4, 8, 9, 14]입니다.

누적 합계를 계산하는 시간 복잡도는 얼마인가요?

왼쪽에서 오른쪽으로 전체 합계를 하나 유지하면서 시간은 O(n)이고, 답을 제외한 추가 공간은 O(1)입니다. 각 접두사를 시작부터 다시 계산하면 O(n²)입니다.

누적 합을 제자리에서 계산할 수 있나요?

네. 인덱스 1부터 끝까지 순회하면서 nums[i] += nums[i-1]를 설정하세요. 그때쯤이면 nums[i-1]에는 이미 해당 위치까지의 모든 값의 합이 들어 있으므로, 각 요소는 최종적으로 자신의 누적 합이 됩니다. 원래 값은 잃게 됩니다.

접두사 합은 구간 합 쿼리에 어떻게 도움이 되나요?

슬라이스 nums[l..r]의 합은 prefix[r] - prefix[l-1]이며, l = 0일 때는 prefix[r]입니다. [3, 4, 8, 9, 14]에서 인덱스 2부터 4까지의 합은 14 - 4 = 10입니다. 한 번의 O(n) 순회 후 각 쿼리는 O(1)이 걸립니다.

def runningSum(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [3, 1, 4, 1, 5]

예상 출력

[3, 4, 8, 9, 14]