투 포인터(Two Pointer)

배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘

• cursor

#include <iostream>
#include <algorithm>

using namespace std;

int n; // 정수의 개수 (배열의 크기)
int s; // 목표 합 or 두 수의 차이
int total; // 현재 부분 배열의 합
int a[100004]; // 정수를 저장할 배열, 수열
int minvalue = 0x7fffffff; // 합이 s 이상인 부분 배열의 최소 길이 (초기값은 최대값으로 설정), 두 수의 차이 중 최소값

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
    // 두 수 입력
    cin >> n >> s;
    
    // 배열 및 수열에 저장
    for (int i=0;i<n;i++) {
        cin >> a[i];
    }    
	
    // total배열(저장할 새로운 배열) 초기화
    total = a[0]; 
	
    // binary_search() 사용할 때는 sort()함수로 먼저 배열을 정렬
    sort(a, a+n);
    
    // 슬라이딩 윈도우(투 포인터 탐색)
    int end = 0;
    // 합이 s 이상이 되는 순간마다 최소 길이를 업데이트하고, start 포인터를 이동시켜 다음 부분 배열을 검사
    for(int start = 0; start<n;start++) {
        while(end < n && total < s) {
            end++;
            
            // end가 배열 끝까지 돌 때까지 total에 현재 끝값을 게속 더함
            // if(end != n) {
                total += a[end];
            }
        }
            // end가 범위를 벗어나면 종룔
            if(end == n) {
                break;
            }
            minvalue = min(minvalue, end-start+1);
            // total -= a[start];
        }
        // if(minvalue == 0x7fffffff) {
            minvalue = 0;
        }
            cout << minvalue;
    }

슬라이딩 윈도우 (투포인터 탐색) 알고리즘

int end = 0;
for(int start=0;start<n;start++) {
	while(end < n && 조건) {
    	end++;
       }
       
    if (end == n) {
    	break;
       }
    minvalue = min(minvalue, 주어진 수식);
    
    }
    cout << minvalue;