TIL-2024.02.14 -알고리즘-투포인터 알고리즘

배열이나 리스트 같은 선형 구조에서 두 개의 포인터를 사용하여 문제를 해결하는 방법입니다. 이 알고리즘은 주로 정렬된 배열이나 리스트에서 두 요소의 합이 특정 값에 해당하는 문제, 연속적인 데이터의 부분 합, 최소 길이 부분 배열 찾기 등에 활용됩니다. 투포인터 알고리즘의 핵심은 두 포인터가 서로 다른 속도로 움직이거나, 조건에 따라 한쪽 또는 양쪽 포인터가 이동하며 조건을 만족하는 해를 찾는 것입니다.

해당 알고리즘은 중첩 For 문을 써서 풀이도 가능하지만, 시간 복잡도 측면에서 다중 For문은 O(N^2)이지만, 
투포인터 알고리즘은 배열을 한번만 순회하기 때문에 선형 시간 복잡도 O(n)을 가짐

 

 

투포인터 알고리즘의 기본 개념 

시작 포인터(Start Pointer): 배열의 시작 부분을 가리킵니다. 

끝 포인터(End Pointer): 배열의 끝 부분 또는 특정 조건에 따라 배열 내 다른 위치를 가리킬 수 있습니다. 

 

조건 검사: 두 포인터가 가리키는 값의 합이 특정 값과 일치하는지, 부분 배열의 합이 특정 값보다 크거나 작은지 등 조건을 검사합니다. 포인터 이동: 조건에 따라 시작 포인터를 오른쪽으로, 끝 포인터를 왼쪽으로, 또는 두 포인터 모두를 이동시킵니다.

 

 

function twoPointers(array, target) {
    let start = 0; // 시작 포인터
    let end = array.length - 1; // 끝 포인터

    while (start < end) {
        let sum = array[start] + array[end];

        if (sum === target) {
            return [start, end]; // 조건에 부합하는 인덱스 반환
        } else if (sum < target) {
            start++; // 합이 목표보다 작으면 시작 포인터를 오른쪽으로 이동
        } else {
            end--; // 합이 목표보다 크면 끝 포인터를 왼쪽으로 이동
        }
    }

    return [-1, -1]; // 조건을 만족하는 요소가 없는 경우
}

// 예제 사용
const array = [1, 2, 3, 4, 5];
const target = 9;
console.log(twoPointers(array, target)); // [3, 4] 출력


// 작동 원리
// 1. 배열이 정렬되어 있다고 가정합니다.
// 2. 시작 포인터는 배열의 첫 번째 요소를, 끝 포인터는 배열의 마지막 요소를 가리킵니다.
// 3. 두 포인터가 가리키는 값의 합을 계산하고, 그 합이 목표값과 같으면 해당 포인터의 위치를 반환합니다.
// 4. 합이 목표값보다 작으면 시작 포인터를 오른쪽으로 이동시켜 합을 증가시킵니다.
// 5. 합이 목표값보다 크면 끝 포인터를 왼쪽으로 이동시켜 합을 감소시킵니다.
// 6. 시작 포인터가 끝 포인터보다 작은 동안 위의 과정을 반복합니다.