[알고리즘] 두 포인터

 

1. 두 포인터란?

포인터 두 개를 사용하여 배열이나 문자열을 탐색하는 알고리즘이다.

흔히 배열을 탐색하다 보면 완전탐색을 진행할 경우 O(N²)의 시간복잡도를 가진다. 하지만 투 포인터를 이용하면 동시에 포인터 두 개로 탐색하므로 O(N)의 시간 복잡도로 한 번에 탐색할 수 있다.

예시

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

2230번: 수 고르기

 

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

int N, M, arr[100000], ans;

int main(void) {
	ans = 100000000;
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)	{
		for (int j = i; j < N; j++) {
			int temp = arr[j] - arr[i];
			if (temp >= M) ans = min(ans, temp);
		}
	}
	cout << ans;
	return 0;
}

시간 복잡도를 보면 O(N²)이 된다. 하지만 두 포인터를 이용하면 O(N)해결할 수 있다.

 

3. 두 포인터와 이분 탐색

두 포인터로 해결할 수 있는 문제는 이분 탐색으로도 해결할 수 있고 그 반대도 가능하다. 따라서 두 가지 모두 익혀두는 것이 좋다.