투 포인터 알고리즘(Two Pointer Algorithm)

투 포인터 알고리즘(Two Pointer Algorithm)
정렬 + 연속 구간 처리 같은 문제에서 자주 쓰이는 알고리즘임

투 포인터란?

두 개의 포인터를 사용해서 배열을 탐색하는 알고리즘
C 문법* 이거랑 다른거임 가리키다의 의미

보통 왼쪽 포인터(l), 오른쪽 포인터(r)를 써서
배열에서 구간, 쌍, 조건을 만족하는 범위를 찾을 때 씀

투 포인터가 필요한 상황

• 정렬된 배열에서 두 수의 합이 K가 되는 쌍 찾기
• 연속된 부분합이 K 이상이 되는 가장 짧은 구간 찾기
• 두 수의 차이가 특정 값 이상인 쌍의 개수 구하기
  

기본 구조

int l = 0, r = 0;
while (r < N) {
    if (조건 만족) {
        // 정답 처리
        l++; // 왼쪽 포인터 움직임
    } else {
        r++; // 오른쪽 포인터 움직임
    }
}

조건을 만족하면 -> 왼쪽 포인터 줄이면서 구간 좁힘
조건 미만이면 -> 오른쪽 포인터 늘리면서 구간 키움

https://www.acmicpc.net/problem/28353
백준 #28353 고양이 카페도 투 포인터로 풀 수 있다

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main(){
    int n;
    long long k;
    long long cat_arr[5001] = {};
    
    scanf("%d %lld", &n, &k);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &cat_arr[i]);
    }

    qsort(cat_arr, n, sizeof(long long), compare);

    long long left = 0;
    long long right = n - 1;
    long long count = 0;

    while (left < right) {
     
        if (cat_arr[left] + cat_arr[right] <= k) {
            count++;
            left++;
            right--;
        } else {
            right--;
        }
    }

    printf("%lld\n", count);
    return 0;
}

정리

특징	설명
포인터 2개 사용	한 배열 위에서 왼쪽/오른쪽 포인터 조절
정렬된 배열에서 자주 사용	구간 합/쌍/조건 만족 탐색에 강함
시간복잡도	O(N)
핵심 아이디어	조건 만족할 때는 좁히고, 안 맞으면 넓힌다

시간 복잡도가 0인 이유
l,r 둘 다 한 방향으로만 움직임 (뒤로 안감)
각 포인터는 최대 N번만 움직일 수 있음