투포인터 알고리즘 (Two pointers Algorithm)

투포인터 알고리즘은 슬라이딩 윈도우 알고리즘이라고도 하며, 1차원 배열에서 두 개의 포인터를 조작해서 원하는 결과를 얻는 알고리즘이라고 한다.

보통 완전탐색으로 풀어서 시간초과가 날때의 해결책이 될 수 있다고 한다.

 

 

---

아래 문제가 전형적인 투포인터 알고리즘 문제이다.

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

2003번: 수들의 합 2

 

주어진 1차원 배열 중에 합이 M이 되는 부분의 수를 구하는 문제이다.

1) 포인터를 start, end로 지정하고

2) arr[start]부터 arr[end]까지의 합이 M보다 작으면 end포인터를 1 중가시키고

3) M보다 크면 start를 1 증가시키고

4) 같으면 cnt를 1 증가시키고 end를 1 증가시킨다.

5) end가 배열의 끝에 도달하면 종료한다.

 

이 문제를 완전탐색으로 풀면 이중 for문이 필요하기에 시간복잡도는 O(N^2)가 된다. 하지만 투포인터를 이용하면 O(N)이다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, m, arr[10010];
ll st, ed, cnt, tmp;

ll arr_sum(ll st, ll ed) {
	ll sum = 0;
	for (ll i = st; i <= ed; i++) {
		sum += arr[i];
	}

	return sum;
}

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;

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

	while (ed != n) {
		tmp = arr_sum(st, ed);
		if (tmp < m) ed++;
		else if (tmp > m) st++;
		else {
			ed++;
			cnt++;
		}
	}

	cout << cnt;
}