투 포인터(Two Pointers) 알고리즘은 주로 배열 또는 리스트에서 특정한 조건을 만족하는 부분을 찾거나, 두 개의 포인터를 이용하여 특정한 연산을 수행하는 알고리즘 기법이다.

주요 특징

• 두 개의 포인터 사용: 주어진 배열이나 리스트에서 두 개의 포인터를 사용하여 특정한 조건을 만족하는 부분을 찾거나, 연산을 수행한다.

• 선형 시간복잡도: 투 포인터 알고리즘은 탐색 범위를 반으로 줄여가며 탐색하는 특징을 가지고 있어서 시간복잡도가 O(n) 또는 O(nlogn)이다.

주요 용도

• 부분합 문제 해결: 주어진 배열에서 두 요소를 선택하여 그 합이 특정한 값이 되는 경우를 찾거나, 연속된 부분 배열의 합이 특정한 값이 되는 경우를 찾는 경우

• 두 요소의 합 찾기: 주어진 정수 배열에서 두 요소를 선택하여 특정한 값이 되는 경우를 찾는 경우

• 특정 구간 찾기: 리스트에서 특정한 조건을 만족하는 부분 구간을 찾는 경우

투 포인터 알고리즘 예시

아래 배열에서 부분합이 9가 되는 구간을 찾는 방법

• 기존 단순 for문 이용 방법
  

• 투 포인터 방법
  

코드 예시

• 두 요소의 합 찾기

public boolean twoSum(int[] nums, int target) {
    Arrays.sort(nums); // 배열 정렬
    int left = 0, right = nums.length - 1; // 투 포인터 설정
    while (left < right) {
        int sum = nums[left] + nums[right]; // 두 수의 합 계산
        if (sum == target) {
            return true; // 합이 target과 동일한 경우
        } else if (sum < target) {
            left++; // 합이 target보다 작은 경우, 왼쪽 포인터를 오른쪽으로 이동
        } else {
            right--; // 합이 target보다 큰 경우, 오른쪽 포인터를 왼쪽으로 이동
        }
    }
    return false; // 찾지 못한 경우
}

• 특정 구간 찾기

public int[] subarraySum(int[] nums, int target) {
    int left = 0, right = 0; // 투 포인터 설정
    int sum = 0; // 현재 부분합 저장
    while (right < nums.length) {
        sum += nums[right]; // 현재 부분합 갱신
        while (sum > target) {
            sum -= nums[left++]; // 현재 부분합이 target을 초과하는 경우, 왼쪽 포인터 이동
        }
        if (sum == target) {
            return Arrays.copyOfRange(nums, left, right + 1); // 조건을 만족하는 구간 반환
        }
        right++; // 오른쪽 포인터 이동
    }
    return new int[]{-1}; // 조건을 만족하는 구간이 없는 경우
}

결론

투 포인터 알고리즘은 주어진 배열이나 리스트에서 두 개의 포인터를 이용하여 특정한 조건을 만족하는 부분을 찾거나, 연산을 수행하는 효율적인 알고리즘 기법이다. 이 알고리즘은 시간복잡도가 선형이기 때문에 대용량 데이터에 대해서도 빠르게 처리할 수 있다.