투 포인터

투 포인터에 대해 알아봅시다.

 

투 포인터는 말 그대로 두 개의 포인터를 조작하면서

두 포인터가 가리키는 값이 특정한 조건을 만족하도록,

또는 두 포인터 사이의 구간이 조건을 만족하도록 하여 문제를 푸는 방식입니다.

 

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

3273번: 두 수의 합

 

\(n\)개의 서로 다른 양의 정수로 이루어진 수열 \(a\)가 주어졌을 때, \(a_i + a_j = x\)를 만족하는 \((i, j)\) 쌍을 모두 구하라고 합니다.

 

수열을 정렬 한 다음, 포인터 두 개를 수열의 맨 끝에 놓아 봅시다.

 

x = 14

다음과 같은 수열이 주어졌고, x가 14라고 가정해 봅시다.

두 포인터가 가리키는 값의 합이 14가 유지되도록 하면서 이동시킵시다.

왼쪽 포인터는 오른쪽으로, 오른쪽 포인터는 왼쪽으로만 이동합니다.

 

현재 두 포인터가 가리키는 값의 합은 1+15 = 16으로, 14보다 큽니다.

어떤 포인터를 옮겨야 할까요?

 

이 경우에는 오른쪽 포인터를 왼쪽으로 옮겨, 합이 작아지도록 하면 됩니다.

 

1 + 13 = 14

 

1+13 = 14인 경우를 하나 찾았습니다.

모든 수가 다르다고 했으니, 두 포인터 중 아무거나 옮기면 됩니다. 오른쪽 포인터를 옮겨 봅시다.

 

1 + 12 = 13

두 포인터가 가리키는 값의 합이 1+12 = 13으로, 14보다 작습니다.

이번에는 왼쪽 포인터를 오른쪽으로 옮겨, 합이 커지도록 하면 됩니다.

 

2 + 12 = 14

정리하면,

두 포인터가 가리키는 합이 x보다 크다면 오른쪽 포인터를 왼쪽으로 옮겨 합이 더 작아지도록,

두 포인터가 가리키는 합이 x보다 작다면 왼쪽 포인터를 오른쪽으로 옮겨 합이 더 커지도록 하면 된다는 사실을 알 수 있습니다.

그리고 두 개의 포인터가 한 점에 만나기 전까지 이를 반복하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
 
    int x; cin >> x;
 
    int ans = 0;
    int l = 0, r = n - 1;
    while (l < r)
    {
        if (a[l] + a[r] == x) ans++;
        if (a[l] + a[r] > x) r--; // 오른쪽 포인터를 왼쪽으로 옮긴다.
        else l++; // 왼쪽 포인터를 오른쪽으로 옮긴다.
    }
 
    cout << ans;
}

 

시간복잡도는 왼쪽 포인터와 오른쪽 포인터 둘다 많아도 \(n\)번 움직이므로, 총 \(O(n)\)입니다.

---

이번엔 각 두 포인터가 가리키는 값이 아니라, 두 포인터 사이의 구간이 특정한 조건을 만족하도록 해 봅시다.

 

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

2003번: 수들의 합 2

 

\(n\) 길이의 수열 \(a\)가 주어집니다.

이 수열의 연속하는 부분수열의 합이 \(m\)이 되는 경우의 수를 구해야 합니다.

 

이번에는 두 포인터를 수열의 맨 앞에 놓아 봅시다.

 

m = 5

역시 다음과 같은 수열이 주어지고, m이 5라고 가정해 봅시다.

두 포인터 사이의 부분 수열의 합이 5가 유지되도록 하면서 두 포인터를 이동시킵시다.

두 포인터 모두 오른쪽으로만 움직입니다.

 

현재 두 포인터가 같은 위치에 있으므로, 사이에 아무런 수도 없습니다.

따라서 두 포인터 사이에 있는 수들의 합은 0이고, 이는 5보다 작으므로 구간이 더 커져야 된다는 사실을 알 수 있습니다.

오른쪽 포인터를 이동시킵시다.

 

구간의 합 : 1

아직도 5보다 작습니다. 5보다 크거나 같을 때까지 오른쪽 포인터를 이동시킵시다.

 

구간의 합 : 6

이번에는 두 포인터 사이의 구간의 합이 6입니다.

이는 5보다 크기 때문에, 구간이 더 작아져야 합니다.

왼쪽 포인터를 이동시킵시다.

 

구간의 합 : 5

이렇게 구간의 합이 5인 경우를 찾을 수 있습니다.

이를 더 이상 포인터가 이동할 수 없을 때까지 반복하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
int a[10001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
 
    int ans = 0;
    int l = 0, r = 0;
    int sum = 0;
 
    for (; l < n; l++)
    {
        while (r < n && sum < m)
        {
            sum += a[r];
            r++; // 오른쪽 포인터를 이동한다.
        }
 
        if (sum == m) ans++;
 
        sum -= a[l]; // 왼쪽 포인터를 이동한다.
    }
 
    cout << ans;
}

 

시간복잡도는 역시 \(O(n)\)입니다

---

 

두 포인터를 간격이 일정하도록 움직여야 한다면, 이를 슬라이딩 윈도우라고 합니다.

 

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

12847번: 꿀 아르바이트

 

\(n\)길이의 수열이 주어지고, 연속한 \(m\)길이의 부분 수열의 합 중 가장 큰 것을 알아내야 합니다.

 

지금까지의 투 포인터와 비슷하지만, 두 포인터의 간격이 \(m\)으로 일정하도록 움직여 주면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n, m;
ll t[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
 
    ll sum = 0;
    for (int i = 0; i < m; i++) sum += t[i];
 
    ll ans = sum;
 
    for (int i = 0; i + m < n; i++)
    {
        // 두 포인터를 모두 오른쪽으로 한칸씩 이동한다.
        sum -= t[i];
        sum += t[i + m];
 
        ans = max(ans, sum);
    }
 
    cout << ans;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.

solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!

그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!

https://www.acmicpc.net/group/7712

ANZ1217