Running Sum of 1d Array — 누적합의 가장 기본 형태

스터디·6분 읽기
#알고리즘#누적합
시리즈#알고리즘· 13/16편
전체 보기
  1. 01Merge Strings Alternately — 단일 루프로 `O(n + m)` 교차 병합
  2. 02Increasing Triplet Subsequence — `O(n)` 시간, `O(1)` 공간으로 푸는 그리디 패턴
  3. 03Move Zeroes — 쓰기 포인터 하나로 `O(n)`/`O(1)` 제자리 재배치
  4. 04String Compression — 읽기/쓰기 포인터로 `O(n)`/`O(1)` 제자리 압축
  5. 05Product of Array Except Self — 나눗셈 없이 `O(n)`/`O(1)`로 나머지 곱 구하기
  6. 06Reverse Vowels of a String — 투 포인터 `O(n)` 스왑으로 모음만 뒤집기
  7. 07Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정
  8. 08시간 복잡도와 공간 복잡도 완전 정복 — Big-O 표기법부터 실전 분석까지
  9. 09Greatest Common Divisor of Strings — `GCD`로 `O(n + m)` 문자열 최대 공약 패턴
  10. 10Container With Most Water — 투 포인터 `O(n)`로 최대 넓이 한 번에 찾기
  11. 11Is Subsequence — 투 포인터 `O(|s| + |t|)`로 부분 수열 판정
  12. 12Richest Customer Wealth — 2차원 배열에서 행 합의 최댓값 찾기
  13. 13Running Sum of 1d Array — 누적합의 가장 기본 형태읽는 중
  14. 14Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기
  15. 15Palindrome Number — 문자열 없이 절반만 뒤집는 숫자 팰린드롬 판정
  16. 16Max Number of K-Sum Pairs — 정렬 `O(n log n)`에서 해시 `O(n)`까지 최대 페어 수 세기

배열의 running sum, 어떤 문제인가요?

LeetCode 1480번 문제는 이렇게 주어집니다.

정수 배열 nums가 주어집니다. runningSum[i] = sum(nums[0] ... nums[i])로 정의할 때, 배열의 running sum을 반환하세요.

예시는 이렇습니다.

  • nums = [1, 2, 3, 4] → [1, 3, 6, 10]
  • nums = [1, 1, 1, 1, 1] → [1, 2, 3, 4, 5]
  • nums = [3, 1, 2, 10, 1] → [3, 4, 6, 16, 17]

제약은 다음과 같습니다.

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

이 문제의 핵심은 각 위치의 답이 이전 위치의 답에 현재 값을 더한 것이라는 점입니다.

runningSum[i] = runningSum[i - 1] + nums[i]

이 형태는 누적합(prefix sum)의 가장 기본적인 모습입니다. 이 글에서는 매번 처음부터 다시 더하는 풀이부터, 누적 변수를 쓰는 풀이, 그리고 입력 배열을 직접 바꾸는 풀이까지 단계적으로 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. 매 위치마다 처음부터 다시 더하기

가장 직관적인 방법은 각 인덱스 i마다 0..i 구간을 다시 더하는 것입니다.

fun runningSum(nums: IntArray): IntArray {
    val answer = IntArray(nums.size)

    for (i in nums.indices) {
        var sum = 0
        for (j in 0..i) {
            sum += nums[j]
        }
        answer[i] = sum
    }

    return answer
}

nums = [1, 2, 3, 4]를 보면:

  • i = 0 → 1
  • i = 1 → 1 + 2 = 3
  • i = 2 → 1 + 2 + 3 = 6
  • i = 3 → 1 + 2 + 3 + 4 = 10

정답은 맞습니다. 하지만 이미 계산한 합을 매번 버리고 다시 계산한다는 점이 비효율적입니다.

연산 횟수는 대략:

1 + 2 + 3 + ... + n = n * (n + 1) / 2

이므로 시간 복잡도는 O(n²)입니다. 입력 제한이 작아서 통과는 할 수 있겠지만, 누적합 문제에서 기대하는 풀이는 아닙니다.

