[Algorithm] 투포인터 / Two Pointers

1. Two pointers 란?

• 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 치리하는 알고리즘
• 보통 알고리즘에서 엄청나게 많은 입력들 중에서 원하는 값을 찾거나 반복문을 사용했을때 시간복잡도가 터지는 경우에 사용.
• 시간 복잡도 : O(N) || 매 과정에서 인덱스를 옮기는데 무조건 1씩 증가하고 항상 start <= end여야하기 때문에 인덱스가 증가하는 과정은 최대 N번만 반복된다. 

---

2. Default Logic

기본적으로 투포인터 알고리즘에 사용되는변수들부터 알아본다.

start = 0; // 포인터 1

end = 0; // 포인터 2

sum = vec[0]; // 부분 합

m = 4; // 원하는 부분 합

 

우리는 우리가 원하는 부분 합이 4일때를 구할 것이다.

다음은 쪼개지는 부분 문제이다.
1. sum < m (현재 부분합이 우리가 원하는 부분합보다 작을 때)
 - end 증가
 - sum += vec[end] (end 인덱스의 값)

2. sum == m (현재 부분합이 우리가 원하는 부분합이랑 일치할 때)
 - end 증가
 - sum += vec[end] (end 인덱스의 값)
 - sum -= vec[start] (start인덱스의 값)
 - start 증가

3. sum > m (현재 부분합이 우리가 원하는 부분합보다 클 때)
 - sum -= vec[start] (start인덱스의 값)
 - start 증가

글로는 이렇게 표현할 수 있지만 직접 그림으로 보자

Testcase 
10 4
5 1 3 5 10 7 4 9 2 2

 

각각 포인터 0으로 값 초기화

 

m보다 sum이 작기 때문에 end++

m보다 sum이 크기 때문에 start++

m보다 sum이 작기 때문에 end++

 

m보다 sum이 작기 때문에 end++ / sum == m 일치

end == 2가 됐을 때 구간합과 원하는 Value가 일치하게 된다.

그리고 이후에 원하는 Value 값이 나왔기때문에 end를 하나 증감하면 다음번에는 또 하나를 내려줘야하기때문에 한번에 end와 start를 올려주고 sum값을 계산해준다.

 

//Default Code

#include<bits/stdc++.h>

using namespace std;

vector<int> vec;

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        vec.push_back(a);
    }

    int cnt = 0;
    int end = 0;
    int start = 0;

    int sum = vec[0];

    while(end < n) {
        if(sum < m) {
            end++;
            sum += vec[end];
        }
        else if(sum == m) {
            cnt++;
            end++;
            sum += vec[end];
            sum -= vec[start];
            start++;
        }
        else if(sum  > m) {
            sum -= vec[start];
            start++;
        }
    }
    cout << cnt;
}

 

---

3. 추천 문제

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

https://www.acmicpc.net/problem/1806

1806번: 부분합