Skip to content

Latest commit

 

History

History
34 lines (22 loc) · 1.03 KB

two-pointers.md

File metadata and controls

34 lines (22 loc) · 1.03 KB

투 포인터 기법

투 포인터 기법(Two Pointers)은 두 개의 인덱스를 움직이면서 구간이나 쌍을 처리하는 방식입니다.

핵심 생각

  • 왼쪽 포인터와 오른쪽 포인터를 상황에 따라 움직인다.
  • 전체를 다시 보지 않고 한 번에 처리할 수 있는 경우가 많다.

언제 떠올리면 좋은가

  • 연속 구간 문제
  • 정렬된 배열에서 두 수의 합
  • 구간 길이, 합, 조건 만족 여부를 빠르게 확인할 때

파이썬 구현 포인트

left = 0  # -> 왼쪽 포인터
right = 0  # -> 오른쪽 포인터
  • 보통 포인터는 한 방향으로만 움직이게 설계한다.
  • 정렬 후 쓰는지, 원래 순서 유지가 필요한지 먼저 본다.

실수하기 쉬운 것

  • 포인터가 뒤로 가게 만들어 시간복잡도가 늘어나는 것
  • 정렬이 필요한데 안 하는 것
  • 구간 의미를 명확히 안 정하는 것

기억할 문장

  • 두 인덱스를 한 방향으로 밀 수 있으면 투 포인터 기법을 본다.