투포인터, 슬라이딩 윈도우 알고리즘

∙ 투포인터 알고르짐 문제의 유형

1. 포인터 2개가 같은 방향으로 진행하는것

/*
 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다.
 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을작성하시오.
 */

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    vector<int> numbers (N,0);
    for (int i = 0; i < N; i++){
        cin >> numbers[i];
    }
    
    int start = 0;
    int end = 0;
    int cnt = 0;
    int sum = numbers[0];
    
    while (end < N){
        if (sum < M){
            end++;
            if (end < N)
                sum += numbers[end];
        }
        else if (sum > M){
            sum -= numbers[start];
            start++;
        }
        else if (sum == M){
            sum -= numbers[start];
            start++;
            end++;
            if (end < N){
                sum += numbers[end];
            }
            cnt++;
        }
    }
    cout << cnt << "\n";
}

2. 포인터 2개가 양끝에서 시작하여 반대로 진행하는 것

/*
    N개의 정수를 갖는 정렬된 수열에서 서로 다른 두 원소를 합해서 0에 가깝게 만들기
    입력 배열 : -99 -2 -1 4 98
 */

#include <iostream>
#include <vector>
#include <algorithm>
// 최대값 및 최소값을 설정할 수 있음
#include <climits>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> numbers(N);
    for (int i = 0; i < N; ++i) {
        cin >> numbers[i];
    }

    sort(numbers.begin(), numbers.end());

    int left = 0, right = N - 1;
    int min_sum = INT_MAX;
    pair<int, int> closest_pair;

    while (left < right) {
        int sum = numbers[left] + numbers[right];
        int abs_sum = abs(sum);

        if (abs_sum < min_sum) {
            min_sum = abs_sum;
            closest_pair = {numbers[left], numbers[right]};
        }

        if (sum < 0) {
            ++left;
        } else {
            --right;
        }
    }

    cout << closest_pair.first << " " << closest_pair.second << "\n";

    return 0;
}

3. 포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것

 

 

∙ 슬라이딩 윈도우 

/*
 최솟값 찾기 문제,,,슬라이딩 윈도우 알고리즘 + 정렬 사용
 N개의 수 A1, A2, ..., AN과 L이 주어진다.
 Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
 */

#include <iostream>
#include <deque>

using namespace std;
typedef pair<int, int> Node;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, L;
    cin >> N >> L;
    deque<Node> mydeque;
    
    for (int i = 0; i < N; i++){
        int now;
        cin >> now;
        
        while(mydeque.size() && mydeque.back().first > now){
            mydeque.pop_back();
        }
        
        mydeque.push_back(Node(now, i));
        
        if (mydeque.front().second <= i - L){
            mydeque.pop_front();
        }
        cout << mydeque.front().first << ' ';
    }
}