[알고리즘] 투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window)

투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window) 대해 공부 후 정리하였습니다.

1. 투 포인터 (Two Pointers)

1️⃣ 개념

두 개의 포인터(인덱스)를 이용해 배열이나 리스트를 한 번에 탐색하는 방식입니다.
이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 많고, 투 포인터로 이분 탐색 문제를 풀 수 있는 경우도 많습니다.

2️⃣ 특징

• 브루트포스(O(N²)) 대비 효율적
• 보통 left와 right 두 개의 변수를 사용
• 배열을 한 번만 스캔하면서 두 포인터를 조절
• 정렬 상태나 연속된 구간을 다루는 문제에서 강력함
• 데이터를 한 방향으로만 이동하면서 조건을 만족하는 부분 구간, 쌍(pair), 합 등을 찾는 데 효율적

3️⃣ 시간 복잡도

• O(N) (포인터들이 한 번만 끝까지 이동)
• 경우에 따라 정렬이 필요하면 O(N log N) + O(N)

4️⃣ 기본 코드 (합이 특정 값인 두 수 찾기)

조건: arr가 오름차순 정렬되어 있어야 함

import java.util.Arrays;

public class TwoPointersExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 7, 11, 15};
        int target = 15;

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) {
                System.out.println(arr[left] + " + " + arr[right] + " = " + target);
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
}

2. 슬라이딩 윈도우 (Sliding Window)

3. 비교

구분	투 포인터 (Two Pointers)	슬라이딩 윈도우 (Sliding Window)
개념	두 개의 포인터를 이용해 배열을 탐색하며 조건을 만족하는 구간/쌍을 찾는 방법	고정 길이 또는 가변 길이의 “연속된 구간”을 효율적으로 탐색하는 방법
포인터 이동	보통 left, right가 독립적으로 움직이며 간격이 변함	left와 right가 항상 일정 간격(고정 길이) 또는 조건에 맞춰 한 칸씩 이동
데이터 정렬 필요 여부	합 문제 등에서는 정렬 필요, 부분합 문제에서는 필수 아님	정렬 필요 없음 (단, 연속된 구간 유지 필요)
시간 복잡도	O(N) (정렬 필요 시 O(N log N) + O(N))	O(N)
주요 활용	두 수의 합, 세 수의 합, 중복 제거, 병합	부분합, 최대/최소 합, 문자열 길이 제한 문제
장점	정렬된 상태에서 빠른 탐색 가능	연속 구간 합/길이 문제에 직관적
단점	정렬이 필요한 경우가 많음, 연속되지 않은 쌍 찾기만 가능	고정/연속 구간 문제에 한정
예시 문제	합이 X인 두 수 찾기, 세 수의 합, 중복 제거	연속 부분합 최대, 길이가 K인 부분 배열의 합