[알고리즘] 투 포인터 (Two pointer)

 

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

 

 

---

 

투 포인터는 두 가지 상황에서 많이 쓴다.

 

1. 특정 조건을 만족하는 두 수를 찾을 때.

2. 특정 조건을 만족하는 구간을 찾을 때.

+ 정렬된 두 배열을 합칠 때 + merge sort (드문 케이스)

 

---

1. 특정 조건을 만족하는 두 수를 찾을 때.

예시 문제)  3273번: 두 수의 합 (https://www.acmicpc.net/problem/3273)

1번 예제 (변형)

9
5 12 7 10 9 1 2 14 11
13

 

 

문제에서 n이 최대 100,000이기 때문에 완전 탐색을 이용해서 문제를 푼다면 시간 복잡도는 O(n^2)으로 

최대 10,000,000,000 (100억)번 연산해야하기 때문에 시간 초과가 발생하게 된다.

 

이 문제는 1번 상황인 "특정 조건을 만족하는 두 수 찾기"이므로 일단 정렬을 해본다

 

5 12 7 10 9 1 2 14 11

====================

1 2 5 7 9 10 11 12 14

 

 

다음은 두 포인터라는 이름답게 두개의 점을 둔다

[s, e] => 정답 후보의 범위

1 2 5 7 9 10 11 12 14
s
                    e

 

arr[s] + arr[e] = 15가 되는데, 이는 우리가 원하는 13보다 크다.

 

따라서 원하는 값을 맞춰주기 위해서 e를 앞으로 한칸 옮겨준다.

1 2 5 7 9 10 11 12 14
s
                 e

 

 

이를 s와 e의 입장에서 봐보자.

s의 입장 : 정답 후보 중 제일 큰 값과 더했다.

e의 입장 : 정답 후보 중 제일 작은 값과 더했다.  => 제일 작은 값과 더했는데도 답보다 크다.

               == 다른 누구와 더해도 절대 답이 될 수 없다.

 

결론적으로

e를 앞으로 한칸 옮기는 것은 더하는 값을 바꾼다 라는 의미가 아니라,

14를 정답 후보에서 제외한다. 라고 이해해야 한다.

(물론 e를 앞으로 한칸 옮기는 것이 틀린 말은 아니지만, 앞으로의 문제 해결을 위해서 정답 후보 제외로 이해하는 것이 좋다.)

 

 

원하는 값인 13이 되었으므로, 이번엔 s 위치의 값을 정답 후보에서 제외한다.

 

1 2 5 7 9 10 11 12 14
  s
                 e

 

arr[s] + arr[e] = 14가 되었으므로 e 위치의 값을 정답 후보에서 제외한다.

(e 위치의 12가 그 어느 것과 더해도 13이 될 수 없으므로 정답 후보에서 제외)

 

 

1 2 5 7 9 10 11 12 14
  s
             e

 

위와 같은 과정을 반복하면서 연산을 진행하는 것이 투포인터의 기본 개념이다.

 

 

투포인터 구현

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> vec;

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

	}

	int x;
	cin >> x;

	int s = 0;
	int e = n - 1;

	int cnt = 0;
	while (s < e) // s와 e가 만나기 전까지 반복
	{
		if (vec[s] + vec[e] == x)
		{
			cnt++;
			s++;
			e--;
		}
		else if (vec[s] + vec[e] < x) s++;
		else e--;
	}

	cout << cnt;
	
	return 0;
}

 

투포인터는 한 연산에 진행하는 것이, 비교와 해당 인자를 정답후보에서 제외하는 것이 전부이므로 시간 복잡도가 O(n)이 된다.

(n번 연산 후에는 정답 후보가 없음 => 정답 구함.)

 

[정리]
1. s = 0, e = n - 1에서 출발한다.
2. s, e가 만날 때까지
3. s, e 중 정답 후보에서 빠져야 하는게 있다면 그것을 지운다.

 

 

---

 

2. 특정 조건을 만족하는 구간 구하기. (연속 부분 수열)

예시문제) 2003번 : 수 들의 합 2 (https://www.acmicpc.net/problem/2003)

10 5
1 2 3 4 2 5 3 1 1 2

 

 

이 문제를 완전탐색을 진행한다면

다음과 같은 코드로 정답을 찾게 된다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

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

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int total = 0;
		for (int j = i; j < n; j++)
		{
			total += vec[j];
			if (total == k) cnt++;
		}
	}

	cout << cnt;

	return 0;
}

 

 

모든 인자가 양수이기 때문에 total이 k를 넘어선다면 break를 하는 식으로 최적화를 할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

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

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int total = 0;
		for (int j = i; j < n; j++)
		{
			total += vec[j];
			if (total == k) cnt++;
			else if (total > k) break;
		}
	}

	cout << cnt;

	return 0;
}

 

 

 

여기서 생각을 조금만 더 해본다면 break가 발생한 시점에 j를 i + 1자리로 가져오는 작업의 필요성에 대해 생각해볼 수 있다.

1 1 1 3 1 3 4 2 5 3 1 1 2
i   
      j

 

=>  i ~ j의 값이 5를 넘긴 시점,

j를 2번 인덱스로 옮겨봤자 부족한 값일 것이 분명하기 때문에 j는 그대로 둔채 i만 오른쪽으로 한칸 이동하면 최적화된 연산을 할 수 있다.

 

여기서 i와 j의 변수명만 s, e로 바꾸고 구현을 하면 투 포인터가 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> vec;
	int temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		vec.push_back(temp);
	}
	// e++를 하고 vec[e]를 더해주기 때문에.
	// range에러가 발생한다. 따라서 이를 막아주기 위해,
	// 의미가 없는 값인 0을 더해주었다.
	vec.push_back(0);

	int s = 0;
	int e = 0;
	int total = vec[0];

	int cnt = 0;
	while (e < n)	// 구간 내라면,
	{
		if (total < k)
		{
			e++;
			total += vec[e];
		}
		else if (total > k)
		{
			total -= vec[s];
			s++;
		}
		else
		{
			cnt++;
			total -= vec[s];
			s++;
			e++;
			total += vec[e];
		}
	}

	cout << cnt;

	return 0;
}

 

 

정리
1. s = 0, e = 0에서 출발 (0번만 들어있는 구간을 생성해서 시작한다.)
2. e < n : 정상적인 구간이라면 반복한다.
3. 구간을 늘려야한다면 e++, 구간을 줄여야한다면 s++