부분 수열의 탐색 문제 - 연속된 부분 수열의 합 - 투포인터 알고리즘(Two-Pointer Algorithm)

coding-test-no-cap/프로그래머스/2/178870. 연속된 부분 수열의 합 at main · LeeQuiett/coding-test-no-cap

coding-test-no-cap/프로그래머스/2/178870. 연속된 부분 수열의 합 at main · LeeQuiett/coding-test-no-cap

 

연속된 부분 수열의 합 문제를 Two-Pointer 방식을 사용하면 O(N)의 시간복잡도로 문제를 해결할 수 있다.

1. 투 포인터(Two Pointers)

정의

• 배열이나 문자열과 같은 선형 구조에서 두 개의 포인터(인덱스)를 활용하여 문제를 해결하는 알고리즘 기법
• 일반적으로 두 포인터는 서로 다른 방향으로 움직이며, 문제의 조건에 따라 적절히 조정
  • 한 포인터는 시작점, 다른 포인터는 끝점에서 출발하거나,
  • 두 포인터가 같은 방향으로 이동하기도 함

특징

• 주로 정렬된 데이터에서 특정 조건을 만족하는 쌍(pair)이나 구간을 찾는 데 사용
• 두 포인터가 반드시 서로 다른 위치에서 시작해야 하는 것은 아님

사용 사례

• 정렬된 배열에서 두 수의 합(Two Sum) 찾기
• 교집합 또는 특정 조건을 만족하는 배열 간 비교
• 팰린드롬 검사 (문자열 좌우에서 비교)

예시 (정렬된 배열에서 두 수의 합이 k인 경우)

int[] arr = {1, 2, 3, 4, 6};
int k = 6;

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == k) {
        System.out.println("Pair: (" + arr[left] + ", " + arr[right] + ")");
        break;
    } else if (sum < k) {
        left++;
    } else {
        right--;
    }
}