[알고리즘] 투 포인터 알고리즘

투 포인터(Two Pointers) 알고리즘 쉽게 이해하기

많은 알고리즘 문제에서 시간 복잡도를 줄이기 위한 테크닉으로 "투 포인터" 기법을 자주 사용한다. 특히 정렬된 배열을 다루거나 부분 배열을 탐색할 때 매우 유용하게 쓰인다.

 

투 포인터란?

투 포인터란 배열에서 두 개의 포인터(인덱스)를 이용해 탐색 범위를 조절해가며 문제를 해결하는 방법이다. 이 두 포인터는 보통 같은 방향으로 이동하거나 양 끝에서 가운데로 좁혀가는 방식으로 활용된다.

 

이 방식의 핵심은 모든 경우를 탐색하지 않고도 정답에 도달할 수 있다는 점이다. 따라서 일반적인 브루트포스 O(N²) 알고리즘보다 훨씬 빠르게 문제를 풀 수 있다.

 

---

 

언제 쓰일까?

1. 정렬된 배열에서 두 수의 합을 찾을 때

2. 부분 배열의 합, 길이 등을 구할 때

3. 슬라이딩 윈도우 처럼 연속된 범위를 다룰 때

 

예시 문제: 두 수의 합이 목표값이 되는 경우 찾기

문제 설명:

정렬된 배열 arr = [1, 3, 4, 5, 7, 10, 11]이 있을 때, 합이 target = 15가 되는 두 수를 찾아보세요.

 

투 포인터로 해결하는 과정

left	right	arr[left]	arr[right]	합	결과
0	6	1	11	12	합이 작음 -> left++
1	6	3	11	14	합이 작음 -> left++
2	6	4	11	15	정답

 

코드 (JAVA)

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

    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{arr[left], arr[right]};
        else if (sum < target) left++;
        else right--;
    }

    return new int[]{-1, -1};
}

 

---

마무리

투 포인터는 정렬된 배열에서 효율적인 탐색을 가능하게 해주는 강력한 도구이다. 특히 O(N²) 복잡도를 O(N)으로 줄일 수 있다는 점에서 알고리즘 문제 풀이에 자주 활요된다.