투포인터 알고리즘 (Two Pointers Algorithm)

투포인터 알고리즘이란?

배열/리스트에서 두개의 인덱스(포인터)를 사용하여 특정 조건을 만족하는 구간을 효율적으로 탐색하기 위한 알고리즘

일반적으로 탐색하는 배열/리스트가 정렬되어 있을 때 사용한다.

 

사용하는 경우

1) 일반적으로 두 인덱스를 탐색범위의 시작과 끝으로 사용하여, 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나 조건을 만족하는 부분배열을 찾는 데에 사용한다.

2) 동일한 인덱스를 시작으로, 한 인덱스를 고정하고 다른 인덱스를 이동시키다가 특정 조건에서 고정한 인덱스도 이동시키며 탐색하는 방법도 사용할 수 있다.

 

 

구현 방식

1) 배열의 탐색할 위치에 두 포인터를 설정한다.

2) 두 포인터 혹은 그 구간을 탐색하고 조건에 일치하는지 확인한다.

3) 조건을 만족시키는 경우 탐색을 종료한다.

4) 조건을 만족시키지 않는 경우 인덱스를 이동시키고 다시 2번 과정부터 반복한다.

 

 

예제

배열에서 두 수의 합이 특정한 값을 갖는 경우의 수 구하기

0) (정렬된 배열이 아니라면) 배열을 정렬해준다!

1) 배열의 시작 인덱스(left), 마지막 인덱스(right)를 두 포인터로 잡는다.

2) left < right 인 조건에서 두 위치의 값을 합하여 조건을 만족하는지 확인한다.

3) arr[left] + arr[right] == 찾는 값인 경우 count 증가, left 증가, right 감소 해준다

4) arr[left] + arr[right] < 찾는 값인 경우 left 증가 (즉, 더하는 수가 더 커짐)

5) arr[left] + arr[right] > 찾는 값인 경우 right 감소(즉, 더하는 수 작아짐)

 

// 배열의 두 값을 더해 12가 되는 경우의 수 구하기
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 12;

let count = 0;
let left = 0;
let right = numbers.length - 1;

while(left < right) {
    let sum = numbers[left] + numbers[right];
    if(sum == target) {
        count++;
        left++;
        right--;
    }
    else if (sum < target) {
        left++;
    }
    else {
        right--;
    }
}

console.log(count);

 

 

배열에서 특정 길이 내 합산이 제일 큰 값 찾기

1) 0번 인덱스에서부터 주어진 길이 - 1까지의 합을 구한다 (currentSum)

2) 주어진 길이만큼의 차이가나는 인덱스를 잡는다

-> 두 인덱스의 차이가 일정하므로 꼭 다른 변수가 아니어도 된다!

-> ex. 인덱스1 = i, 인덱스2 = i + k  or 인덱스1 = i, 인덱스2 = i - k

3) 오른쪽 인덱스가 마지막 인덱스일 때까지 반복하며 currentSum에서 직전 부분배열의 가장 왼쪽 값을 빼고, 이번 부분 배열의 가장 오른쪽 값을 합해준다.

-> 매번 그 간격만큼 순회하며 합산하는게 아니라 직전에 구한 값에서 다음 값을 구할 때 제외되는 값(가장 왼쪽 값)을 빼고, 새로운 값(가장 오른쪽 값)을 더해주는 것이다!

Num 아니고 Sum ㅎㅎ

4) currentSum이 기존의 최대값보다 크다면 최대값을 바꿔준다.

 

const numbers = [1, 3, 4, 2, 7, 1, 0];
const k = 3;

let maxSum = 0;
let currentSum = 0;

for(let i = 0; i < k; i++) {
    currentSum += numbers[i];
}

maxSum = currentSum;

for(let i = k; i < numbers.length; i++) {
    currentSum = currentSum - numbers[i - k] + numbers[i];
    maxSum = Math.max(maxSum, currentSum);
}

console.log(maxSum);