002 (알고리즘) 누적합

누적합

알고리즘

누적합은 직관적으로 누적합 문제라는 것을 알려주는 문제가 있고, 그렇지 않은 문제가 있다. 누적합인 것을 알고 푸는것과 모르고 푸는것은 십중팔구 모르고 풀었을때 운좋게 통과되는 경우는 없다. 출제 의도가 누적합이라면, 누적합으로 풀어야 시간제한 안으로 문제를 풀 수 있다.

Subarray Sum Equals K

https://neetcode.io/problems/subarray-sum-equals-k/question

Input: nums = [2,-1,1,2], k = 2
 
Output: 4

연속된 서브 배열의 합이 k가 되는 서브 배열의 갯수를 구하라.

일단 답을 구한다.

시간복잡도: O(N^2)

class Solution {
public:
 
    int subarraySum(vector<int>& nums, int k) { 
        int res = 0;
        for (int i = 0 ; i < nums.size() ; i++) {
            vector<int> arr(nums.begin() + i, nums.end());
            if (arr[0] == k) res++;
            for (int j = 1 ; j < arr.size() ; j++) {
                arr[j] += arr[j-1];
                if (arr[j] == k) res++;
            }
        }
        return res;
    }
};

누적합을 적용한 방식

시간 복잡도: O(N) 공간 복잡도: O(N)

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0;
        int sum = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;
        for (auto n : nums) {
            sum += n;
            int need = sum - k;
            if (mp.find(need) != mp.end()) {
                res += mp[need];
            }
            mp[sum]++;
        }
        return res;
    }
};

i까지의 누적합 과 그전에 구한 어떤 누적합의 차이가 k일때, 그 사이의 원본배열 값들의 합이 k라는 의미가 된다. [2, -1, 1, 2] 누적합→ [0, 2, 1, 2, 4] i=0, 2 기준, 2-k = 0, 0이 prefixSum 배열에 존재하므로, 있다고 생각 ([2], [2, -1, 1]) i = 3 기준, 4 - k = 2, 2 또한 prefixSum 배열에 두개 존재하므로, 있다고 생각 ([-1, 1, 2], [2]) → 총 4개

직관이 뛰어난 사람이면 바로 이해하겠지만, 나는 이를 바로 이해하지 못했다. 누적된 값과 원본 배열의 상관관계를 잘 이해하지 못해서 그런것 같은데, 연속된 수의 합과 같은 것은 일단 누적합 을 쓸 수 있겠다는 생각을 지니고 문제를 접근해야곘다.

누적합을 통해 원본배열 혹은 어떠한 자료구조의 연속된 특징을 뽑아내서 쓸수 있다 라는 생각