[알고리즘] - 투 포인터 (Two-Pointers)

1. 투 포인터 알고리즘 (Two - Pointers Algorithm)

투 포인터 알고리즘은 1차원 배열에서 활용할 수 있는 알고리즘이다.

배열에서 특정 원소를 가리키는 2개의 포인터를 사용하여 목표값을 찾는다.

이중 반복문을 이용하면 시간 복잡도가 O(n^2)이지만, 투 포인터 알고리즘을 이용하면 O(n)으로 해결이 가능하다. 

코딩테스트에서 자주 나오는 편은 아니지만 종종 사용되므로 알아두고 넘어가자.

 

---

2. 투 포인터 알고리즘 활용하기

N개의 자연수가 저장되어 있는 수열이 있다고 했을 때, 이 수열에서 연속된 특정 구간의 합이 K이 되는 부분을 찾고자 한다. 

예를 들어, 7개의 자연수가 들어있는 배열 arr에서 구간 합이 6인 경우의 수를 세어 보자.

N = 7 / K = 6

 

초기 설정

기본 알고리즘
arr[start] ~ arr[end] 까지의 합을 sum이라 했을때, 
1. sum > K인 경우 :  sum -= arr[start];   start++; 
2. sum < K인 경우 :  sum += arr[end];    end++;
3. sum = K인 경우 :  count++;     end++;     sum += arr[end];

 

 

STEP 1

현재 부분합은 1이다. 즉 목표값보다 작으므로 end를 증가시키고, end가 가리키는 값인 3을 sum에 더해준다.

그러면 부분합은 4가 된다. (부분합을 따로 반복문을 사용하여 구하지 않아도 되므로 효율적이다.)

 

 

STEP2

현재 부분합은 4이다. 즉 목표값보다 작으므로 end를 증가시키고, end가 가리키는 값인 2을 sum에 더해준다. 그러면 부분합은 6이 된다.

 

 

STEP3

현재 부분합은 6이다. 즉 목표값과 같으므로 count를 증가시키고, end를 증가시킨 후 end가 가리키는 값인 4을 sum에 더해준다. 그러면 부분합은 10이 된다.

 

 

 

STEP4

현재 부분합은 10이다. 즉 목표값보다 크므로 sum에서 현재 start가 가리키는 값인 1을 빼준 후 start를 증가시킨다. 그러면 부분합은 9가 된다.

 

 

STEP5

현재 부분합은 9이다. 즉 목표값보다 크므로 sum에서 현재 start가 가리키는 값인 3을 빼준 후 start를 증가시킨다. 그러면 부분합은 6이 된다.

 

 

STEP6

 

위와 같은 과정을 모든 경우를 찾을 때까지 반복한다. (end == n이거나 start > end 가 되면 반복문 종료)

 

 

---

투 포인터 활용 예제 코드

#include <iostream>
using namespace std;

int main()
{
	int n, k;
	n = 7;
	k = 6;
	int arr[7] = {1,3,2,4,2,1,5};
	int start = 0;
	int end = 0;
	int sum = arr[0];	//start와 end가 0번 인덱스이므로 sum의 초기값은 arr[0]
	int count = 0;

	while (end != 7) {
    
    		//구간합이 목표값 k와 같은 경우
		if (sum == k) {
			count++;
			end++;
			sum += arr[end];
		}
        
        	//구간합이 목표값 k보다 큰 경우 -> start가 가리키는 값을 sum에서 뺀 후 start 증가
		else if (sum > k) {
			sum -= arr[start];
			start++;
		}
        
        	//구간합이 목표값 k보다 작은 경우 -> end를 증가시킨 후 end가 가리키는 값을 sum에 더한다.
		else {
			end++;
			sum += arr[end];
		}

		if (start > end) {
			break;	//만약 start가 end보다 커진다면 반복문 종료
		}
	}

	cout << count;
}

출력 결과 정상적으로 count 되었다.