투 포인터 알고리즘

그게뭔데?

• 배열, 리스트에서 2개의 포인터를 활용하여 특정 조건을 만족하는 부분 구간을 찾는 알고리즘
• 일반적으로는 정렬이 되어있는 배열에 대하여 해당 알고리즘을 수행한다.
• 반복문 2개를 활용하여 탐색하는 방식이 아닌, 한번의 선형 시간(반복문 1개)에서 한번에 두 포인터를 사용하면서 처리하므로 $O(N)$의 시간복잡도를 갖는다.

기본적인 작동과정

1. 배열의 0번째에서 두개의 포인터 (p1, p2)가 시작되도록 설정한다.
   (left, right) 또는 (start, end) 라고 명명해서 풀기도 한다
   
2. 두 포인터 사이의 구간을 보고 조건을 만족하는지 확인한다.
   2-1. 조건을 만족할 경우, 수행을 종료한다.
   2-2. 조건을 만족하지 않았을 경우, 포인터 위치를 이동시킨다
3. 조건을 만족을 찾을 때까지 2번을 반복한다.

예제 - 특정 합에 부합하는 구간 찾기

특정 합을 target, 현재 두 포인터 사이의 값들의 합을 cur이라고 하자.

1. 두 포인터 모두 배열의 인덱스 0을 가리킨다.
2. cur가 target과 같다면 조건에 일치한다. (수행을 종료하거나 카운트를 센다)
3. cur가 target보다 작다면 p2를 1 증가 시킨다.
4. cur가 target보다 크다면 p1을 1 증가 시킨다.
5. 배열을 모두 탐색 할 때까지 위 2-4의 과정을 반복한다.

해당 예제에서는 두 포인터 모두 0에서 시작했지만, 상황에 따라 양 끝이나, 특정 위치에 시작하는 로직을 활용할 수 있다.

슬라이딩 윈도우

• 투포인터 알고리즘에서 두 포인터 사이의 간격이 일정하게 유지되면 슬라이딩 윈도우 알고리즘이라고 한다.
• 투 포인터의 경우 처음에 동일한 위치에서 포인터가 시작하고, 조건에 따라 p2가 멀리 떨어지거나 p1이 쫒아가는 형식이다.
• 슬라이딩 윈도우는 p2-p1의 값이 일정하다고 생각하면 된다.

백준 - 2467.용액

2467. 용액

해설

1. 포인터를 양 끝에 (p1, p2)로 설정한다.
2. 현재 값을 구한다.
   cur = v[p1] + v[p2];
3. best(두 용액의 합의 절대값 중 최소인 값)보다 cur의 절대값이 작다면 갱신한다.
4. p1과 p2를 이동시킨다.
   4-1. cur이 0과 같다면 수행을 종료한다. 0 보다 작아질 수 없기 때문에 최선의 최솟값을 찾은 것이다.
   4-2. cur이 0보다 크다면 오른쪽에 있는 p2의 값을 줄인다. 주어진 수에서 가장 큰 값을 가리키는 것이 p2이기 때문에 해당 값을 줄여보는 것이다.
   4-3. cur이 0보다 작다면 왼쪽에 있는 p1의 값을 키운다. 주어진 수에서 가장 작은 값을 가리키는 것이 p1이기 때문에 해당 값을 키우는 것이다.
5. 4번을 p1 < p2 조건을 만족할 때 동안 계속 반복 수행한다.
   

구현