투포인터 개념

투 포인터

(주로) 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘

 

1. 두 포인터(인덱스)를 시작점(left=0, right=0 또는 left=0, right=마지막인덱스 또는 서로다른 배열 등)으로 초기화한다.

2. 규칙에 따라 포인터를 이동시킨다.

- 같은 배열에서 동일한 방향으로 이동하는 투 포인터

- 같은 배열에서 마주보는 방향으로 좁혀가는 투 포인터

- 서로 다른 배열에서 이동하는 투 포인터

- 여러 형태에서 효율적인 시간 복잡도를 가진다.

3. 두 포인터 중 하나 혹은 둘 모두가 끝에 도달할 때까지 반복한다.

 

 

* 인덱스가 아니더라도 오른쪽(시계방향), 왼쪽(반시계) 거리를 right, left로 둘 수 도 있다. https://yunzae.tistory.com/425

BOJ2118 두개의 탑*

 

 

반복문이 두개라 해서 N제곱이 아니다. 실질적으로 보면 N+N이다.

 

 

 

백준 2470 두 용액 문제를 보면

 

 

 

 

위 코드는 i는 고정시켜서 계속 증가시키도록 하고 right 인덱스만 직접 조절하는 방식의 코드이다.

 

\

위 코드는 left와 right 인덱스를 모두 직접 관리하는 코드이다.

 

 

 

바이너리 서치와 투포인터는 닮아있지만 분명 다른 알고리즘이다.

투 포인터로만 풀 수 있는 문제도 존재