data structures - 투포인터

투 포인터 알고리즘(Two Pointers Algorithm)은 배열이나 리스트에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 데 사용되는 알고리즘입니다. 주로 정렬된 배열이나 리스트에서 특정한 조건을 만족하는 부분집합을 찾는 데 효과적으로 사용됩니다. 이 알고리즘은 일반적으로 배열의 양 끝에서 시작하여 서로 다가가는 방식으로 동작합니다.

투 포인터 알고리즘의 핵심 아이디어는 두 개의 포인터를 조작하여 원하는 조건에 도달하거나 조건을 만족하는 결과를 찾는 것입니다.

function twoSum(arr, target) {
  let left = 0;               // 배열의 시작 지점
  let right = arr.length - 1;  // 배열의 끝 지점

  while (left < right) {
    let sum = arr[left] + arr[right];

    if (sum === target) {
      return [arr[left], arr[right]];  // 합이 타겟과 일치하는 경우
    } else if (sum < target) {
      left++;  // 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로 이동
    } else {
      right--; // 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로 이동
    }
  }

  return []; // 찾을 수 없는 경우
}

const arr = [2, 7, 11, 15];
const target = 9;

console.log(twoSum(arr, target)); // 출력: [2, 7]

두 포인터를 배열의 양 끝에서 시작하여 합이 target과 일치하는지 확인합니다. 만약 합이 작다면 왼쪽 포인터를 오른쪽으로 이동하고, 합이 크다면 오른쪽 포인터를 왼쪽으로 이동합니다. 이런 식으로 포인터들이 서로 다가가면서 원하는 조건을 찾을 수 있습니다.

투 포인터 알고리즘은 배열이나 리스트에서 서로 다른 두 요소를 조작해가면서 특정한 패턴을 찾는 경우에 효과적으로 사용됩니다.