[C++] 투 포인터

투 포인터

• 2개의 포인터를 이용해 알고리즘의 시간 복잡도를 최적화한다.
• 시간 복잡도에서 N의 최댓값이 10,000,000 처럼 매우 크게 잡혀 있는 경우, O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 하는데, 이런 경우 투 포인터 알고리즘을 자주 사용한다.

 

관련 문제들

• 백준 2018 (실버5)

#include <iostream>
using namespace std;

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

	int N;
	cin >> N;

	int start_index = 1;
	int end_index = 1;
	int cnt = 1;
	int sum = 1;

	while (end_index != N)
	{
		if (sum < N)
		{
			end_index++;
			sum += end_index;
		}
		else if (sum > N)
		{
			sum -= start_index;
			start_index++;
		}
		else if (sum == N)
		{
			cnt++;
			end_index++;
			sum += end_index;
		}
	}
	cout << cnt << '\n';

	return 0;
}

• 백준 1940 (실버4)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, M;
	cin >> N >> M;

	vector<int> material(N, 0);

	for (int i = 0; i < N; i++)
	{
		cin >> material[i];
	}
	sort(material.begin(), material.end());

	int start_index = 0;
	int end_index = N - 1;
	int cnt = 0;

	while (start_index < end_index)
	{
		if (material[start_index] + material[end_index] < M)
		{
			start_index++;
		}
		else if (material[start_index] + material[end_index] > M)
		{
			end_index--;
		}
		else if (material[start_index] + material[end_index] == M)
		{
			cnt++;
			end_index--;
		}
	}

	cout << cnt << '\n';

	return 0;
}

• 백준 1253 (골드4)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int N;
	cin >> N;

	vector<int> A(N, 0);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	sort(A.begin(), A.end());

	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		int start_index = 0;
		int end_index = N - 1;

		while (start_index < end_index)
		{
			if (i == start_index)
			{
				start_index++;
				continue;
			}
			if (i == end_index)
			{
				end_index--;
				continue;
			}

			if (A[start_index] + A[end_index] < A[i])
			{
				start_index++;
			}
			else if (A[start_index] + A[end_index] > A[i])
			{
				end_index--;
			}
			else if (A[start_index] + A[end_index] == A[i])
			{
				cnt++;
				break;
			}
		}
	}
	cout << cnt << '\n';

	return 0;
}