백준 2559번 - 수열

https://www.acmicpc.net/problem/2559

2559번: 수열

#include <bits/stdc++.h>
using namespace std;
int n, k;

int main(){
	
	cin >> n >> k;
	
	vector<int> tem(n);
	
	for(int i=0; i<n; i++){
		cin >> tem[i];
	}
	
	int curSum =0;
	int maxSum = 0;
	
	//초기설정 
	for(int i=0; i<k; i++){
		curSum += tem[i];
	}
	maxSum = curSum;
	
	//슬라이딩 윈도우 
	for(int i=k; i<n; i++){
		curSum = curSum + tem[i] - tem[i-k];
		maxSum = max(curSum, maxSum);
	}
	
	cout << maxSum;
		
	return 0;
}

 [ 슬라이딩 윈도우 기법 ]

 

- 연속적인 부분 구간을 이동하면서 해결하는 알고리즘 기법

- 주로 "부분 합", "최대값/최솟값" 구할 때 사용

- 배열 or 리스트에서 고정 크기의 윈도우 움직이면서 필요한 연산 수행

 

cf) 시간 초과 나왔던 코드

#include <bits/stdc++.h>
using namespace std;
int n, k;

int main(){
	
	cin >> n >> k;
	
	vector<int> tem(n);
	
	for(int i=0; i<n; i++){
		cin >> tem[i];
	}
	int maxSum = tem[0];
	
	for(int i=0; i+k <= n; i++){
	    int sum =0;
		int std = i;
		int cnt = k;
		
		while(cnt>0){
			sum += tem[std];
			
			std++;
			cnt--;
		}
		
		if(maxSum < sum){
			maxSum = sum;
		}	
	}
	
	cout << maxSum;
		
	return 0;
}

각 위치에서 k개의 숫자를 선택한 후에 부분합을 구해 최대값을 찾는 것이기 때문에 시간 복잡도는 O(nk)가 된다. 이 방법은 k가 작을 때는 상관없지만, k가 커지면서 입력이 커지면 시간 초과가 발생할 수 있다.