투 포인터, 슬라이딩 윈도우 기법

투 포인터(Two Pointers method)

 

투 포인터란?

 

 - 배열을 따라 두 개의 포인터를 이동시키면서 데이터를 처리하는 알고리즘

 

 - 포인터 두 개는 모두 한쪽 방향으로 움직인다.

 

 - 투 포인터를 이용한 경우 값이 모두 양수이여야 한다.

 

---

 

투 포인터 예시(부분합이 27인 구간 구하기)

 

- SUM = 1 < 27 이기 때문에 RIGHT를 오른쪽으로 한 칸 이동

 

 

- SUM = 6 < 27 이기 때문에 RIGHT를 오른쪽으로 한 칸 이동 

 

 

- SUM = 9 < 27 이기 때문에 RIGHT를 오른쪽으로 한 칸 이동 

 

 

- SUM = 20 < 27 이기 때문에 RIGHT를 오른쪽으로 한 칸 이동 

 

- SUM = 33 > 27 이기 때문에 LEFT를 왼쪽으로 한 칸 이동 

 

 

 

- SUM = 32 > 27 이기 때문에 LEFT를 왼쪽으로 한 칸 이동 

 

 

- SUM = 27 == 27 이기 때문에 종료. 

 

 

---

투 포인터 예시

#include <bits/stdc++.h>
#include <string>

using namespace std;

int number[100001];

int twoPointer(int N,int S)
{
	int start = 0;
	int last = 0;
	long long sum = 0;
	int result = INT_MAX;

	// sum = number[start] + ... + numbers[last-1] 값
	while (true)
	{

		if (sum >= S)
		{
			result = min(result, last - start);
			sum -= number[start];
			start++;
		}
		else if (last == N)
			break;
		else if (sum < S)
		{
			sum += number[last];
			last++;
		}
	}

	if (result == INT_MAX)
		result = 0;
	return result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	int S;
	
	cin >> N >> S;

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

	cout << twoPointer(N, S) << endl;
	

	return 0;
}

 

 

 

---

관련문제

20922번: 겹치는 건 싫어

 

 

1806번: 부분합

---

 슬라이딩 윈도우(Sliding Window)

 

슬라이딩 윈도우란?

 

 - 슬라이딩 윈도우는 배열을 따라 왼쪽에서 오른쪽으로 고정된 크기의 부분 배열을 이동하는 알고리즘

 

 - 배열의 크기가 N, 고정된 크기가 K인 경우 시간복잡도는 O(N+K)이다.

 

---

 

슬라이딩 윈도우 예시(크기 3인 배열)

 

 

 

 

---

슬라이딩 윈도우 예시( 크기가 정해진 연속 배열의 최대 값 구하기 )

 

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	srand((unsigned int)time(0));

	int r1 = rand() % 100;

	int N = 1000;
	int K = 5;

	int sum = 0;
	int result = 0;

	int arr[1000];

	for (int i = 0; i < N; i++) {
		arr[i] = rand() % 100;
	}

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

	result = sum;
	

	for (int i = K; i < N; i++) {
		
		// 앞에 값 뺴주기
		sum -= arr[i - K];

		// 뒤에 값 넣어주기
		sum -= arr[i];

		result = max(result, sum);

	}

	cout << " 연속된 5개의 합 중 가장 큰 값은 " << result << " 이다.";


	return 0;
}

 

 

---

관련 문제

 

15961번: 회전 초밥