[Algorithm] 투 포인터(two pointer) 완.전.정.복

투 포인터(two pointer)란?

- 투 포인터란, 배열에서 필요한 목표에 도달하기 위해, 두 개의 점을 순차적으로 이동하면서 목표에 도달하는지 확인하는 알고리즘입니다. 여기서 포인트는 바로 두 개의 점! 투 포인터라는 알고리즘의 이름을 갖게 한 핵심 원리입니다.

 

1

2

3

4

5

                 start                                                                      end

 

위에서 보시는 것처럼, start와 end가 바로 투 포인터의 핵심 역할을 진행합니다. 현재는 start가 1, end가 3을 가리키는데 특정 조건을 걸어서 조건을 이행하며, start와 end를 이동시켜 원하는 값을 구하도록 합니다. 

 

??? : "투 포인터보다, 이중 반복문을 사용해서 두 개의 점을 이동시키는 것은 안되나요? 이중 반복문은 모든 경우의 수를 볼 수 있잖아요?"

- 매우 좋은 지적입니다. 이중 반복문을 이용한다면, 모든 경우의 수를 볼 수 있습니다. 하지만, 시간복잡도는 O(N^2)이 되어, 모든 경우의 수가 많은데 제한 시간이 짧다면 이용하기 어렵겠죠. 그리고 두 개의 점을 이용하여 원하는 값에 도달하기 위해서는 모든 경우의 수를 볼 필요가 없습니다.

-> ⭐따라서 주어진 시간복잡도가 짧고, 두 개의 점을 이용한 목표값이 있다면? 투 포인터를 사용!⭐

 

투 포인터의 예시 문제

2003번: 수들의 합 2

 

매우매우 대표적인, 다른 two pointer 알고리즘을 설명하는 블로그에서도 대표적으로 뽑는 문제입니다. 그만큼 위 문제는 투 포인터를 설명하기에 매우 적합한 문제입니다. 투 포인터가 사용되기 적합한 조건이죠.(0.5초의 짧은 제한 시간, i와 j라는 두 개의 점을 이용)

문제를 읽으시고, 괄호에 설명된 두 개의 조건으로 투 포인터를 떠올리시면, 이 문제는 이미 푸신거나 다름없습니다. 핵심 알고리즘을 찾았으니 조심해야할 부분 몇 가지만 찾으시면 됩니다!

 

point_sum라는 start point에서 end point까지의 총합을 두고, 두 포인트를 이동시키며 M과 같은 갯수를 찾으면 된다!

나머지 설명은 주석으로 추가하겠다.

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;
	vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
	}
	int startp = 0, endp = 0, num = 0;;
	int point_sum = vec[0];

	while (endp < N) { // endp가 배열의 크기를 넘기면 안된다.
		if (point_sum > M) {
			point_sum -= vec[startp]; 
			startp++;
		}// point_sum에서의 startp 원소를 빼준 후, startp의 포인트를 한칸 앞으로
		else if(point_sum < M) {
			endp++;
			if (endp < N)
				point_sum += vec[endp];
		}// point_sum에서 endp를 한칸 앞으로 이동 후, 총합에 더한다.
		else {
			num++;
			point_sum -= vec[startp];
			startp++;
			endp++;
			if (endp < N)
				point_sum += vec[endp];
		}// 같을 경우, num이라는 M과 같은 합의 개수에 추가, startp와 endp를 한칸씩 앞으로
	}

	cout << num;

	return 0;
}

위 사진은 작성한 코드로 푼 풀이 : 시간이 0ms인 것을 알수 있다.

아래 사진은 이중 반복문으로 푼 풀이 : 시간이 24ms, 위 사진과 매우 많은 차이가 발생한다.

(파이썬이었으면 아마 틀렸을거다..)

코드 리뷰는 언제나 환영입니다!