투 포인터

투 포인터(Two Pointers) 알고리즘은 1차원 배열에서 두 개의 포인터를 조작하여 각각이 가리키는 원소에 의미를 부여하여 원하는 결과를 얻는 알고리즘이다.

2중 for 문을 이용해 배열의 모든 연속 구간을 잡는다면 O(N^2) 의 시간 복잡도이지만 투 포인터 알고리즘을 사용하면 O(N) 의 시간복잡도로 해결할 수 있다.

투 포인터의 유형으로는 2개의 포인터를 어떤 조건에 증감시킬지에 따라 다음과 같이 나눌 수 있다.

1. 포인터 2개가 같은 방향으로 진행하는 것
2. 포인터 2개가 양 끝에서 시작하여 반대로 진행하는 것
3. 포인터 1개는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것 → 모스 알고리즘 (Mo’s Algorithm)

예시

1번 유형

• 포인터 2개가 같은 방향으로 진행하는 경우

N 개의 자연수를 갖는 수열에서 연속 구간의 합이 M 이 되는 경우의 수 찾기

위 그림의 경우에 대해 코드를 작성하면

#include <iostream>
#include <vector>

int main() 
{
	std::vector<int> Nums = { 1, 2, 3, 4, 2, 5, 3, 1, 1, 2 };
	std::cout << "합이 5인 구간" << std::endl;

	int Left = 0, Right = 0;
	int Sum = Nums[0], Result = 0;
	while (Left <= Right && Right < Nums.size())
	{
		if (5 < Sum) // 합이 작아져야 하는 상황. Left 포인터가 오른쪽으로
			Sum -= Nums[Left++];
		else if (5 > Sum)	// 합이 커져야 하는 상황. Right 포인터가 오른쪽으로
		{
			if (Nums.size() > ++Right)
				Sum += Nums[Right];
		}
		else // 두 포인터 모두 오른쪽으로
		{
			std::cout << "[" << Left << ", " << Right << "]" << std::endl;
			Sum -= Nums[Left++];
			if (Nums.size() > ++Right)
				Sum += Nums[Right];
		}
	}
	
	return 0;
}

합이 5인 구간
[1, 2]
[5, 5]
[6, 8]

2번 유형

• 포인터 2개가 양 끝에서 시작하여 반대로 진행하는 경우

N 개의 서로 다른 정수를 갖는 정렬된 수열에서 서로 다른 두 원소의 합이 M 인 경우

위 그림의 경우에 대해 코드를 작성하면

#include <iostream>
#include <vector>

int main() 
{
	std::vector<int> Nums = { -10, -6, -2, -1, 2, 4, 6, 7, 12, 15 };
	std::cout << "합이 5인 두 원소" << std::endl;

	int Left = 0, Right = Nums.size() - 1;
	while (Left < Right)
	{
		int Sum = Nums[Left] + Nums[Right];
		if (5 < Sum) // 합이 작아져야 하는 상황. Right 포인터를 왼쪽으로
			--Right;
		else if (5 > Sum) // 합이 커져야 하는 상황. Left 포인터를 오른쪽으로
			++Left;
		else // Left 포인터를 오른쪽, Right 포인터를 왼쪽으로
		{
			std::cout << Nums[Left] << ", " << Nums[Right] << std::endl;
			--Right;
			++Left;
		}
	}

	return 0;
}

합이 5인 두 원소
-10, 15
-2, 7
-1, 6