[알고리즘] Two Pointers

투 포인터

1차원 배열에서 위치를 담은 두 포인터를 이동시키면서 최적의 답을 찾는 알고리즘
두개의 배열에서 각 배열이 가진 하나의 포인터를 이동시키기도 한다.

두 포인터의 위치는 보통 두가지로 나뉜다.

1. start - 처음, end - 처음
   → start, end를 한 칸씩 뒤로 이동 ⇒ start > end 또는 end가 범위를 벗어나면 종료
2. start - 처음, end - 끝
   → start는 뒤로 end는 앞으로 이동 ⇒ start > end 종료

⇒ 조건에 맞는 효율적인 방법을 쓰자.

연속된 부분 수열의 합 문제에서 투 포인터 사용 유무에 따른 시간복잡도를 비교해보자.

無 - 이중 for문

 #include <string>
 #include <vector>
 
 using namespace std;
 
 vector<int> solution(vector<int> sequence, int k) {
     vector<int> answer;
     answer.push_back(sequence.size());
     answer.push_back(sequence.size()*2);
     
     for(int i=0; i<sequence.size(); i++){
         int sum = 0;
         if(sequence[i] > k)
             break;
         for(int j=i; j<sequence.size(); j++){
             sum += sequence[j];
             if(sum > k)
                 break;
             
             if(sum == k){
                 if(answer[1]-answer[0] > j-i){
                     answer[0] = i;
                     answer[1] = j;
                 }
                 else if(answer[1]-answer[0] == j-i && answer[0] > i){
                     answer[0] = i;
                     answer[1] = j;
                 }
             }
         }
     }
     
     return answer;
 }

항상 O(N^2)

有 - 투 포인터

 #include <string>
 #include <vector>
 
 using namespace std;
 
 vector<int> solution(vector<int> sequence, int k) {
     int size = sequence.size();
     vector<int> answer = {size, size*2};
     int start = 0, end = 0;
     int sum = sequence[0];
     
     while(start <= end && end < size){
         if(sum < k){
             sum += sequence[++end];
             continue;
         }
         else if(sum == k){
             if(answer[1]-answer[0] > end-start){
                 answer[0] = start;
                 answer[1] = end;
             }
         }
         sum -= sequence[start++];
     }
     
     return answer;
 }

최악의 경우에도 O(N*2)

참고: https://www.geeksforgeeks.org/two-pointers-technique/

두 배열이 각각 하나의 포인터를 가질 수도 있고
배열의 부분합을 구할 수도 있고
두 포인터가 가리키는 원소의 쌍을 찾을 수도 있는 등
투 포인터는 활용이 매우 다양해서 개념을 이해하고 문제에서 마주할 때 꺼내 써야겠다.