[알고리즘] Two-Pointers Algorithm (투 포인터 알고리즘)

정의

• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을때 까지 탐색하는 알고리즘
• 배열이나 리스트에 순차적으로 접근해야 할 때 두개의 포인트의 위치를 기록하면서 처리한다
• 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)의 시간복잡도로 단축 시킬 수 있다
• 이분탐색 알고리즘과 유사한 방식이다

 

동작 방식

• 왼쪽 left, 오른쪽 right 또는 start, end 이런 식으로 포인트의 변수 이름을 지정한다
• 조건은 항상 두 포인터의 관계는 left <= end 여야 한다

 

1. 초기화 

 

두개의 포인터를 초기화 한다, 이 포인터들은 배열의 시작과 끝 또는 특정 위치에서 시작할 수 있다

 

2. 반복 처리

 

반복문을 사용하여 두 포인터가 특정 조건을 만족할 때까지 이동한다 여기에서 포이넡의 이동 방향은 문제에 따라 다를 수 있다

 

3. 조건 체크

 

포인터가 가리키고 있는 요소를 비교하거나 합산하여 조건을 확인하고 만족한다면 필요한 작업을 수행하고 포인터를 이동시킨다

 

4. 포인터 이동

 

조건에 따라 적절히 이동시킨다

 

5. 종료 조건

 

포인터가 서로 교차하거나 더 이상 조건을 만족하지 않을때 반복문을 종료한다

---

이분탐색 vs 투 포인터 알고리즘

차이점

 

사용조건

• 이분탐색 : 정렬된 배열
• 투포인터 : 정렬 여부 상관 없음

 

목적

• 이분 탐색 : 특정 값의 존재 여부 및 위치 찾기
• 투 포인터 : 구간 내 조건 만족하는 요소 찾기

 

시간 복잡도

• 이분 탐색 : O(log n)
• 투 포인터 : O(n)

 

알고리즘 방식

• 이분 탐색 : 반복적으로 배열을 반으로 나눔
• 투 포인터 : 두개의 포인터로 배열을 순회

 

적용예시

• 이분 탐색 : 값 검색, 특정 값 위치 찾기
• 투 포인터 : 두 수의 합, 부분 배열 합

 

이분탐색 관련 글

https://hyeonni.tistory.com/20

[알고리즘] 이분 탐색 / 이진 탐색 Java

---

투 포인터 문제

 

https://hyeonni.tistory.com/75

[백준] 1644 소수의 연속합 - Java