투포인터(Two Pointers) 알고리즘

투포인터(Two Pointers)란 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용해 문제를 효율적으로 푸는 알고리즘 기법이다. 주로 정렬된 배열이나 연속 구간 문제에서 사용되며 O(N^2)의 완전 탐색을 O(N) 또는 O(N log N)으로 최적화할 수 있다.

핵심 아이디어

• 두 개의 포인터(left, right)를 사용해 탐색 범위를 좁혀가며 조건을 만족하는 구간을 찾는다.
• 포인터를 움직이는 규칙을 잘 설계하면 불필요한 중복 탐색을 제거할 수 있다.

장점

• 연속 구간/정렬 배열에서 매우 빠르게 탐색 가능 (O(N))
• 추가 메모리 사용이 거의 없음

단점

• 정렬되지 않은 데이터에서는 바로 적용하기 어려움
• 포인터 이동 조건을 잘못 설계하면 무한 루프 발생

언제 사용하면 좋은가?

• 연속 구간의 합 / 길이를 빠르게 계산해야 할 때
• 정렬된 배열에서 특정 합을 찾거나 최소/최대 거리를 구할 때
• 슬라이딩 윈도우(Sliding Window) 문제를 해결할 때도 활용 가능

예시 문제
1. 두 수의 합이 target이 되는 쌍 찾기
2. 길이가 N인 배열에서 합이 M 이하인 최대 부분 배열 길이 찾기
3. 부분 문자열 / 연속 부분 수열의 조건 충족 여부 탐색

어떻게 동작하는가?

1. 시작점(left)과 끝점(right) 두 개의 포인터를 준비
2. 조건에 따라 한쪽 포인터를 이동
3. 탐색 범위를 좁혀가며 문제 해결

예시 1 – 두 수의 합이 target 되는 경우 찾기

문제: 정렬된 배열에서 두 수의 합이 target인 경우를 찾아라.

public class TwoPointerExample {
    public static int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int currentSum = nums[left] + nums[right];

            if (currentSum == target) {
                return new int[]{nums[left], nums[right]};
            } else if (currentSum < target) {
                left++; // 합이 작으면 왼쪽 포인터를 오른쪽으로 이동
            } else {
                right--; // 합이 크면 오른쪽 포인터를 왼쪽으로 이동
            }
        }

        return new int[]{}; // 못 찾으면 빈 배열
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 7, 11, 15};
        int target = 15;
        int[] result = twoSum(nums, target);

        if (result.length > 0) {
            System.out.println(result[0] + ", " + result[1]);
        } else {
            System.out.println("No pair found");
        }
    }
}

동작 과정

nums = [1, 2, 4, 7, 11, 15], target = 15

1. left=0, right=5 → sum=1+15=16 > 15 → right--
2. left=0, right=4 → sum=1+11=12 < 15 → left++
3. left=1, right=4 → sum=2+11=13 < 15 → left++
4. left=2, right=4 → sum=4+11=15 == target → return (4, 11)

최종 결과 : 4, 11

예시 2 – 합이 M 이하인 가장 긴 부분 배열 길이

문제: 양의 정수 배열에서 연속 부분합이 M 이하인 최대 길이를 구하라.

public class MaxLengthSubarray {
    public static int maxLengthSubarray(int[] nums, int M) {
        int left = 0;
        int currentSum = 0;
        int maxLength = 0;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];

            // 합이 M을 초과하면 왼쪽 포인터 이동
            while (currentSum > M) {
                currentSum -= nums[left];
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 3, 2, 4};
        int M = 6;

        int result = maxLengthSubarray(nums, M);
        System.out.println("최대 길이: " + result); // 출력: 3
    }
}

동작 과정

nums = [2, 1, 3, 2, 4], M = 6

1. right=0 → sum=2 ≤ 6 → maxLength=1
2. right=1 → sum=3 ≤ 6 → maxLength=2
3. right=2 → sum=6 ≤ 6 → maxLength=3
4. right=3 → sum=8 > 6 → left++ → sum=6 → maxLength=3
5. right=4 → sum=10 > 6 → left++ → sum=8 >6 → left++ → sum=7>6 → left++ → sum=4

최종 결과 : 3

📝 느낀점

이번에 투포인터를 정리하면서 완전 탐색으로는 O(N²)인 문제를 O(N)으로 최적화할 수 있다는 점이 인상 깊었다. 특히 배열의 합이나 문자열의 연속 구간 문제에서 불필요한 반복을 줄일 수 있어 효율적이다. 다만, 포인터 이동 조건을 잘못 설계하면 무한 루프에 빠질 수 있으므로 이동 규칙을 명확히 정의하는 것이 중요하다고 느꼈다. 앞으로 연속 부분합, 슬라이딩 윈도우, 문자열 처리 문제를 만날 때 우선 투포인터를 떠올리면 큰 도움이 될 것 같다.