노트

투 포인터

Two Pointers

CS#algorithm · 연결된 개념 4개

쉽게 말하면

투 포인터는 키 순서로 선 줄의 양 끝에 한 명씩 서서 짝을 찾는 방식이에요. 두 사람 키의 합이 목표보다 크면 큰 쪽이, 작으면 작은 쪽이 한 칸 안으로 들어오니 모든 짝을 다 재 보지 않아도 돼요.

비유가 깨지는 곳 어느 쪽이 움직일지 알 수 있는 건 줄이 키 순서로 서 있어서예요. 정렬되지 않은 입력에서는 이 판단 근거가 사라져요. 두 포인터가 같은 방향으로 함께 움직이는 모양도 있어요.

배열이나 문자열에서 위치를 가리키는 포인터 두 개를 두고, 조건에 따라 움직여 가며 답을 찾는 패턴. 추가 메모리 없이(O(1) 공간) 중첩 반복을 한 번의 순회로 줄인다. 보통 정렬된 입력에서 쓴다.

양끝에서 안쪽으로

// 정렬된 배열에서 합이 0인 첫 쌍
function sumZero(arr: number[]) {
  let left = 0
  let right = arr.length - 1
  while (left < right) {
    const sum = arr[left] + arr[right]
    if (sum === 0) return [arr[left], arr[right]]
    if (sum > 0) right-- // 합이 크면 큰 쪽을 줄인다
    else left++ // 작으면 작은 쪽을 키운다
  }
}

같은 방향으로

// 정렬된 배열의 서로 다른 값 개수(입력 배열의 앞쪽을 덮어쓴다)
function countUnique(arr: number[]) {
  if (arr.length === 0) return 0
  let i = 0
  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) arr[++i] = arr[j] // i 앞쪽을 고유값으로 채운다
  }
  return i + 1
}
  • 정렬돼 있다는 사실이 "어느 쪽 포인터를 움직일지"를 결정해 준다
  • 두 정렬 배열 병합(병합 정렬), 퀵 정렬의 분할(퀵 정렬), 회문(Palindrome) 검사에서도 같은 모양이 나온다
  • 두 포인터가 구간의 양끝이 되어 함께 미끄러지면 슬라이딩 윈도우가 된다

다른 패턴은 알고리즘 문제 풀이 접근법.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 연결 리스트

    각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.

  • 이진 탐색

    정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

  • 정렬 알고리즘

    컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

  • 재귀

    함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.

  • 이진 힙

    부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

보기 옵션