[Algorithm] 투 포인터 알고리즘

조재훈·2025년 5월 28일

algorithm

투 포인터 알고리즘

투 포인터 알고리즘이란?
두 개의 포인터를 이용해 배열이나 문자열을 탐색하며 문제를 해결하는 알고리즘

보통 일차원 자료구조에서 특정 조건을 만족하는 연속 구간을 구할 때 O(N)의 시간 복잡도로 문제를 해결하기 위해 많이 사용되는 기법이며 코딩 테스트에서도 자주 등장하는 알고리즘이다

보통 이중루프로 풀어야 할 것 같은데 입력값이 커서 시간 초과가 날 것 같을 때 투 포인터 알고리즘을 떠올리면 대부분 풀어지더라

이와 비슷한 알고리즘 기법인 슬라이딩 윈도우도 있는 데 차이는 투 포인터는 구간이 가변적이며 슬라이딩 윈도우는 구간이 고정적이다. 자세한 건 다음 포스팅에서 다뤄보자

대부분 투 포인터 알고리즘은 인덱스를 나타내는 포인터인 left와 right를 사용하며 문제의 유형은 다음과 같다

포인터 2개가 같은 방향으로 진행
포인터 2개가 양 끝에서 시작해 서로를 향해 다가오며 진행
포인터 하나는 단방향으로 진행하고, 다른 포인터는 양쪽으로 이동

백준 2003번 : 수들의 합 2

간단하고 대표적인 투 포인터 문제이다

시간 제한이 0.5초이고 배열의 길이는 10000까지이며 구간 [i, j] 내의 값들의 합이 M이 되는 경우를 찾아야 한다

만약 투 포인터를 안 쓸 경우 이중루프를 통해 구해야 되는데 바로 시간 초과가 뜬다

코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
int arr[10004];
int answer;

void Input() 
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
}

void Solve()
{
	int left = 0, right = 0;
	int sum = arr[0];

	while (right < N)
	{
		if (sum == M)
		{
			answer++;
			sum += arr[++right];
		}
		else if(sum > M)
		{
			sum -= arr[left++];
		}
		else if (sum < M)
		{
			sum += arr[++right];
		}
	}

	cout << answer;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Input();
	Solve();

	return 0;
}