알고리즘 - 3. Two Pointers (투 포인터)

Two Pointers를 사용해야 할 때

Two Pointers는 서로 다른 위치에 있는 요소들 간의 관계를 체계적으로 탐색해야 할 때 사용합니다. 어떤 조건에 기반해 포인터를 이동시켜 진행하면서 가능성들을 제거해 나갈 수 있을 때 이 기법이 작동합니다.

정렬된 배열이 필요한 문제들

타겟을 가진 Two Sum (클래식한 사용 사례 - 어떤 포인터를 움직일지 알기 위해 정렬이 필요)
Three Sum / Four Sum (중첩된 포인터 쌍 사용 - 제거를 위해 순서가 필요)
특정 차이를 가진 쌍 찾기 (영역을 제거하기 위해 순서가 필요)

정렬되지 않은 배열에서 작동하는 문제들

가장 많은 물을 담는 컨테이너 (인덱스가 순서를 제공하지, 값이 아님)
회문 검증 (양 끝에서부터의 자연스러운 순서)
배열/문자열 뒤집기 (양 끝에서 교환)
파티셔닝 문제 (네덜란드 국기 문제, 퀵소트 파티션)
빠른/느린 포인터 변형 (사이클 감지, 중간 요소 찾기)
읽기/쓰기 포인터로 중복 제거 (스캔하면서 불변 조건 유지)

예제 문제 (정렬된 배열)

타겟 합을 가진 쌍 찾기: 정렬된 정수 배열 [1, 3, 4, 6, 8, 9, 11]과 타겟 합 14가 주어졌을 때, 타겟에 합산되는 두 수를 찾습니다.

위치 0과 6의 포인터로 시작: 1 + 11 = 12 (너무 작음)
왼쪽 포인터를 위치 1로 이동: 3 + 11 = 14 (찾았다!)
답: 인덱스 [1, 6]의 요소들, 즉 3과 11

정렬 없이는 O(n²)의 비교가 필요합니다. 정렬된 배열에서 Two Pointers를 사용하면 O(n) 시간에 찾을 수 있습니다.

예제 문제 (정렬되지 않은 배열)

가장 많은 물을 담는 컨테이너: 높이 [1, 8, 6, 2, 5, 4, 8, 3, 7]이 주어졌을 때, x축과 함께 가장 많은 물을 담는 컨테이너를 형성하는 두 선을 찾습니다.

위치 0과 8의 포인터로 시작: 면적 = 8 × min(1, 7) = 8
왼쪽 포인터(더 작은 높이)를 위치 1로 이동: 면적 = 7 × min(8, 7) = 49
포인터가 만날 때까지 계속하며 최대 면적을 추적
답: 인덱스 [1, 8]로 면적 49

정렬이 필요 없습니다! 인덱스 자체가 너비를 제공하고, 더 큰 면적을 찾을 가능성을 위해 더 작은 높이의 포인터를 이동시킵니다.

가장 중요한 통찰

Two Pointers는 각 포인터 이동으로 불가능한 옵션들을 제거하면서 해 공간을 체계적으로 탐색합니다 - 정렬 순서(합 문제의 경우)나 위치적 제약(기하학적 문제의 경우)을 통해, 각 비교는 하나가 아닌 많은 가능성에 대한 지식을 제공합니다.

멘탈 노트: "위치 i에서 끝나는 최선의 부분 배열"에 초점을 맞추는 Kadane의 알고리즘과 Sliding Window와 달리, Two Pointers는 서로 다른 위치에 있는 요소들 간의 관계에 초점을 맞춥니다. 당신은 어떤 위치에도 고정되어 있지 않습니다 - 대신 비교에 기반해 두 개의 독립적인 포인터를 움직여서 쌍/관계를 탐색합니다. Kadane이 "이 위치에서 확장할까 재시작할까?"라고 묻는 반면, Two Pointers는 "더 나은 관계를 찾기 위해 어떤 포인터를 움직여야 할까?"라고 묻습니다.

멘탈 모델 비교

