투 포인터

투 포인터란?

먼저 투 포인터(two pointer)에서 포인터는 예전에 학교에서 공부한 포인터 개념이 아니라 현재 배열이나 수열에서 특정 위치를 가리키는 '인덱스 역할'의 변수를 말한다.
이 알고리즘은 정렬된 배열이나 수열에서 특정 조건을 만족하는 구간이나 쌍을 찾을 때 유용하게 사용된다.

• 예시 문제
  길이가 n인 수열이 주어진다. 이 수열에서 연속된 구간의 합이 m이 되는 경우 중 길이가 가장 짧은 구간의 길이를 출력하라.
  단, 그런 구간이 없다면 -1을 출력한다.

n = 5, m = 9
수열: {1, 2, 5, 4, 3}일 때 알고리즘은 다음과 같이 동작한다.

그림과 같이 st(start), en(end) 두 개의 포인터를 이용해 구간을 정의한다.
en을 오른쪽으로 이동시키면서 누적합을 키워가고 합이 m 이상이 되면 st를 이동시키면서 합을 줄인다.
이렇게 누적합이 m이 되는 경우에 값을 갱신하며 최단 길이를 찾을 때 까지 반복한다.

코드

#include <bits/stdc++.h>
using namespace std;

int a[100002];
int n, m;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> a[i];
	
	int en = 0;
	int result = 0x7fffffff;
	int sum = a[0];
	for(int st=0; st<n; st++)
	{
		while(en < n && sum < m)
		{
			en++;
			if(en != n) sum += a[en];
		}
		if(sum == m) result = min(result, en-st+1);
		sum -= a[st];
	}
	
	if(result == 0x7fffffff) cout << -1;
	else cout << result;
	
	return 0;
}

마무리

투 포인터는 생각보다 간단한 방식이지만 조건을 어떻게 설정하고 포인터를 어떻게 움직일지에 따라 난이도가 크게 달라진다. 특히 연속된 구간을 다루는 문제에서 유용하며, 일부 문제는 이분 탐색으로도 해결할 수 있다.

아직 투 포인터 관련 문제를 많이 풀어보지 않았다면, 다양한 유형을 접해보며 감을 익히는 것이 중요하다. 더 나아가 슬라이딩 윈도우(sliding window) 방식과도 유사한 개념이므로, 같이 익혀두면 좋다.



Reference
[실전 알고리즘] 0x14강 투 포인터 - BaaaaaaaarkingDog