[알고리즘] 투 포인터

개념

잘 모르고 있다가 투포인터라는 알고리즘에 대해 듣게되어 공부할겸 포스팅을 작성한다.

일반적으로 연속된 수들의 합을 구할 때 자주 사용된다고 한다.

기본 원리는 두 개의 인덱스를 이용하여 두 인덱스의 범위를 조절하여 정답을 찾는 방식이다.

예시를 보며 이해해보자.

크기가 10인 자연수 배열이 있고, 연속된 숫자들의 합이 5가 되는 경우의 개수를 찾아야한다고 가정하자.

투포인터 알고리즘에서는 인덱스를 2개로 지정한다. s와 e라고 하자. 그리고 두개의 인덱스를 통한 범위는 [s, e)라고 가정할 것이다.

초기에는 s = 0, e = 0이고, [s, e) 범위 내의 숫자의 합은 0이므로 M보다 작다. 따라서 e의 값을 1 증가시킨다.

위 그림의 경우 [s, e) 범위 내 숫자의 합은 1이 되었지만 아직도 M보다 작으므로 e의 값을 다시 1 증가시킨다.

이번엔 범위 내 합이 3이지만 아직도 M보다 작다.

이번엔 범위 내 합이 M보다 커져버렸다. 이 때는 s의 값을 증가시켜 합을 줄인다.

드디어 범위 내 합이 M과 같은 경우가 나왔다. 정답의 값을 1 증가시키고 s값을 증가시켜 범위를 변경한다.

위의 경우는 M보다 작아졌으므로 m 값을 증가시킨다.

이런 방식으로 배열의 처음부터 끝까지 확인하면서 답을 찾을 수 있다.

투포인터 알고리즘의 가장 큰 장점은 시간 복잡도가 O(N) 이라는 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    int s = 0, e = 0;
    // 배열의 크기 n,  찾으려는 값 m을 입력받음
    cin >> n >> m;
    vector<int> num(n);
    // 배열 num의 값을 입력받음
    for (int i = 0; i < n; i++)
        cin >> num[i];

    int ans = 0;
    int sum = 0;
    while (true) {
           // [s, e) 의 합이 m보다 크거나 같은 경우 
        if (sum >= m) sum -= num[s++];
        else if (e == n) break;
        else sum += num[e++];
        if (sum == m) ans++;
    }
    cout << ans << '\n';
    return 0;
}