[투 포인터 알고리즘][1] - 개요 및 백준1806번

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

투 포인터 알고리즘은 선형자료구조에서 특정부분집합을 빠르게 찾아낼때 사용된다.

 

예를 들어 다음 문제를 보자.

 

---

백준 1806번 - 부분합

 

위 문제같은 경우 N = 100000 일때 모든 부분합의 개수는 N^2 으로 많은 시간이 소요된다.

 

그렇다고 메모이제이션을 하기에는 부분합인 S의 범위가 1억이하이므로 메모리상으로도 초과가 발생한다.

 

이때 사용할 수 있는 알고리즘이 투 포인터 알고리즘 이다.

 

다음과 같은 배열에서 합이 10이상이되는 가장 짧은 길이를 구해보자.

 

먼저 우리가 찾을 부분배열의 시작 인덱스를 start, 마지막 인덱스를 end라고 하자.

 

처음에는 두값모두 0이다.

 

 

이후 현재 부분배열의 합이 S(10) 이상이 아니라면 end++ 하여 진행한다.

 

 

 

end가 2가 되었을때 부분합이 10이상이 되었다.

 

현재까지의 최소길이는 3이며 이후부터는 end값과 동시에 start값도 같이 늘려준다.

 

 

위의 붉은 네모박스를 한칸씩 오른쪽으로 이동한다고 보면 된다.

 

또한 한번 이동한 후 아래와같은 로직으로 반복한다.

 

if ( start 에 있는 값을 뺐을때 S이상이 되는가? )

True-> start값을 빼고 최소길이 최신화 및 start++ -> if문으로 다시이동

False -> start++ end++

 

 

 

아래와같은 경우 위의 로직에서 True에 해당되며 최소길이가 갱신된다.

 

 

 

 

 

이렇게 진행하게되면 최소길이가 1이라는것을 알아낼수 있다.

 

이 알고리즘의 시간복잡도는 2n으로 O(N)이다.

 

 

#include <iostream>

using namespace std;

int n,target;
int p[100001];

int main(){
    cin >> n >> target;
    for(int i=0;i<n;i++){
        cin >> p[i];
    }

    int minimum = 99999999; // 합이 S이상인 것중 가장 짧은 길이
    bool notFound = true;
    bool tmp = true;
    int total = 0;
    int s,e;
    s = 0;
    for(int i=0;i<n;i++){ // i 번째를 마지막으로 한 부분합
        if(notFound){ // 합이 S이상인것을 못찾았을때
            total = total + p[i];
            if(total >= target){ // 처음으로 합이 S이상인 것을 찾았을때
                minimum = i-s+1;
                notFound = false;
            }
        }
        else{
            total = total - p[s] + p[i]; // 현재 길이가 x인것을 찾았는데 그 이후로는 길이가 x이상인것은 찾을 필요가 없다.
            s = s + 1;
        }
        if(total >= target){ // 만약 minimum 개씩 합을 확인하다가 타겟보다 커지면
            tmp = true;
            while(tmp){ // 가장 왼쪽부터 하나씩 빼면서 최소길이를 구한다.
                if(total - p[s] >= target){
                    total = total - p[s];
                    s = s + 1;
                    minimum = minimum - 1;
                }
                else{
                    tmp = false;
                }
            }
        }
    }
    if(minimum >= 99999999){
        cout << 0;
    }
    else{
        cout << minimum;
    }
}

---

Q. 투 포인터 알고리즘이 과연 모든 경우의수를 고려했다고 볼 수 있나?

위 알고리즘에 따르면 end값은 인덱스 0부터 n-1 까지 진행된다.

 

다르게 생각하면 한 Loop를 돌때마다(end값이 증가될때마다 하나의 Loop라고 가정) end값을 인덱스로 할때 길이가 S이상이 되는 최소길이를 구한다고 생각할 수 있다.

 

모든 경우의 수들은 항상 end를 마지막 인덱스로하는 집합에 속하므로 모든 경우의수를 고려한다고 볼 수 있다.

 

또한 처음으로 S이상이 되는 부분합을 찾았을 때 그 이후로 start 와 end 값을 동시에 ++하는 이유는 이미 합이 S이상이 되는 길이 k를 찾았는데 굳이 end값만 ++해서 길이가 k+1 이 되는 경우는 굳이 고려할 필요가 없기때문이다. 따라서 이미 길이가 k인 부분합을 구했으면 계속 k기준으로 부분합을 구하다가 더 짧아질수 있다면 길이를 최신화하는 방향으로 진행한 것이다.