[백준/C++] 2559번 수열 /투 포인터 알고리즘/ two_pointer - (1)

백준 2559번 수열

 

2559번 수열 코딩테스트 풀이

이 문제는 투 포인터 알고리즘을 통해 구현할 수 있다. 

 

투 포인터란?

배열에서 이중 for문으로 O(n^2)으로 시간 복잡도를 가지는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다.

 

2559번 수열 문제에서는 연속된 k개의 수열 중 가장 최댓값을 구하는 문제이기 때문에, 이중 for문으로 돌기는 하지만, 2번 째 for문은 k번만 돌면 되고 만약 k 값이 크다면 첫번째 for문은 n-k 번째까지만 돌기 때문에

온전한 시간복잡도가 O(n^2)이 아니다.

 

	for (int i = 0; i <= n-k; i++) {
		int num = 0;
		for (int j = i; j < i+k; j++) {
			num += vec[j];
			
		}
		if (num > max) max = num;
	}

 

다른 부분을 볼 필요가 없고, 위 코드처럼 간단히 비교해주면 된다.

 

여기서 수열의 값의 범위는 -100 부터 100까지이기 때문에 절대 max 값을 무심코 0이나 -10 같이 적게 설정하면 실제로 max값이 그 값보다 작아 값이 안나올 수 있다. 

 

2559번 수열 전체 코드

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

using namespace std;

vector<int> vec;

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

	int n, k;

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		vec.push_back(num);
	}

	int result = 0;

	int max = -100000;

	for (int i = 0; i <= n-k; i++) {
		int num = 0;
		for (int j = i; j < i+k; j++) {
			num += vec[j];
			
		}
		if (num > max) max = num;
	}

	cout << max;
}