공간 복잡도는 반환 배열을 제외하면 O(1)입니다. 반환 배열까지 포함하면 O(n)입니다.

Phase 2. 누적 변수 하나로 한 번만 훑기

이전 위치까지의 합을 기억하면 다시 더할 필요가 없습니다.

fun runningSum(nums: IntArray): IntArray {
    val answer = IntArray(nums.size)
    var sum = 0

    for (i in nums.indices) {
        sum += nums[i]
        answer[i] = sum
    }

    return answer
}

같은 입력을 따라가 봅시다.

nums = [1, 2, 3, 4]

i = 0, sum = 0 + 1 = 1  -> answer[0] = 1
i = 1, sum = 1 + 2 = 3  -> answer[1] = 3
i = 2, sum = 3 + 3 = 6  -> answer[2] = 6
i = 3, sum = 6 + 4 = 10 -> answer[3] = 10

sum은 항상 현재 인덱스까지의 누적합을 의미합니다. 그래서 각 원소는 정확히 한 번만 더하면 됩니다.

시간 복잡도는 O(n), 추가 공간은 반환 배열을 제외하면 O(1)입니다. LeetCode 함수는 결과 배열을 반환해야 하므로, 새 배열을 만들면 전체 공간은 O(n)으로 볼 수 있습니다.

왜 이전 누적값 하나만 있으면 충분한가요?

i번째 답은 이렇게 쓸 수 있습니다.

runningSum[i] = nums[0] + nums[1] + ... + nums[i]

그리고 i - 1번째 답은:

runningSum[i - 1] = nums[0] + nums[1] + ... + nums[i - 1]

따라서 i번째 답은 이전 답에 현재 값만 더하면 됩니다.

runningSum[i] = runningSum[i - 1] + nums[i]

이 점화식 때문에 0..i를 매번 다시 볼 필요가 없습니다. 누적합 문제는 대부분 이 관찰에서 시작합니다.

Phase 3. 입력 배열을 직접 바꾸기

문제에서 nums를 보존해야 한다는 조건은 없습니다. 따라서 입력 배열을 결과 배열로 재사용할 수 있습니다.

fun runningSum(nums: IntArray): IntArray {
    for (i in 1 until nums.size) {
        nums[i] += nums[i - 1]
    }

    return nums
}

nums = [3, 1, 2, 10, 1]를 따라가면:

초기: [3, 1, 2, 10, 1]

i = 1 -> nums[1] = 1 + 3  = 4  -> [3, 4, 2, 10, 1]
i = 2 -> nums[2] = 2 + 4  = 6  -> [3, 4, 6, 10, 1]
i = 3 -> nums[3] = 10 + 6 = 16 -> [3, 4, 6, 16, 1]
i = 4 -> nums[4] = 1 + 16 = 17 -> [3, 4, 6, 16, 17]

여기서 nums[i - 1]는 더 이상 원래 값이 아닙니다. 이미 0..i-1까지의 누적합으로 바뀐 값입니다. 그래서 nums[i] += nums[i - 1]만 해도 nums[i]가 0..i까지의 누적합이 됩니다.

시간 복잡도는 O(n), 추가 공간은 O(1)입니다.

언제 새 배열을 만들고, 언제 in-place로 바꿀까요?

알고리즘 문제에서는 입력 배열을 바꿔도 되는 경우가 많습니다. 이 문제도 반환값이 running sum 배열이면 충분하므로 in-place 풀이가 가장 짧습니다.

하지만 실무 코드에서는 원본 배열을 이후에도 사용해야 할 수 있습니다. 이 경우에는 Phase 2처럼 새 배열을 만드는 편이 안전합니다.

  • 원본 보존이 필요함 → 새 배열 사용
  • 원본이 더 이상 필요 없음 → in-place 사용

복잡도만 보면 in-place가 더 좋지만, 실제 코드에서는 입력 변경이 호출자에게 보이는 부작용인지를 먼저 판단해야 합니다.