Kadane의 알고리즘: "위치 i에서 끝나는 최선의 부분 배열은 무엇인가?" - 끝점에 고정
Sliding Window: "위치 i에서 끝나는 최선의 윈도우는 무엇인가?" - 오른쪽 경계에 고정
Two Pointers: "다음에 탐색할 두 위치 간의 관계는 무엇인가?" - 앵커 없음, 순수한 탐색

위치적 고정의 부재가 Two Pointers를 독특하게 만듭니다 - 비교에 기반해 어느 포인터든 자유롭게 움직일 수 있고, 해 공간의 전체 영역을 체계적으로 제거할 수 있습니다.

결정 프레임워크

정렬된 배열 문제의 경우 (Two Sum)

합이 너무 큰가? 오른쪽 포인터를 왼쪽으로 이동 (합을 감소)
합이 너무 작은가? 왼쪽 포인터를 오른쪽으로 이동 (합을 증가)
합이 타겟과 같은가? 쌍을 찾았다!

정렬되지 않은 배열 문제의 경우 (가장 많은 물을 담는 컨테이너)

더 작은 높이를 가리키는 포인터를 이동
왜? 더 작은 높이가 면적을 제한하므로, 잠재적으로 더 높은 선을 찾음
지금까지 본 최대 면적을 추적

코드 예제

정렬된 배열: Two Sum

function twoSum(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const currentSum = nums[left] + nums[right];

    // DECISION FRAMEWORK
    if (currentSum > target) {
      // 합이 너무 큼: 오른쪽 포인터를 왼쪽으로 이동해 감소
      right--;
    } else if (currentSum < target) {
      // 합이 너무 작음: 왼쪽 포인터를 오른쪽으로 이동해 증가
      left++;
    } else {
      // 타겟 합을 찾았다
      return [left, right];
    }
  }

  return null; // 유효한 쌍을 찾지 못함
}

// 문제의 데이터를 사용한 예제
const sortedArray = [1, 3, 4, 6, 8, 9, 11];
const targetSum = 14;
const result = twoSum(sortedArray, targetSum);
console.log(result); // [1, 6] - 3과 11의 인덱스

정렬되지 않은 배열: 가장 많은 물을 담는 컨테이너

function maxArea(heights: number[]): number {
  let left = 0;
  let right = heights.length - 1;
  let maxWater = 0;

  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(heights[left], heights[right]);
    const currentWater = width * minHeight;

    maxWater = Math.max(maxWater, currentWater);

    // DECISION FRAMEWORK
    if (heights[left] < heights[right]) {
      // 왼쪽 벽이 제한 요인, 더 높은 왼쪽 벽을 찾으려고 시도
      left++;
    } else {
      // 오른쪽 벽이 제한 요인, 더 높은 오른쪽 벽을 찾으려고 시도
      right--;
    }
  }

  return maxWater;
}

// 문제의 정렬되지 않은 배열을 사용한 예제
const heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(heights)); // 49 (인덱스 1과 8 사이)

정렬되지 않은 배열: 회문 체크

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    // DECISION FRAMEWORK
    if (s[left] !== s[right]) {
      return false; // 불일치 발견
    }
    left++;
    right--;
  }

  return true; // 모든 문자가 일치
}

// 어떤 문자열에서도 작동 - 정렬 필요 없음!
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false

정렬된 배열을 넘어서: Two Pointers가 여전히 작동하는 경우

일반적인 오해: "Two Pointers는 정렬된 배열에서만 작동한다."

이것은 틀렸습니다! Two Pointers는 다음을 할 수 있을 때 작동합니다:

조건에 기반해 포인터를 움직여 체계적인 진행을 만들기
가능성을 제거하거나 해 공간을 체계적으로 탐색하기
어떤 구조(꼭 정렬 순서일 필요는 없음)를 사용해 중복 비교를 피하기

왜 가장 많은 물을 담는 컨테이너는 정렬되지 않은 배열에서 작동하는가

핵심 통찰: 인덱스 자체가 우리가 필요한 순서를 제공합니다!

