투포인터

• 배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 배열이나 원소 쌍을 찾는 기법
• 일반적으로 하나의 포인터는 시작 위치, 다른 하나는 끝 위치에 놓고 탐색 시작
• 시간복잡도: O(n)

사용 예시

• 연속 부분 배열 및 수열과 연속 부분 집합
  • 특정 조건을 만족하는 부분 찾을 때
• 두 포인터를 움직여서 조건을 만족하는 가장 큰/작은 범위를 찾을 때

코드

    static int twoPointer() {
        int s = 0, e = 0, len = 0;
        int max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        
        while (e < n) {
            map.put(arr[e], map.getOrDefault(arr[e], 0) + 1);

            // 현재 arr[e] 숫자의 개수가 k를 초과했을 때
            // Map의 모든 값이 k 이하가 될 때 까지 s를 이동시키며 윈도우 축소
            while (map.get(arr[e]) > k) {
                map.put(arr[s], map.get(arr[s]) - 1);
                s++;
            }
            max = Math.max(max, e - s + 1);
            e++;
        }
        return max;
    }

투포인터와 이분탐색의 차이

투포인터

• 주로 배열 내의 부분 배열이나 원소 쌍을 찾을 때 사용
• 정렬되지 않은 배열에서도 사용 가능
• 시간복잡도: O(n)
• 두 수의 합, 특정 차이 등 연속적인 부분을 찾을 때 유용

예제

• 두 수의 합이 특정 값을 갖는지 확인하는 문제
• 차이가 특정 값 이상이면서 가장 작은 경우를 찾는 문제

코드

// 문제: N개의 정수로 이루어진 수열에서 두 수를 골랐을 때 그 차이가 M 이상이면서 제일 작은 경우를 구하는 문제
int s = 0;
int e = 0;
int min = Integer.MAX_VALUE;

while (e < n) {
    int diff = a[e] - a[s];
    if (diff >= m) {
        min = Math.min(min, diff);
        s++;
    } else {
        e++;
    }
}

이분탐색

• 항상 정렬된 배열에서만 특정 값을 찾거나 최적의 값을 찾기 위해 사용
• 배열을 절반으로 나누어 목표 값을 찾을 때까지 반복적으로 범위를 줄여나감
• 시간복잡도: O(log n)
• 정확한 값 또는 특정 조건을 만족하는 첫 번째/마지막 위치를 찾을 때 유용
• 정렬된 배열에서 원하는 값을 빠르게 찾고자 할 때 유용

예제

• 정렬된 배열에서 특정 값의 위치를 찾는 문제
• 정렬된 배열에서 특정 값보다 크거나 작은 값을 찾는 문제

코드

// 문제: 정렬된 배열에서 특정 값 x를 찾는 문제
int binarySearch(int[] arr, int x) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 값이 없는 경우
}

요약

투 포인터는 배열의 두 요소 간의 관계를 탐색할 때 사용하며,
이분 탐색은 배열 내의 특정 값을 빠르게 찾을 때 사용