투포인터 알고리즘 (Two Pointer Algorithm)

투포인터 알고리즘 이란?

배열이나 리스트에서 두 개의 포인터 인덱스를 이동시키면서 문제를 해결하는 방식

보통 정렬된 배열에서 구간 합, 조건 만족 여부, 두 원소의 조합 등 을 사용할 때 사용

시간 복잡도

O(N)

기본 원리 예시

int[] arr = {1, 2, 4, 7, 11, 15};
int target = 15;

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

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

    if (sum == target) {
        System.out.println(arr[left] + " + " + arr[right]);
        break;
    } else if (sum < target) {
        left++; // 합을 키우기 위해 왼쪽 포인터 이동
    } else {
        right--; // 합을 줄이기 위해 오른쪽 포인터 이동
    }
}

마무리 요약

투 포인터 알고리즘은 배열 문제를 풀 때 주로 사용

브루트포스 방식을 O(N) ~ O(N log N) 으로 줄여주기 때문에 효율적