15. 투 포인터 (Two pointers method, c++)

투 포인터 (Two pointers method)?

개별적인 연산에 중점을 두지 않고 알고리즘이 실행되는 전체 시간을 측정하는 방식 중의 하나입니다.

 

두개의 포인터로 배열의 값들을 순회하는 방법으로, 두 포인터는 한방향으로 움직일 수도 있고 서로 반대방향으로 움직일 수도 있습니다.

---

Subarray sum

 

n개의 양의 정수로 이루어진 배열이 있고 x 라는 값을 만들 수 있는 부분 배열을 찾는 문제가 있습니다.

 

예를 들면, { 1, 3, 2, 5, 1, 1, 2, 3 } 이라는 배열이 있고 여기서 8을 만들 수 있는 subarray를 찾아야합니다.

 

이러한 문제는 모든 부분 배열을 검사하지 않아도, 투 포인터로 O(N)에 해결할 수 있습니다.

 

이 문제에서 두개의 포인터(left, right)는 각각 부분배열의 시작과 끝을 의미합니다.

 

그리고 두 포인터 모두 왼쪽에서 오른쪽으로 이동하면서 부분배열의 합(sum)을 계산할 것입니다.

 

만약 sum이 x보다 작다면 right 포인터를 증가시켜 합을 키워보고 x보다 크다면 left 포인터를 증가시켜 합을 줄여봅니다.

 

이러한 과정을 반복하며 x를 찾게되면 정답이 구해지는 것입니다.

subarray	left pointer index	right pointer index	sum
{ 1 }	1	1	1
{ 1, 3 }	1	2	4
{ 1, 3, 2 }	1	3	6
{ 1, 3, 2, 5 }	1	4	11
{ 3, 2, 5 }	2	4	10
{ 2, 5 }	3	4	7
{ 2, 5, 1 }	3	5	8

 

left, right 포인터 모두 N번 움직일 수 있습니다. 그러므로 O(N)에 수행되는 알고리즘입니다.

---

2SUM Problem

2SUM 문제는 N개의 숫자로 이루어진 배열과 찾아야하는 숫자 x가 주어지고, array의 두가지 요소를 뽑아 x를 만드는 경우를 찾는 문제입니다.

 

예를 들면, { 1, 4, 5, 6, 7, 9, 10 } 이라는 배열이 있고 합이 12가 되는 경우를 찾아야합니다.

 

이러한 문제도 투 포인터를 이용해 O(NlogN)에 해결할 수 있습니다.

 

이 문제를 해결하기 위해서는 우선 배열을 오름차순으로 정렬해야합니다.

 

이후 왼쪽에서 오른쪽으로 이동하는 포인터 하나(left)와 오른쪽에서 왼쪽으로 이동하는 포인터 하나(right)를 사용합니다.

 

각각의 포인터는 현재 탐색중인 array의 요소를 의미합니다.

 

left 포인터는 가장 작은 수에서 시작할 것이고 right 포인터는 가장 큰 수에서 시작할 것입니다.

 

x와 일치하는 sum을 찾을 때 까지, 두 수의 합(sum)이 x보다 크다면 left 포인터를 증가시켜 sum을 키워보고 x보다 작다면 right 포인터를 감소시켜 sum을 줄입니다. 

 

SUM	left pointer index	right pointer index
11	1	7
14	2	7
13	2	6
11	2	5
12	3	5

 

투 포인터를 사용한 문제해결은 O(N)이지만 정렬에 O(NlogN)이 소요되는 방식입니다. 물론 단순히 binary search를 이용해서도 이 문제를 해결할 수 있습니다.

 

이 해결법을 응용하면 3SUM 문제를 O(N^2)에 해결할 수 있습니다. 

 

3SUM 문제는 3개의 수를 뽑아 합이 x가 되는 경우를 찾는 문제입니다.

 

마찬가지로 오름차순으로 정렬한 뒤 맨 앞 숫자부터 하나를 고정하고(O(N))나머지 범위에 대해 2SUM 문제를 푸는 방식(O(N))을 사용할 수 있습니다.