[알고리즘] 두 포인터(Two-pointer)

두 포인터(Two-pointer)란?

두 포인터(Two Pointer)는 두 개의 포인터를 사용하여 문제를 해결하는 알고리즘 기법이다. 두 포인터는 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 구간이나 조합을 찾는 문제에서 활용한다. 문제 유형으로는 부분합 찾기나 두 수의 합 등이 있다.

 

주 목표는 최적화

두 포인터는 다른 알고리즘이랑 느낌이 살짝 다르다. 다른 알고리즘들은 특정 문제를 해결하기 위해 사용한다면, 두 포인터는 해결 가능한 문제의 시간복잡도를 줄이기 위해 사용한다. 즉, 최적화를 위한 알고리즘이며 일반적으로 O(N^2) -> O(N)으로 줄이는 것이 목표다.

 

동작방식

두 포인터를 사용하는 상황은 다양하다. 아래 예제는 합이 9가 되는 구간을 찾는 경우이다.

 

 

1. 초기화 

시작과 끝을 가리키는 두 개의 포인터를 배열의 특정 부분에 위치시킨다. 해당 예제에서는 둘 다 시작 부분에 위치시킨다.

 

2. 포인터 이동

각 포인터가 이동 조건을 만족할 경우, 해당 포인터를 움직인다. 

 

3. 반복

탐색할 수 없을 때까지 2번 과정을 반복한다. 

 

 

4. 최종 결과

반복을 마치면 기록한 결과물을 얻을 수 있다. 

 

 

구현 코드

두 포인터는 상황에 따라 각각의 포인터의 움직이는 방향, 위치 등이 다를 수 있다. 아래 예제들은 두 포인터가 다른 방향과 위치에서 움직이는 예제들이다.

 

문제. 백준 1806번: 부분합(문제 링크:  https://www.acmicpc.net/problem/1806)

---

시작 포인터(왼쪽 -> 오른쪽), 끝 포인터(왼쪽 -> 오른쪽)

// target이상인 부분 합의 최소 길이 반환
int twoPointer(vector<int>& v1, int target){
    int len = v1.size();
    int end = 0, sum = v1[0]; // start와 end는 겹쳐있다는 설정.
    int minLen = INT32_MAX;

    // start포인터 이동: 반복당 한 번 이동
    for(int start = 0; start < len; start++){
        // end포인터 이동: sum이 target이상이 될 때까지 이동
        while(end < len && sum < target){
            end++;
            if(end != len) sum += v1[end];  // 예외처리
        }

        // 더 이상 S 이상인 구간이 없음
        if(end == len) break;

        // 현재 start의 최소 길이와 비교 및 갱신
        minLen = min(minLen, end-start+1);
        sum -= v1[start];
    }

    return minLen;
}

 

문제. 백준 1806번: 두 용액(문제 링크:  https://www.acmicpc.net/problem/2470)

---

시작 포인터(왼쪽 -> 오른쪽), 끝 포인터(왼쪽 <- 오른쪽)

// 두 용액의 합이 0과 가장 가까운 값 반환(ver1)
pair<int, int> twoPointer2(vector<int>& v1){
    int len = v1.size();
    int end = len-1;
    pair<int, int> p = {v1[0], v1[end]};
    int minSum = abs(v1[0] + v1[end]);

    // start포인터 이동: 반복당 한 번 이동
    for(int start = 0; start < end; start++){
        pair<int, int> tempP = {v1[start], v1[end]};
        int tempSum = abs(v1[start] + v1[end]);

        // end포인터 이동: start에 가장 어울리는 end를 찾을 때까지 이동
        while(start < end && abs(v1[start] + v1[end-1]) < tempSum){
            end--;
            if(start != end){   // 예외처리
                tempP = {v1[start], v1[end]};
                tempSum = abs(v1[start] + v1[end]);
            } 
        }

        // 현재 start의 최소값과 비교 및 갱신
        if(tempSum < minSum){
            p = tempP;
            minSum = tempSum;    
        }
       
    }

    return p;
}

// 두 용액의 합이 0과 가장 가까운 값 반환(ver2)
pair<int, int> twoPointer2(vector<int>& v1){
    int len = v1.size();
    int start = 0, end = len-1;
    pair<int, int> p = {v1[0], v1[end]};
    int minSum = abs(v1[0] + v1[end]);

    while(start < end){
        // start, end포인터 이동: 두 용액의 합이 양수면 end, 아니면 start 이동
        if(v1[start] + v1[end] > 0) end--; 
        else start++;

        // 더 이상 구간이 없음
        if(start == end) break;

        // 현재 최소값과 비교 및 갱신
        if(abs(v1[start] + v1[end]) < minSum){
            p = {v1[start], v1[end]};
            minSum = abs(v1[start] + v1[end]);    
        }
    }
    
    return p;
}

 

 

짚고 넘어가야 할 점

두포인터 문제는 이분탐색으로 풀리는 경우가 많다

두 포인터는 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 구간이나 조합을 찾는 문제에서 활용한다. 이때 끝 포인터 대신 이분탐색을 사용하여 풀 수 있는 문제가 꽤 있다. 시간복잡도 면에서 보면 이분탐색의 시간복잡도는 O(NlogN), 두 포인터의 시간복잡도는 O(N)이므로 이분탐색으로 푸는 경우가 더 느리지만, logN의 차이로 시간초과가 나는 경우는 거의 없으므로 둘 중 편한 방법을 사용하면 된다.

 

참고자료

https://www.youtube.com/watch?v=I_0aAKzu0m8