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

투 포인터란?

두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것

 

투 포인터의 특징

    1. 투 포인터 알고리즘은 선형시간 복잡도[ O(n) ]를 가지므로 효율적.

    2. 한 번의 반복으로 모든 요소를 처리하기에 효율적.

 

활용 예시

주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제

 

문제 : 갯수가 5개인 배열에서 구간합이 5인 구간을 찾기

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 A과 같다면 카운트한다.
3. 현재 부분 합이 A보다 작다면 end를 1 증가시킨다.
4. 현재 부분 합이 A보다 크거나 같다면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.

 

1. 5개의 배열

 

 

 

2. start, end는 배열의 시작점에서 동시에 출발

    S=0, e=0, sum=1, cnt=0

 

 

 

3. e를 한칸씩 움직여 S~e의 구간합을 구한다.

sum = A[0] ~ A[1] = 3

sum = A[0] ~ A[2] = 6

 

 

4. 구간합이 6이므로 찾고자하는 5를 넘긴다. 따라서 값을 줄이기 위해 
   시작값인 S를 한칸 올린다. 
   5를 찾았으므로 cnt를 1증가시킨다.

sum= A[1]~A[2]=5, cnt=1

 

 

 

5. 위의 작업을 반복 후 최종

sum= A[5]~A[5]=5, cnt=1+n

int end = 0;
int sum = 0; // 부분 합
int cnt = 0; // 개수 

// i 가 start
for (int i = 0; i < n; i++) {
    while (end < n && sum < m) {
        sum += arr[end];
        end++;
    }

    if (sum == m) {
        cnt++;
    }

    sum -= arr[i];
}