음수도 그대로 처리되나요?

됩니다. 누적합은 더하기만 사용하므로 음수라고 해서 별도 처리가 필요하지 않습니다.

예를 들어 nums = [-1, 2, -3, 4]라면:

[-1, 1, -2, 2]

가 됩니다.

또한 이 문제의 제약에서는 합이 Int 범위를 넘지 않습니다. 최악의 경우에도 1000 * 10^6 = 10^9 수준이므로 Kotlin Int 안에 들어갑니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력 결과 이유
[1] [1] 원소가 하나면 그대로 반환
[1, 2, 3, 4] [1, 3, 6, 10] 기본 증가 예시
[1, 1, 1, 1, 1] [1, 2, 3, 4, 5] 같은 값 반복
[3, 1, 2, 10, 1] [3, 4, 6, 16, 17] 값이 섞인 기본 예시
[-1, 2, -3, 4] [-1, 1, -2, 2] 음수 포함
[0, 0, 0] [0, 0, 0] 누적합도 모두 0

이 문제에서는 빈 배열이 들어오지 않습니다. 1 <= nums.length가 보장되므로 in-place 풀이에서 1 until nums.size를 바로 써도 안전합니다.

세 풀이를 다시 비교

풀이 시간 공간 특징
매번 0..i 다시 더하기 O(n²) 반환 배열 제외 O(1) 가장 직관적이지만 중복 계산이 많음
누적 변수 + 새 배열 O(n) O(n) 원본 배열을 보존하면서 한 번만 스캔
입력 배열 in-place 변경 O(n) O(1) 가장 짧고 공간 효율적, 원본 배열이 바뀜

마무리

  1. running sum은 누적합의 기본 형태입니다 — runningSum[i] = runningSum[i - 1] + nums[i] 점화식이 핵심입니다
  2. 매번 처음부터 다시 더하면 O(n²)입니다 — 이미 계산한 prefix를 버리지 말고 재사용해야 합니다
  3. 누적 변수 하나만 있으면 O(n)에 풀 수 있습니다 — sum이 현재 인덱스까지의 합을 계속 들고 갑니다
  4. 입력 배열을 직접 바꾸면 추가 공간을 O(1)로 줄일 수 있습니다 — 다만 원본 배열을 보존해야 하는 상황에서는 새 배열이 더 안전합니다
  5. 이 패턴은 이후의 prefix sum 문제로 이어집니다 — 구간 합, 빈도 누적, 차분 배열 같은 문제들도 결국 "이전까지의 계산을 재사용한다"는 관찰에서 출발합니다
← 목록으로
공유
이전 편

Richest Customer Wealth — 2차원 배열에서 행 합의 최댓값 찾기

다음 편

Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기

다음으로 읽어볼 글

스터디

Max Number of K-Sum Pairs — 정렬 `O(n log n)`에서 해시 `O(n)`까지 최대 페어 수 세기

합이 `k`가 되는 두 수를 한 번씩만 써서 최대 몇 쌍을 만들 수 있는지 구하는 LeetCode 1679번, `O(n²)` 브루트포스부터 정렬 + 투 포인터 `O(n log n)`, 해시 카운팅 `O(n)`까지 정리합니다.

#알고리즘
·8분
스터디

Palindrome Number — 문자열 없이 절반만 뒤집는 숫자 팰린드롬 판정

정수가 앞에서 읽어도 뒤에서 읽어도 같은지 판정하는 LeetCode 9번, 문자열 변환 풀이부터 전체 숫자 뒤집기, 오버플로우 걱정을 줄이는 절반 뒤집기 `O(log x)` 풀이까지 정리합니다.

#알고리즘
·7분
스터디

Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기

로마 숫자 문자열을 정수로 바꾸는 LeetCode 13번, 감산 조합을 직접 처리하는 풀이부터 왼쪽→오른쪽 lookahead, 오른쪽→왼쪽 스캔 `O(n)` 풀이까지 정리합니다.

#알고리즘
·11분