투 포인터 (Two Pointers)

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

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분 구간을 빠르게 탐색하기 위해 사용하는 효율적인 알고리즘 기법입니다. 주로 정렬된 배열이나 리스트에서 연속된 부분 수열을 찾거나 특정 합을 구하는 문제에서 자주 활용됩니다. 이 방법은 두 개의 포인터를 사용하여 탐색을 진행하며, O(n)의 시간 복잡도를 제공하여 대량의 데이터를 효율적으로 처리할 수 있습니다.

 

투 포인터의 동작 원리

투 포인터 알고리즘은 보통 두 가지 포인터를 사용하여 배열의 시작점과 끝점 또는 배열의 특정 부분을 탐색합니다. 이 두 포인터는 보통 다음과 같이 동작합니다:

1. 포인터의 초기화:
   • 하나의 포인터는 배열의 시작 위치(start)에, 다른 포인터는 시작 위치나 그 이후(end)에 위치시킵니다.
2. 포인터의 이동:
   • 특정 조건(예: 부분 수열의 합이 특정 값 이상)이 충족되지 않으면 end 포인터를 오른쪽으로 이동하여 구간을 확장합니다.
   • 조건이 충족되면 start 포인터를 오른쪽으로 이동하여 구간을 줄이며, 조건이 유지되는지 확인합니다.
3. 조건 확인:
   • 탐색 도중 특정 조건(예: 합이 k와 같은지)을 만족하면, 조건에 맞는 구간의 정보를 저장하고 더 최적의 구간을 찾기 위해 포인터를 조정합니다.

 

투 포인터의 예시

다음은 Java로 작성한 간단한 투 포인터 알고리즘 예제입니다. 이 코드는 비내림차순으로 정렬된 수열에서 합이 k인 부분 수열의 시작 인덱스와 끝 인덱스를 찾는 예제입니다.

public class TwoPointersExample {
    public int[] findSubarrayWithSum(int[] sequence, int k) {
        int start = 0, end = 0, sum = 0;
        int minLength = Integer.MAX_VALUE;
        int[] result = new int[2];

        while (end < sequence.length) {
            sum += sequence[end];  // 오른쪽 포인터 확장
            end++;

            while (sum >= k) {  // 합이 k 이상일 경우 처리
                if (sum == k && (end - start) < minLength) {
                    minLength = end - start;
                    result[0] = start;
                    result[1] = end - 1;
                }
                sum -= sequence[start];  // 왼쪽 포인터 이동으로 구간 축소
                start++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TwoPointersExample solution = new TwoPointersExample();
        int[] sequence = {1, 2, 3, 4, 5};
        int k = 7;
        int[] result = solution.findSubarrayWithSum(sequence, k);
        System.out.println("Start index: " + result[0] + ", End index: " + result[1]);
    }
}

코드 설명

1. start와 end 포인터: 배열의 시작부터 두 포인터를 초기화합니다.
2. sum 변수: 현재 포인터 사이의 부분 수열의 합을 저장합니다.
3. while 루프: end 포인터를 증가시켜 구간을 확장합니다.
4. 내부 while 루프: sum이 k 이상일 때 start 포인터를 오른쪽으로 이동하여 합을 줄이고 조건을 유지합니다.
5. 조건 만족 시 갱신: sum == k인 경우, 현재 구간의 길이를 계산하고 최소 길이와 비교하여 갱신합니다.

 

투 포인터 알고리즘의 장점

• 효율성: 단일 포인터를 사용하여 O(n^2)로 풀어야 하는 문제를 O(n)으로 해결할 수 있습니다.
• 간결함: 구현이 비교적 단순하여 직관적으로 이해할 수 있습니다.
• 적용 범위: 다양한 문제(정렬된 배열의 합 찾기, 연속된 부분 배열 문제 등)에 적용할 수 있습니다.

 

투 포인터가 적합한 문제 유형

• 정렬된 배열에서 특정 조건을 만족하는 두 원소나 부분 배열을 찾는 문제.
• 연속된 부분 배열에서 특정 합을 구하는 문제.
• 두 배열을 비교하여 공통 요소를 찾는 문제.