sliding window, prefix

한 칸씩 배열을 전진하면서 W칸의 합을 구할 때

int arr[] = {1, 2, 3, 3, 5, 0, 8, 3, 4};

 

1. 이중 for문

for (int i=0;i<N;i++) {
	int sum=0;
	for (int j=i;j<i+W;j++) {
    	sum += arr[j];
    }
}

 

시간복잡도 : O(N*W)

 

 

2. Sliding Window

만약 W=3이라면,

 

1. 1 + 2 + 3
2. 2 + 3 + 3

겹치는 구간 발생!

 

sum(0, 2) = arr[0] + sum(1, 2)

sum(1, 3) = sum(1, 2) + arr[0]

임을 이용하자

 

int sum;  // 구간의 합
int s=0, e=0; // s : 구간의 시작점, e : 구간의 끝점

while (e<9) {
    sum += arr[e];
    e++;
    if (e-s+1 >= W) { // W개 크기의 구간이 완성됐다면
    	// 구간을 옮겨준다. 맨 앞 칸 전진.
        sum -= arr[s];
        s++;
    }
}

 

시간복잡도 : O(N)

 

 

3. prefix

• 전처리 방식 일종
  • 전처리 방식 : 중복계산을 줄여준다
• 미리 각각의 index마다 sum(0, index) 값을 구하는 것
• 어떤 구간 사이의 합을 빠르게 구할 수 있다

int prefix[] = {0};

prefix[0] = arr[0];
for (int i=1;i<N;i++) {
	prefix[i] = arr[0] + prefix[i-1];
}

 

만약 sum(3, 5)의 값을 알고 싶으면

int sum = prefix[7]-prefix[4];

 

즉,

int sum = prefix[end] - prefix[start-1];

 

시작복잡도 : O(N)