투 포인터 (Two Pointers)

투 포인터 (Two Pointers) 설명:

투 포인터 기법은 배열이나 리스트와 같은 순차적인 자료구조에서 두 개의 포인터를 동시에 이용하여 문제를 해결하는 방법론입니다. 주로 정렬된 배열에서 두 수의 합, 연속된 서브 배열의 합 등의 문제에서 유용하게 사용됩니다.

기본 아이디어는 두 포인터가 배열 안에서 움직이며 조건을 만족하는 부분을 찾는 것입니다. 포인터의 움직임은 문제의 조건에 따라 결정됩니다.

투 포인터의 대표적인 사용 예:

1. 정렬된 배열에서 두 수의 합 찾기: 배열과 타겟 값을 주면, 합이 타겟 값이 되는 두 원소의 인덱스를 찾는 문제.
2. 서브 배열의 합: 주어진 합을 가진 연속된 서브 배열을 찾는 문제.
3. 최소 길이 서브 배열의 합: 주어진 합 이상을 가진 최소 길이의 연속된 서브 배열을 찾는 문제.
4. 회문 판별: 두 포인터를 사용하여 문자열이 회문인지 판별하는 문제.

예제와 솔루션 (정렬된 배열에서 두 수의 합 찾기):

문제:
정렬된 배열과 타겟 값을 입력받아, 합이 타겟 값이 되는 두 원소의 인덱스를 반환하라.

function twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];

        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return [];
}

console.log(twoSum([2, 7, 11, 15], 9));  // 출력: [1, 2]

이 코드는 투 포인터 방식을 사용하여 twoSum 문제를 해결합니다. 배열의 처음과 끝에서 시작하는 두 포인터를 중간으로 점점 좁혀오면서 합이 타겟 값과 일치하는 두 원소의 인덱스를 찾습니다.

투 포인터 기법은 주어진 조건을 만족하는 부분을 효율적으로 찾기 위한 알고리즘으로, 특히 정렬된 배열에서의 탐색 문제에 매우 효과적입니다.