너비는 항상 right - left (포인터가 수렴하면서 감소)
더 작은 높이의 포인터를 움직이는 이유는 그것이 제한 요인이기 때문
각 이동은 더 작은 너비지만 잠재적으로 더 큰 높이의 컨테이너를 탐색
위치(값이 아닌)가 너비를 결정하므로 정렬이 필요 없음

Two Pointers를 가능하게 하는 다양한 구조들

정렬된 값 → 합/차이 문제를 위한 방향성 있는 결정을 가능하게 함
위치 인덱스 → 기하학적 문제를 위한 자연스러운 순서를 제공
문자열/배열의 끝 → 회문/역순 문제를 위한 자연스러운 경계
불변 조건 유지 → 인플레이스 수정을 위한 읽기/쓰기 포인터

"구조"는 정렬된 값일 필요가 없습니다 - 체계적인 탐색을 가능하게 하기만 하면 됩니다!

의심 해소 (정렬된 배열의 경우)

일반적인 의심: "알고리즘은 타겟과의 비교에 기반해 포인터를 움직이는데, 올바른 쌍을 건너뛰면 어떻게 되나요? 한 번 요소를 지나가면 다시 돌아가지 않는데 - 이렇게 하면 해를 놓칠 수 있지 않나요?"

이런 생각이 틀린 이유

핵심 깨달음: 모든 포인터 이동은 불가능한 쌍들의 전체 클래스를 제거합니다!

합 < 타겟일 때 → 왼쪽 포인터를 오른쪽으로 이동 → 현재 왼쪽 요소와의 모든 쌍 제거 (모두 너무 작음)
합 > 타겟일 때 → 오른쪽 포인터를 왼쪽으로 이동 → 현재 오른쪽 요소와의 모든 쌍 제거 (모두 너무 큼)

실행 중인 체계적 탐색

타겟 7로 [1, 3, 4, 6, 8]을 추적해봅시다:

단계 1: left=0 (1), right=4 (8) → sum=9 > 7
        제거: 8과 요소≥1의 모든 쌍
        right를 3으로 이동

단계 2: left=0 (1), right=3 (6) → sum=7 = 7  → 찾았다!

단계 1에서 무슨 일이 일어났는지 주목하세요:

1+8=9를 타겟 7과 비교했습니다
9 > 7이므로, 8과 1, 3, 4, 또는 6의 쌍은 모두 ≥ 9가 될 것임을 압니다
따라서 8을 고려에서 완전히 안전하게 제거할 수 있습니다

방향성 있는 이동이 완전성을 보장하는 이유

알고리즘은 이 불변 조건을 유지합니다:

지나간 왼쪽 요소들과의 모든 쌍은 완전히 탐색됨
지나간 오른쪽 요소들과의 모든 쌍은 완전히 탐색됨
남은 미탐색 공간은 체계적으로 줄어들어 비게 됨

보장: 정렬된 순서 덕분에 단일 비교로 어떤 전체 영역이 불가능한지 알 수 있어, 각 포인터 이동으로 많은 쌍을 제거할 수 있습니다. 이 체계적인 탐색은 모든 불가능한 쌍을 건너뛰면서 모든 실행 가능한 쌍을 정확히 한 번 확인하도록 보장합니다!

마법은 정렬된 배열에 있습니다: 하나의 쌍과의 비교를 많은 쌍에 대한 지식으로 변환해, O(n²) 대신 O(n) 시간에 전체 해 공간을 탐색할 수 있게 합니다.

의심 해소 (정렬되지 않은 배열의 경우)

일반적인 의심: "Two Pointers가 어떻게 정렬되지 않은 배열에서 작동할 수 있나요? 어떤 포인터를 움직일지 알기 위해 정렬이 필요하지 않나요?"

이런 생각이 틀린 이유

핵심 깨달음: 정렬은 구조를 만드는 하나의 방법일 뿐입니다. 어떤 활용 가능한 구조든 있으면 Two Pointers가 작동합니다!

정렬되지 않은 배열의 경우, 구조는 다음에서 나옵니다:

