[실버3] [C++] 2559번: 수열

링크

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

2559번: 수열

문제

입출력 예제

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, k;

	cin >> n >> k;

	vector<int> temper(n);
	vector<int> sum;

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

	int start = 0;
	int end = k - 1;
	int temp = 0;

	for (int i = start; i <= end; i++)
	{
		temp += temper[i];
	}
	sum.push_back(temp);


	while (end < n - 1)
	{
		temp -= temper[start++];
		temp += temper[++end];
		sum.push_back(temp);
	}
	sort(sum.begin(), sum.end(), greater<>());

	cout << sum[0];
}

풀이

슬라이딩 윈도우는 연속적인 데이터나 배열에서 고정된 크기의 창(윈도우)를 이용하여 특정 연산을 수행하는 기술입니다. 이는 배열 또는 연속적인 데이터 구조에서 부분적인 데이터에 대한 작업을 수행하는 데 유용합니다. 주로 부분합, 부분곱, 특정 범위 내의 최소값 또는 최대값을 찾는 데 사용됩니다.

 

해당 문제는 투포인터를 사용하여 풀었고 그 중, 슬라이딩 윈도우를 사용하였습니다.

슬라이딩 윈도우는 창문을 밀듯이 일정 범위를 옆으로 옮겨가며 값을 찾는 알고리즘입니다.

다음과 같은 배열에서 연속된 5개의 수의 합 중 가장 큰 값을 찾기 위해

 

이런식으로 5개의 수를 범위로 지정해두고 옆으로 옮겨가며 총 합 중에서 가장 큰 값을 찾는것 입니다!

 

 

 

start와 end 포인터를 통해서 해당 지점들 사이의 수를 모두 더해 sum에 저장합니다.

 

이후 sum에서 start의 값을 빼고, start와 end를 증가시키고 sum에 증가된 end의 값을 더하면
그림과 같이 크기를 유지한채로 범위가 옆으로 한칸 옮겨가는 것을 확인할 수 있습니다.

 

해당 과정을 반복하여 모든 범위의 합을 저장한 후 그 중 가장 큰 값을 찾아 출력하면 끝입니다!