Two Pointer 란

• 주로 사용하는 상황: 가변 크기의 부분 배열이나 서브시퀀스를 탐색할 때 사용됩니다. 예를 들어, 특정 조건을 만족하는 두 요소를 찾거나, 연속적인 부분 배열의 합이 주어진 값과 일치하는 부분 배열을 찾는 경우.

• 작동 방식:

  • 두 개의 포인터를 배열의 시작점(left)과 끝점(right)에 놓고, 이 두 포인터를 서로 독립적으로 움직이면서 조건을 만족하는 구간을 탐색합니다.
  • 두 포인터 사이의 구간이 가변적이며, 조건에 따라 포인터가 각각 움직입니다.
  • 예를 들어, left 포인터는 증가하고 right 포인터는 감소할 수 있습니다.

• 주요 특징:

  • 두 포인터가 독립적으로 움직일 수 있어, 윈도우 크기가 가변적입니다.
  • 문제에 따라 O(N) 시간 복잡도에서 O(N²)까지 다양하게 적용될 수 있습니다.
  • 배열의 양 끝에서 출발하여 특정 조건을 만족할 때까지 좁혀가는 방식으로 사용되는 경우가 많습니다.