투 포인터 알고리즘 (Two pointer Algorithm)

투 포인터 알고리즘 (Two pointer Algorithm)

---

 개요 

  위와 같은 Array 에 대해서 array[0] + array[1] + ... + array[k] 의 값이 20이 넘을 때 k의 최소값을 구하라고 한다면, 위 주황색 포인터를 계속해서 1씩 증가시켜 가면서 20이 처음으로 넘는 index를 찾게 될 것 이다. 위의 경우 이 때의 정답은 5이다. 

 

  이 경우는 사실 많이 기초적이며 array에 대해서 이해를 하려고 공부를 할 때나 다루는 부분일 것이며 대부분의 사람들이 생각할 수 있을 것 이다.

 

  그렇다면, 위와 같은 Array 에 대해서 부분합인 array[k] + array[k + 1] + ... + array[n] 의 값이 6에 해당이 되는 index가 연속되는 부분집합의 개수를 구하라면 과연 어떻게 해야할까?

 

  이런 문제에 대해서 투 포인터 알고리즘 (Two pointer Algorihtm) 을 사용할 수 있다.

---

 설명 

 

  위 Array 에서 연속된 수들의 부분합이 11인 부분집합의 개수를 찾아본다고 하자. 육안으로 보면 대강 파악할 수 있다.

 

{ array[0], array[1] }

{ array[4], array[5] }

{ array[11], array[12], array[13] }

...

 

등이 보인다. 하지만 육안으로 확인하는 것은 위와 같이 단순한 Array에 대해서만 가능할 뿐 10만, 100만의 크기를 가지는 Array 에 대해서 위와 같은 부분집합의 개수를 찾기 위해 우리는 투 포인터를 사용한다.

 

  투 포인터는 위와 같이 두 개의 포인터 (주황색 화살표, 파란색 화살표) 를 사용한다. 초기에는 left 와 right 모두 index 0 에 해당되도록 초기화를 시킨다.

 

  이 left, right pointer 가 정의하는 부분집합은 { array[left], array[left + 1], ... , array[right - 1], array[right] } 가 된다. 따라서 이 때 우리는 { array[0] } 부분집합을 하나 체크 하였다. 이 때, 이 부분집합의 부분합은 4이다. 우리는 11인 경우를 찾아야 하므로 부분집합의 개수를 늘림으로써 부분합을 증가시켜야 한다. 이를 위해서 right pointer 를 우측으로 한 칸 이동시킨다.

---

 

  left pointer와 right pointer 는 부분집합 { array[0], array[1] } 를 가리킨다. 이 때 이 부분집합의 부분합은  6 이다. 구하고자 하는 11보다 작으므로 다시 right pointer 를 우측으로 한 칸 이동시켜서 부분집합의 개수를 늘린 후 부분합을 다시 측정을 해 본다.

---

 

  위 두 pointer 는 { array[0], array[1], array[2] } 부분집합을 생성하며, 이 때의 부분합은 11이다. 부분합이 11인 부분집합 하나를 구했다. 다시 right pointer 를 우측으로 이동 시킨다. 이 때, 우측으로 이동시키면 당연히 부분합이 11인 지금보다 부분합이 큰 부분집합이 생성이 될 것 이다. 이 때에는 부분집합에서 원소를 하나 빼야하는데, 연속적인 원소들로 이루어진 부분집합 이기에 가장 좌측에 해당되는 부분집합을 빼야한다. 따라서 left pointer 도 우측으로 이동을 시킨다.

---

 

  이동시킨 결과, 이 때의 부분합은 10 으로 11보다 작다. 그래서 다시 right pointer 를 이동시켜야 한다.

 

  이렇게 계속해서 상황에 맞게 right pointer 와 left pointer 를 이동시킨다. 그렇게 하면 결국 위 case 는 마지막에 아래와 같이 된다.

---

  현재 두 pointer 가 가리키는 부분집합의 부분합은 11보다 작다. 따라서 right pointer 를 우측으로 이동시켜야 한다. 하지만, right pointer 는 더이상 갈 index 가 존재하지 않는다. 따라서 모든 작업이 종료가 된 것 이다. 

 

  right pointer는 Array 의 첫 번째 index 에서 마지막 index 까지 이동을 하였다. 따라서 O(N) 의 Time complexity 가 소요가 된다.

 

  left pointer는 Array 의 첫 번째 index 에서 마지막에 가까운 index 까지 이동을 하였다. 이는 구하고자 하는 부분합의 값에 따라 left pointer 가 끝날 때 있는 index의 값은 다를 것 이며, 가장 최악의 조건으론 left pointer 또한 마지막 index 까지 이동하여 O(N) 의 Time complexity 가 소요가 될 것 이다.

 

  따라서, 결국 O(2N)의 Time complexity 가 소요가 된다.

 

  예를 든 경우는 투 포인터를 이용한 가장 보편적인 문제를 예로 들었다. 이 투 포인터를 활용하여 풀 수 있는 문제들에 대해서, 그 문제가 요구하는 사항에 맞게 조금씩 변화를 주어 풀면 될 것 이다.

---

 Code 

#include <iostream>

using namespace std;

int main() {
	int n = 14, target = 12;
	int arr[14] = { 4, 2, 5, 3, 2, 4, 2, 7, 1, 5, 2, 3 ,2, 1 };

	int left = 0, right = 0; // 두 pointer 는 0'th index 에서 시작한다. 
	int sum = arr[0]; // 부분합을 구하기 위한 변수
	int count = 0; // target 값을 가지는 부분집합의 개수

	while (right < n) {
		//printf(" left = %d, right = %d : sum = %d\n", left, right, sum);
		if (sum < target) {
			sum += arr[++right];
		}
		else if (target < sum) {
			sum -= arr[left++];
		}
		else { // target == sum
			count++;
			sum += arr[++right];
		}
	}
}