알고리즘 투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 주로 정렬된 배열에서 특정 조건을 만족하는 쌍이나 구간을 찾는 문제를 풀 때 사용된다.

https://algorithm-flow.vercel.app

개념

투 포인터는 배열의 시작과 끝, 혹은 특정 위치에 두 개의 포인터(인덱스 변수)를 배치한 후, 두 포인터를 이동시키면서 문제를 해결하는 방법이다. 이 방법을 통해 모든 요소를 일일이 탐색하는 대신, 양쪽에서 동시에 탐색하거나 특정 조건을 만족하는 범위 내에서만 탐색할 수 있다.

1. 두 개의 인덱스 변수를 사용한다.
2. 조건에 따라 인덱스를 움직여 구간을 줄인다.

예시

연속된 자연수의 합이 10을 나타내는 가짓수를 출력해야 한다. (수들의 합 - 백준 2018)

만약, 모든 구간을 직접 탐색할 경우 시간 복잡도는 O(n²)이다.

const N = 10;

let count = 0;

// 모든 구간 탐색
for (let i = 1; i <= N; i++) {
  let sum = 0;
  for (let j = i; j <= N; j++) {
    sum += j; // 현재 구간의 합 계산
    if (sum === N) {
      count++;
    } else if (sum > N) {
      // 합이 N보다 커지면 더 이상 탐색 필요 없음
      break;
    }
  }
}

console.log(count);

이를 투 포인터로 변경할 경우 시간 복잡도는 O(n)이며, 필요한 구간만 효율적으로 탐색하기에 직접 탐색보다 빠르다.

const N = 10;

let sum = 0;
let count = 0;
let start = 1;
let end = 1;

while (end <= N) {
  if (sum == N) {
    count++;
    sum += end;
    end++;
  } else if (sum > N) {
    sum -= start;
    start++;
  } else {
    sum += end;
    end++;
  }
}

console.log(count);

start를 증가시키는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 같으며, end를 증가하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미이다.

• sum이 N보다 작으면 end를 오른쪽으로 한 칸 옮겨 다음 수를 더해 sum에 추가한다.
• sum이 N보다 크면 start를 오른쪽으로 한 칸 옮기고, sum에서 start 값을 빼서 구간을 줄인다.
• sum이 N과 같으면, 해당 구간을 하나의 경우로 간주하고 카운트를 증가시킨다. 이후 end를 오른쪽으로 한 칸 이동하여 다음 구간을 탐색한다.