슬라이딩 윈도우

간단하지만 유용한 스킬이다. 만약 가능하다면 O(n^2) 알고리즘을 O(n)으로 처리할 수도 있다. 문제 내에서 보조적으로 사용하면 유용한 경우가 많으니 사용가능성을 염두에 두자.

#include <stdio.h>  
  
int getSum(int index) {  
	int sum = 0;  
	for (int x = 0; x < 4; x++) {  
		sum += vect[x + index];  
	}  
	return sum;  
}  
  
int main(void) {  
	int sum = getSum(0);  
	int max = 0;  
  
	for (int x = 0; x <= 5; x++) {  
		if (sum > max) max = sum;  
		if (x == 5) break;  
  
		sum += vect[x + 4];  
		sum -= vect[x];  
	}  
  
	printf("%d", max);  
	return 0;  
}  

네트워크와 데이터 통신과 같은 과목을 들어보면, 실제로 패킷 유효성 체크를 하면서 이런 윈도우를 통해 진행하는 것을 볼 수 있는데 윈도우라는 기법이 일반적으로 많이 쓰인다고 생각하면 될 것 같다.

내용은 코드를 보면 쉽게 알 수 있을 것이다. 윈도우가 지나갈때마다 하나의 요소가 빠지고 하나의 요소를 더하는 방식으로 쭉 지나간다. 따라서 for문 하나로 처리가 가능하다.