[Algorithm][Template] 투 포인터

투 포인터(Two Pointer) 알고리즘 : 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리

 

투 포인터는 다음 2가지 케이스가 대표적인 문제 유형이다.

 

1. 특정한 합(M)을 가지는 부분 연속 수열 찾기

   - 시간복잡도 : O(N) { O(2*N)}

   - 동작과정

      1) 시작점(s)와 끝점(e)를 첫 번째 원소의 인덱스(0)로 지정한다

      2) s부터 e까지 현재 부분합이 특정한 합(M)과 같다면 카운트한다.

      3) s부터 e까지 현재 부분합이 특정한 합(M)보다 작다면 e를 1 증가시킨다.

      4) s부터 e까지 현재 부분합이 특정합 합(M)보다 크다면 s를 1 증가시킨다.

      5) 모든 경우를 확인할 떄까지 2)번부터 4)까지의 과정을 반복한다.

#include <iostream>
#include <vector>

using namespace std;

int n = 5, m = 5; // 데이터의 개수 n, 찾고자 하는 부분합 m

int arr[] = {1, 2, 3, 2, 5};

int main(void) {
    int cnt = 0;
    int interval_sum = 0;
    int e = 0;

    // start를 차례때로 증가시키며 반복
    for (int s = 0; s < n; s++) {
        // end를 가능한 만큼 이동시키기
        while (interval_sum < m && e < n) {
            interval_sum += arr[e++];
        }

        // 부분합이 m일 때 카운트 증가
        if (interval_sum == m) {
            cnt++;
        }

        interval_sum -= arr[s];
    }

    cout << cnt << endl;

    return 0 ;
}

2. 정렬되어 있는 두 리스트의 정렬된 합집합

    - 시간복잡도 : O(N+M) [N: a 크기, M: b 크기]

    - 동작과정

      1) 정렬된 리스트 a와 b를 입력 받는다.

      2) 리스트 a에서 처리되지 않은 원소의 인덱스를 i로 지정한다.

      3) 리스트 b에서 처리되지 않은 원소의 인덱스를 j로 지정한다.

      4) a[i]와 b[j]중 저 작은 원소를 결과(result) 리스트에 담고 해당 리스트의 인덱스(i 또는 j)를 1 증가시킨다.

      5) a와 b에 처리할 원소가 없을 때까지 2) ~ 4) 과정을 반복한다.

#include <iostream>
#include <vector>

using namespace std;

// 사전에 정렬된 리스트 a, b 선언
int n = 3, m =4;
vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6, 8};

int main(void) {
    int i = 0;
    int j = 0;
    // 리스트 a와 b의 모든 원소 담을 수 있는 결과 리스트
    vector<int> result;

    // 더 이상 리스트 a와 b에 처리할 원소가 없을 때까지 반복
    while (i < n || j < m) {
        // 리스트 b의 모든 원소가 처리되었거나, 리스트 a의 원소가 더 작을 경우
        if (j >= m || (i < n && a[i] <= b[j])) {
            result.push_back(a[i++]);
        }
        // 처리되지 않은 리스트 b의 원소가 존재하고 리스트 a의 모든 원소가 처리되었거나, 리스트 b의 원소가 더 작을 경우
        else {
            result.push_back(b[j++]);
        }
    }

    for (int r : result) {
        cout << r << " ";
    }
    cout << endl;

    return 0 ;
}

 

2번 코드에서 while문 안의 if-else구문에 조건이 여러개 들어가는데 이 부분이 익숙하지 않다.

익숙해지도록 하자.