[알고리즘] 구간 합 구하기 sliding window & prefix sum

강신현·2022년 7월 7일
0

1. 일반적인 방법

이중 for문으로 한칸씩 이동하면서 구간 크기(w)만큼의 data 합을 구하면서 최솟값을 구한다

  • O(N*w)

2. sliding window

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

  • 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 매우 유용
  • O(N)

3. prefix sum

미리 각각의 숫자까지의 합을 계산하여 미리 저장해 놓고, 저장한 값을 그대로 활용하여 구간합을 구함

  • O(N)

예제

#include <iostream>
using namespace std;

int main(){
    int w; // 버스크기
    int park[] = {1,2,3,3,5,1,0,1,3};
    cin >> w;

    // 1. 일반적인 방법 - O(N*w)
    // 이중 for문으로 한칸씩 이동하면서 w개의 data 합을 구하면서 최솟값을 구한다

    // 2. <sliding window> - O(N)

    int s = 0; // 구간의 시작점
    int e = 0; // 구간의 끝점
    int sum = 0; // 구간내 합
    int ans = 5567890; // w크기 구간들 중 합이 가장 작은 값

    while(e<9){ // 정상 구간
        sum += park[e]; // 구간에 data 추가

        if(e-s+1 >= w){ // e-s+1 : s~e 까지의 data 개수
            if(sum < ans) ans = sum;

            sum -= park[s]; // 앞의 data 삭제
            s++; // 시작점 당기기
        }

        e++; // 끝점 미루기
    }

    cout << ans;

    // 3. <prefix> - O(N)

    int prefix[9] = {0,}; // 0~index까지의 합
    int sum = 0;

    for(int i=0;i<9;i++){ // 전처리
        sum += park[i];
        prefix[i] = sum;
    }
    
    int s = 0;
    int e = w-1;
    int ans = 5567890;

    while(e<9){
        int cal =  prefix[e] - prefix[s] + park[s];
        if(ans > cal) ans = cal;
        s++;
        e++;
    }

    cout << ans;

    return 0;
}

References

profile
땅콩의 모험 (server)

0개의 댓글

관련 채용 정보