99클럽 코테 스터디 5일차 TIL + 수열(백준 2559번)

✅ 오늘의 학습 키워드

- 누적합 (Prefix Sum)

---

✅ 공부한 내용

- 오늘은 연속된 K개 요소의 합이 최대가 되는 부분 배열을 찾는 문제를 누적합 기법으로 접근해 봤다.

누적합(Prefix Sum) 기법 이해하기

누적합은 배열의 각 위치까지의 합을 미리 계산해 두는 방식이다.
이렇게 하면 어떤 구간 [i, j]의 합도 O(1) 시간에 prefixSum[j+1] - prefixSum[i]로 계산할 수 있다.

// 누적합 배열 계산
vector<int> prefixSum(n+1, 0);
for(int i = 0; i < n; i++){
    prefixSum[i + 1] = prefixSum[i] + nums[i];
}

 

예를 들어, 배열 [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]의 누적합은 [0, 3, 1, -3, -12, -12, -9, -2, 11, 19, 16]이 된다.

이를 활용하면 인덱스 7~8 위치(13, 8)의 합은 prefixSum[9] - prefixSum[7] = 19 - (-2) = 21로 빠르게 계산할 수 있다.

---

✅ 오늘의 회고

  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

오늘 풀었던 문제는 연속된 K개 요소의 최대 합을 구하는 것이었다. 누적합을 이용해 문제를 해결하는 방법을 시도했고, 이 과정에서 누적합 배열의 크기와 인덱싱에 주의해야 한다는 점을 깨달았다.

  - 어떻게 해결했는지

누적합 배열을 n+1 크기로 만들어서 prefixSum[0]은 0으로, prefixSum[i]는 원래 배열의 0번부터 i-1번까지의 누적합을 저장하도록 구현했다. 그런 다음 모든 가능한 K 길이 구간에 대해 prefixSum[i] - prefixSum[i-k] 값을 계산하여 최대값을 찾았다.

 

// 누적합 이용
int findMaxSum(vector<int>& nums, int k){
    int n = nums.size();
    vector<int> prefixSum(n+1, 0);

    for(int i = 0; i < n; i++){
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    int maxSum = prefixSum[k] - prefixSum[0];
    for (int i = k + 1; i <= n; i++) {
        maxSum = max(maxSum, prefixSum[i] - prefixSum[i - k]);
    }

    return maxSum;
}

 

처음에 maxSum 변수를 잘못 초기화하는 실수가 있었지만, 첫 번째 K개 요소의 합으로 초기화하는 방식으로 수정했다.

  - 무엇을 새롭게 알았는지

이 문제는 슬라이딩 윈도우나 투 포인터 방식으로도 해결할 수 있다는 점을 알게 되었다.

아래는 슬라이딩 윈도우 코드다. 뭔가 유사한듯 ..아닌듯..🤔

메모리 효율성은 슬라이딩 윈도우가 더 적합하다고 한다. 다음에는 슬라이딩 윈도우를 써봐야지~

// 슬라이딩 윈도우 사용
int findMaxSum_SlidingWindow(vector<int>& nums, int k){
    int n = nums.size();
    int windowSum = 0;
    
    // 첫 k개 요소의 합 계산
    for(int i = 0; i < k; i++){
        windowSum += nums[i];
    }
    
    int maxSum = windowSum;
    
    // 윈도우를 한 칸씩 오른쪽으로 이동
    for(int i = k; i < n; i++){
        windowSum = windowSum + nums[i] - nums[i - k];
        maxSum = max(maxSum, windowSum);
    }
    
    return maxSum;
}

 

---

🛠️ 전체 코드 (누적 합)

#include <iostream>
#include <vector>

using namespace std;

int findMaxSum(vector<int>& nums, int k){ 
    int n = nums.size();
    vector<int> prefixSum(n+1, 0);

    for(int i = 0; i < n; i++){
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    int maxSum = prefixSum[k] - prefixSum[0];;
    for (int i = k + 1; i <= n; i++) {
        maxSum = max(maxSum, prefixSum[i] - prefixSum[i - k]);
    }

    return maxSum;
}

int main()
{   
    int n; 
    int k;

    cin >> n >> k;

    vector<int> nums(n);
    for (int i = 0; i < n; i++){
        cin >> nums[i];
    }

    int result = findMaxSum(nums, k);
    cout << result << '\n';

    return 0;
}