투 포인터

• 전제 조건: 배열은 반드시 정렬되어 있어야 함.
  • 정렬: O(N log N)
  • 투 포인터: O(N)

Case 1. 양 끝에서 좁혀오기

Two Pointer - Inward

• 시작: L = 0, R = N - 1
• 조건: L < R
• 동작 원리:
  - sum == X이면, 정답 처리, 이후 L++, R--
  - sum < X이면 왼쪽 확장 L++
  - sum > X이면 오른쪽 축소 R--
  

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> a(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int X; cin >> X;

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

    int ans = 0, L = 0, R = N - 1; // L, R은 양 끝
    while(L < R) {
        int sumA = a[L] + a[R];
        if (sumA == X) { ans++; R--, L++; }
        else if (sumA < X) L++;
        else R--;
    }
    cout << ans;
}

Case 2. 한 쪽에서 한 방향으로 이동하기

Two Pointer - Sliding Window

• 시작: L = 1, R = 1, sum = 1
• 조건: L <= N
• 동작 원리:
  • sum == N이면 정답 처리
  • sum < N이면 오른쪽 확장 R++
  • sum > N이면 왼쪽 축소 L++

#include <bits/stdc++.h>
using namespace std;

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

    int L = 1, R = 1, sum = 1, ans = 1; // N 자신은 무조건 들어가므로, ans = 1로 초기화

    while (L <= N / 2) { // 두 수 이상 더해서 N이 되려면 제일 작은 수는 N/2보다 작아야 함
        if (sum == N) ans++;
        
        if (sum < N) sum += ++R;
        else sum -= L++;
    }
    
    cout << ans;
}

이분탐색과 비교

공통점

• 정렬된 배열에서
• 탐색 범위를 빠르게 줄이는 방법

차이점

항목	투 포인터	이분 탐색
목적	조건을 만족하는 쌍/구간 찾기	조건을 만족하는 값/인덱스 찾기
방식	두 포인터 이동	가운데 값을 기준으로 반씩 나눔
시간복잡도	O(N) + O(N log N) (정렬 포함)	O(log N) + O(N log N) (정렬 포함)
예시	두 수의 합, 구간 개수	특정 수 존재 여부, 최솟값/최댓값 찾기