위치적 관계 (가장 많은 물을 담는 컨테이너: 인덱스가 너비를 결정)
자연스러운 경계 (회문: 끝에서 안쪽으로 비교)
유지되는 불변 조건 (파티셔닝: 포인터 앞의 요소들이 조건을 만족)

가장 많은 물을 담는 컨테이너 - 왜 정렬이 필요 없는가

높이 [1, 8, 6, 2, 5, 4, 8, 3, 7]을 생각해봅시다. 알고리즘이 작동하는 이유:

너비는 인덱스로 결정되지, 값으로 결정되지 않음: 위치 i와 j 사이의 거리는 항상 |i - j|
포인터를 움직이면 항상 너비가 감소: 이는 인덱스 위치에 의해 보장됨
더 높은 선을 기대하며 더 짧은 선을 움직임: 너비가 감소하므로, 더 높은 선만이 더 큰 면적을 줄 수 있음

중요한 통찰: 인덱스 자체가 우리가 필요한 순서를 제공합니다. 우리는 쌍을 찾기 위해 값을 비교하는 것이 아니라, 값의 순서와 무관하게 존재하는 위치적 관계를 사용하고 있습니다.

왜 정렬이 실제로 일부 문제를 망가뜨리는가

가장 많은 물을 담는 컨테이너의 경우, 정렬은 위치적 관계를 파괴합니다:

원본: [1, 8, 6, 2, 5, 4, 8, 3, 7] - 인덱스가 중요함
정렬됨: [1, 2, 3, 4, 5, 6, 7, 8, 8] - 원래 위치가 사라짐!

문제는 요소들의 원래 위치에 의존하지, 정렬된 순서에 의존하지 않습니다.

기억하세요: Two Pointers는 구조가 필요하지, 꼭 정렬된 값이 필요한 것은 아닙니다. 당신의 특정 문제에서 체계적인 탐색을 가능하게 하는 구조가 무엇인지 식별하세요.

변형과 패턴

빠른 포인터와 느린 포인터 (토끼와 거북이)

포인터가 다른 속도로 움직이는 특별한 변형:

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next; // 1단계 이동
    fast = fast.next.next; // 2단계 이동

    // DECISION FRAMEWORK
    if (slow === fast) {
      return true; // 사이클 감지
    }
  }

  return false; // 사이클 없음
}

인플레이스 수정을 위한 읽기/쓰기 포인터

이 패턴은 배열을 인플레이스로 수정하기 위해 같은 방향으로 다른 속도로 움직이는 두 포인터를 사용합니다:

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let writePointer = 0; // 다음 고유 요소를 쓸 위치

  for (let readPointer = 1; readPointer < nums.length; readPointer++) {
    // DECISION FRAMEWORK
    if (nums[readPointer] !== nums[writePointer]) {
      writePointer++;
      nums[writePointer] = nums[readPointer];
    }
  }

  return writePointer + 1; // 고유 요소의 길이
}

// 예제: [1,1,2,2,3]은 [1,2,3,2,3]이 되고 길이 3

작동 방식:

읽기 포인터는 새로운 고유 값을 찾아 전체 배열을 스캔합니다
쓰기 포인터는 다음 고유 값을 쓸 위치를 표시합니다
읽기 포인터가 쓰기 포인터의 값과 다른 값을 찾으면:
1. 쓰기 포인터를 앞으로 이동
2. 새로운 고유 값을 쓰기 위치에 복사
배열이 인플레이스로 수정됩니다: [1,1,2,2,3] → [1,2,3,2,3]
- 처음 3개 요소가 이제 고유 값들입니다: [1,2,3]
- 나머지 요소 [2,3]은 무시됩니다 (새로운 길이를 넘어섰으므로)
3을 반환하여, 처음 3개 요소가 모든 고유 값을 포함함을 나타냅니다

이 패턴은 특정 요소는 유지하면서 다른 요소는 제거하고 싶은 인플레이스 배열 수정에 강력하며, O(n) 시간과 O(1) 공간으로 실행됩니다.