투 포인터 알고리즘이란?

투 포인터 알고리즘은 리스트(배열)에서 두 개의 포인터를 사용해 연속된 구간을 다루면서 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이며 주로 리스트(배열)가 정렬이 되어 있는 경우에 사용한다.

주로 왼쪽(left)과 오른쪽(right) 포인터를 사용하고, 각각 리스트(배열)의 시작과 끝을 나타내며 주로 최소(최대) 길이, 갯수 등을 구할 때 사용한다.

이 알고리즘의 가장 큰 장점은 시간 복잡도가 O(N) 이라는 것이다.

하나의 리스트를 양쪽에서 범위를 좁혀가며 탐색을 하기에 리스트의 최대 길이 이상의 시간 복잡도가 넘지 않는다.

투 포인터의 단계적 구분

1. 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정

2. 두 포인터 사이의 구간을 조사하고 조건을 확인

3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료

4. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동

5. 다시 2번 단계로 돌아가 반복

투 포인터 알고리즘의 종류

1. 고정 길이 슬라이딩 윈도우

고정 길이 슬라이딩 윈도우는 윈도우(구간)의 길이가 처음부터 끝까지 일정하게 유지된 상태에서, 구간을 한 칸씩 이동시키며 합, 평균, 최대값, 최소값 등을 효율적으로 구하는 방식이다.

윈도우의 크기를 K로 고정 -> 초기 K개의 합을 한 번 계산 -> 앞의 값은 제거 -> 뒤의 값은 새로 추가하는 방식으로 매 구간의 값을 갱신한다.

int N = 10;
int K = 3;
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int sum = 0;

// K개 구간 합 만들기
for (int i = 0; i < K; i++) {
    sum += arr[i];
}

int max = sum;

// 슬라이딩 이동
for (int i = K; i < N; i++) {
    sum = sum - arr[i - K] + arr[i];
    max = Math.max(max, sum);
}

System.out.println(max);

2. 가변 길이 슬라이딩 윈도우

구간의 길이가 상황에 따라 늘어나기도 하고 줄어들기도 하는 방식이며,
조건을 만족하면 줄이고, 부족하면 늘린다.

주로 최소 길이 부분 배열이나, 최대 길이 부분 배열을 효율적으로 구한다.

int N = 10;
int S = 15;
int[] arr = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8};

int left = 0;
int right = 0;
int sum = 0;
int min = Integer.MAX_VALUE;

while (right < N) {
    sum += arr[right++]; // 구간 확장

    while (sum >= S) {   // 조건 만족 → 구간 축소
        min = Math.min(min, right - left);
        sum -= arr[left++];
    }
}

System.out.println(min == Integer.MAX_VALUE ? 0 : min);

3. 두 포인터 합과 차

정렬된 배열에서 두 포인터를 양쪽에서 움직이며 합 또는 차를 조절하는 방식

주로 정렬이 된 배열에서 두 수의 합이 K인지 찾는 문제에서 자주 사용한다.

int[] arr = {1, 3, 5, 7, 9, 11};
int N = arr.length;
int K = 10;

int left = 0;
int right = N - 1;

while (left < right) {
    int sum = arr[left] + arr[right];

    if (sum == K) {
        System.out.println("찾음: " + arr[left] + ", " + arr[right]);
        break;
    }
    else if (sum < K) {
        left++;
    }
    else {
        right--;
    }
}

구분	고정 슬라이딩	가변 슬라이딩	합·차 투포인터
구간 크기	고정	가변	2개 위치
포인터 이동	같이 이동	독립 이동	양쪽 또는 같은 방향
정렬 필요	❌	❌	✅
핵심 목적	최대합, 평균	최소 길이, 조건 만족	특정 합·차 찾기
대표 문제	BOJ 2559	BOJ 1806	BOJ 2470

투 포인터 알고리즘의 적용 예시

https://www.acmicpc.net/problem/1806

// 제한시간 0.5초, 10 ≤ N < 100,000, 0 < S ≤ 100,000,000
public class boj_1806_G4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // Two Pointer 방법 -> O(2N) 즉 O(N)으로 줄여줌
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = N + 1;

        while (true) {
            if (sum >= S) {
                min = Math.min(min, right - left);
                sum -= arr[left++];
            }
            else {
                if (right == N) break;
                sum += arr[right++];
            }
        }

        System.out.println(min == N + 1 ? 0 : min);

        br.close();
    }
}

핵심
연속된 부분 수열의 합이 S 이상이 되는 최소 길이를 구하라.

N ≤ 100,000, 제한시간 0.5초 → 무조건 O(N) 풀이가 필요하기에 O(N) 알고리즘인 투 포인터 알고리즘을 떠올리는 것이 중요하다.

int left = 0;
int right = 0;
int sum = 0;
int min = N + 1;

• left, right -> 두개의 포인터
• sum -> 현재 구간 합
• min -> 최소 길이

while (true) {
    if (sum >= S) {
        min = Math.min(min, right - left);
        sum -= arr[left++];
    }
    else {
    	if (right == N) break;
    	sum += arr[right++];
}

• 조건을 만족하면 최소값을 비교하고, left 포인터를 이동해 범위를 줄임
• 조건을 만족하지 않으면 right 포인터를 이동시켜서 범위를 확장시킴