투 포인터 알고리즘

1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘이다. 투 포인터 알고리즘을 통해 결과를 구하게 되면 시간복잡도를 O(n^2)에서 O(n)으로 단축시킬 수 있다.

포인터의 방향에 따라

투 포인터 알고리즘을 크게 2개로 나누면 두 포인터가 모두 같은 방향으로 움직이는 알고리즘과 두 포인터가 반대 방향으로 움직이는 알고리즘이 있다.

두 포인터가 같은 방향으로 움직이는 알고리즘

배열에서 두 개의 원소의 합이 s보다 큰 경우의 수를 출력하는 문제

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;

int n, s;
int arr[MAX];
int cnt=MAX;
int sum=0;

int Min(int a, int b){
    if(a>b)
        return b;
    else
        return a;
}

void Input(){
    cin>>n>>s;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
}

void Solution(){
    int start=0;
    int end=0;
    while(start<=end){
        if(sum>=s){
            cnt=Min(cnt, end-start);
            sum-=arr[start++];
        }
        else if(end==n)
            break;
        else
            sum+=arr[end++];
    }
    if(cnt==MAX)
        cout<<0<<endl;
    else{
        cout<<cnt<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}

두 포인터가 다른 방향으로 움직이는 알고리즘

배열에서 두 개의 원소의 합이 0과 가장 가까운 수가 되는 경우를 찾는 문제

#include <iostream>
#include <algorithm>
#include <math.h>
#define MAX 100001
using namespace std;

int n;
int arr[MAX];
int min=INT_MAX;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
}

void Solution(){
    sort(arr, arr+n);
    int start=0;
    int end=n-1;
    int index1, index2;
    while(start<end){
        int sum=arr[start]+arr[end];
        if(abs(sum)<min){
            min=abs(sum);
            index1=start;
            index2=end;
        }
        if(sum<0){
            start++;
        }
        else{
            end--;
        }
    }
    cout<<arr[index1]<<" "<<arr[index2]<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}