[투 포인터] c++구현 및 백준 2003 예제 설명

목차

 

투 포인터 알고리즘 정의

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.

 

대표 예제

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

2003번: 수들의 합 2

 

 

투 포인터 알고리즘 설명

크게 4가지 절차를 알면됩니다.

 

1. 목표값보다 작으면 종착점을 증가시킨다.
2. 목표값보다 크면 시작점을 증가시킨다.
3. 종착점이 끝에 도달하면 목표값에 상관없이 시작점을 증가시킨다.
4. 시작점이 끝에 도달하면 종료한다.

목표값 = 2라고 해봅시다.

sum: 0 / 시작점: 0 / 종착점: 0

sum: 1 / 시작점: 0 / 종착점: 1

sum: 2 / 시작점: 0 / 종착점: 2 / cnt++

sum: 1 / 시작점: 1 / 종착점: 2

sum: 2 / 시작점: 1 / 종착점: 3 / cnt++

sum: 1 / 시작점: 2 / 종착점: 3

sum: 2 / 시작점: 2 / 종착점: 4 / cnt++

sum: 1 / 시작점: 3 / 종착점: 4

sum: 0 / 시작점: 4 / 종착점: 4

 

cnt =3

 

코드구현

#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
int main() {
	int N, M, i, num, cnt =0, s=0, e=0, sum=0;
	cin >> N >> M;

	for (i = 0; i < N; i++) {
		cin >> num;
		arr.push_back(num);
	}

	while (s < N) {

		if (sum < M) {
			if (e != N ) { // 종착점이 끝에 도달 시 
				sum += arr[e];
				e++;
			}
			else {    // 합이 목표값보다 작은 경우 종착점 증가
				sum -= arr[s];
				s++;
			}
		}
		else {  //합이 목표값보다 크거나 같은 경우 시작점 증가
			sum -= arr[s];  
			s++;
		}
		
		if (sum == M)   //합이 목표값인  경우 카운트 증가
			cnt++;
	}
	cout << cnt;

}

 

참고

https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)