[ 알고리즘 ] 투포인터 ( Two Pointer )의 이해 및 구현

투 포인터(Two Pointer)란?

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 두 개의 포인터를 만들어 각각이 가리키는 원소에 의미를 부여해 요구하는 문제를 해결하는 알고리즘
• 포인터 2개가 같은 방향으로 진행해 나가는 것 , 포인터 2개가 양끝에서 반대로 진행해 나가는 것, 포인터 하나는 한쪽으로 이동하고 다른 포인터는 양쪽으로 이동하는 것 등이 대표적 예시이다.

 

대표 문제 풀이

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

2003번: 수들의 합 2

특정한 합을 가지는 부분연속수열의 개수 찾기

 

1 . 문제 해결 아이디어

  -1. start와 end가 첫번째 인덱스(0)을 가르킨다.

  -2. 현재 부분합이 m보다 작다면 end를 1 증가한다.

  -3. 현재 부분합이 m보다 크거나 같다면 start를 1 증가한다.

  -4. 2~3번 과정을 모든 경우를 확인할 때까지 반복한다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, m, e, ans,nowSum; // n : 수열의 길이 , m : 원하는 합
int A[10001];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> A[i];
	
	for (int start = 0; start < n; start++)
	{
		//end 이동
		while (nowSum < m && e < n)
		{
			nowSum += A[e];
			e++;
		}
		//부분합이 m
		if (nowSum == m)
			ans++;
		nowSum -= A[start]; //
	}

	//output
	cout << ans;
	return 0;
}