투포인터 알고리즘(Two Pointers Algorithm) - c++

투포인터 알고리즘이란?

두 개의 포인터를 각각 이동시키면서 1차원 배열 안 특정 조건에 해당하는 값을 구하는 알고리즘입니다.

 

---

알고리즘의 이해

1차원 배열이 있고, 합이 5인 연속적인 부분 수열의 개수를 구하는 문제라고 가정해보겠습니다.

 

처음 두 개의 포인터는 인덱스 0에 위치해 있고, 각각 start, end 로 구분합니다.

↓ : start

↓ : end

 

↓↓

1

2

3

4

5

6

 

현재 두 포인터 모드 인덱스 0을 가리키고 있으므로 인덱스0부터 0까지의 합은 1입니다.

합을 5로 맞춰야하므로 end 포인터를 오른쪽으로 한 칸 이동시킵니다.

 

↓                ↓

1

2

3

4

5

6

현재 start의 인덱스는 0, end는 1을 가리킵니다.

인덱스 0부터 1까지의 합은 3.

end포인터를 오른쪽으로 이동 시킵니다.

 

↓                                     ↓

1

2

3

4

5

6

현재 start의 인덱스는 0, end는 2을 가리킵니다.

인덱스 0부터 2까지의 합은 6.

합 5를 초과했으므로 start 포인터를 이동시킵니다.

 

                    ↓                ↓

1

2

3

4

5

6

값을 확인해보니 합 5가 됐습나다.

합이 5인 연속적인 부분 수열 개수를 구하는 문제이므로 count를 해줍니다.

count=1

 

이런 식으로 end가 인덱스 끝에 도달할 때 까지 반복해주면 됩니다.

 

//count: 요구에 맞는 부분수열 개수를 저장하는 변수, sum: 연속적인 부분수열 합을 저정하는 변수
int count=0, sum=0;
int start, end; //투포인터

 start=end=0; //투포인터 초기화
 
for(;end<=N;) { //end포인터가 배열의 끝에 도달할 때 까지 반복
        
        if(sum > M) //연속적인 부분 수열 합이 요구 합 보다 클 때
            sum -= a[start++]; 
            //start포인터가 오른쪽으로 이동하기 전 가르켰던 곳에 있는 값을 빼주고 오른쪽으로 이동
        else if(sum < M)
            sum += a[end++];
        else {
            count ++;
             sum += a[end++];
        }
    }
    cout << count;

 

sum -= a[start++];

위 코드를 보던 중 이 문장이 익숙치 않는 분들에게 풀어서 설명해보겠습니다.

 

위 우선순위는 다음과 같습니다.

1. sum -=a[start]; 

start 포인터가 오른쪽으로 이동했으니 포인터가 전에 위치했던 값을 없애줘야합니다.

2. start++

1번을 완료한 뒤 start를 후위연산 시켜줌으로써 start포인터가 다음 인덱스를 가르키게 합니다.

 

---

투 포인터는 두 포인터 모두 오른쪽으로 이동하는 방법 외에도 인덱스 처음과 끝에 start, end가 위치하여 가운데 지점으로 만나는 형식도 있습니다. 문제에 따라 쓰이는 방법이 조금씩 다른데 원리는 같으니 여러 가지 문제를 풀어보며 익히는 것을 추천드립니다.