[알고리즘] 두 포인터 (Two Pointer)

문제를 풀 때마다 그 문제에 적합한 알고리즘이 무엇일지 찾으면서 공부하고 있는데, 알고리즘은 참 다양한 것 같다.

두 개의 예제를 통해서 이 알고리즘을 어떻게 적용하는지 알아보려고 한다.

 

두 포인터(Two Pointers)란?

배열이나 리스트에서 두 개의 포인터(인덱스)를 사용하여 효율적으로 문제를 해결하는 알고리즘이다.

주로 정렬된 배열이나 리스트에서 특정 조건을 만족하는 값을 찾거나, 병합, 탐색할 때 사용된다.

 

두 개의 포인터를 사용

• 배열이나 리스트의 특정 위치를 가리키는 두 개의 포인터를 사용해 문제를 해결
• 주로 시작점과 끝점, 또는 두 배열의 각각 첫 번째 요소에서 시작

 

효율성

• 배열 전체를 한 번만 순회하거나, 필요한 만큼만 순회하기 때문에 시간 복잡도가 O(N) 또는 O(N + M)으로 매우  효율적

 

주로 사용하는 경우

• 정렬된 배열(리스트)에서 탐색, 병합, 교집합, 합의 조건 찾기 등
• 구간 탐색 : 부분합이 특정 값을 넘는 최단 구간 찾기(슬라이딩 윈도우와 결합)

 

 

예시 1 : 두 배열을 병합하는 경우

function mergeSortedArrays(arr1, arr2) {
  let p1 = 0; // 첫 번째 배열의 포인터
  let p2 = 0; // 두 번째 배열의 포인터
  let result = []; // 결과 배열

  // 두 배열이 끝날 때까지 병합
  while (p1 < arr1.length && p2 < arr2.length) {
  	// 정렬된 배열을 만들기 위한 조건문	
    if (arr1[p1] < arr2[p2]) {
      result.push(arr1[p1]); // 첫 번째 배열의 값이 작으면 추가
      p1++; // 첫 번째 배열 포인터 이동
    } else {
      result.push(arr2[p2]); // 두 번째 배열의 값이 작으면 추가
      p2++; // 두 번째 배열 포인터 이동
    }
  }

  // 남은 요소 처리
  while (p1 < arr1.length) result.push(arr1[p1++]);
  while (p2 < arr2.length) result.push(arr2[p2++]);

  return result; // 병합된 배열 반환
}

// 테스트
let arr1 = [1, 3, 5];
let arr2 = [2, 3, 6, 7, 9];
console.log(mergeSortedArrays(arr1, arr2)); // [1, 2, 3, 3, 5, 6, 7, 9]

 

 

예제 2 : 두 수의 합 찾기

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

  while (start < end) {
    const sum = arr[start] + arr[end]; // 두 포인터가 가리키는 값의 합

    if (sum === target) {
      return [arr[start], arr[end]]; // 합이 target이면 반환
    } else if (sum < target) {
      start++; // 합이 target보다 작으면 start를 오른쪽으로 이동
    } else {
      end--; // 합이 target보다 크면 end를 왼쪽으로 이동
    }
  }

  return null; // target이 되는 조합이 없는 경우
}

// 테스트
let arr = [1, 2, 3, 4, 6, 8, 10];
let target = 10;
console.log(twoSum(arr, target)); // [2, 8]

 

 

장점과 단점

이렇게 두 포인터 알고리즘을 사용하면 시간 복잡도가 작고 추가 메모리 사용이 적기 때문에 효율적이다.

그리고 정렬된 배열에서 조건을 탐색하는데 최적화 되어 비교적 간결하다.

 

하지만, 정렬되지 않은 배열에서는 사용할 수 없거나 먼저 정렬해야 한다. 그리고 두 포인터로 맨 앞과 뒤에서부터 탐색해나갈 수 있어야하기 때문에 양방향 탐색이 가능해야 사용할 수 있다.

 

입력값의 범위가 크거나, 시간 제한이 있는 문제의 경우 O(N) 또는 O(N + M)의 시간복잡도를 갖는 두 포인터 알고리즘을 적용하는 것이 적합할 수 있다.

 

 

그럼 오늘은 이만~!

안뇽 !