[알고리즘] Range: Two Pointer

1. Two Pointer

• 조건을 충족하는 구간 혹은 쌍을 찾는 알고리즘 입니다.
• 두 개의 포인터를 동시에 움직여가며 문제를 해결합니다.
• 정렬된 선형 자료구조에서 사용됩니다.
  • 답에 가깝게 접근하기 위한 올바른 포인터 이동을 하기 위해서

 

동작 원리

포인터 설정

• 두 개의 포인터 배치 (배열의 시작과 끝 or 인접한 위치)

 

포인터 이동

• 범위를 좁히거나 넓히는 방식으로 답을 찾아갑니다. 
• 한쪽 또는 양쪽 모두를 이동시킵니다.

 

조건 만족 검사

• 두 포인터의 현재 위치에서 조건을 만족하는지 검사합니다.

 

장점

• 반복을 줄여 시간복잡도를 줄이는 목적을 가지는 알고리즘 입니다.
• O(n)으로 최적화 가능

 

2. 문제

Two Sum

• 배열 중 조건을 만족하는 숫자쌍 찾기

 

문제

• Two Sum 2 - Input Array is sorted (문제) (해설)

 

Fast / Slow

• 배열 내 중복 원소 확인하기
• 링크드리스트 내 사이클 확인하기

 

문제

• Linked List Cycle (문제) (해설)

 

 

출처

• [Median] tarun jain - Two Pointers