🍡 Two Pointers

intro

🍡 two pointers란 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 이중 for문으로 돌리면 i=0일때의 정보를 i=1일 때 전혀 쓰이지 않지만, two pointers는 i=0일 때의 작업이 i=1일 때의 작업에 쓰인다. 과거 정보를 기억한 채로 효율적이게 index를 O(N)으로 움직이는 알고리즘. 이분탐색 문제를 투포인터로도 풀 수 있는 경우가 많고, 그 반대도 많다. two pointers는 O(N)으로, 각각의 모든 case를 일일이 점검할 필요 없이, 일부 case는 점프하는 경우만 풀이가 가능.

explanation

🍡 위와 같은 배열이 있다고 할 때, a일때 b~i를 돌고 / b일 때 c~i를 도는 형태로 2중 반복문을 돈다면 O(N^2) naive approach가 되며 TLE가 되는 case가 많다. 이 때 two-pointer approach는 두 개의 pointer 시작점을 동시에 a로 둘 수 있고 / 한 개는 a, 나머지는 i에 두거나 / 각각 다른 배열에서 시작하는 경우로 나눌 수 있다. 위 배열을 two-pointer approach로 접근하자면,

: 두 개의 포인터 x와 y가 있고 동시에 왼쪽시작점에서 진행한다고 가정. x는 a부터 i까지 쭉 진행할 예정. x는 a일 때 y가 a부터 d까지 갔다고 하면, 그 다음 x가 b일 때 y가 다시 a부터 시작하는 게 아니라, 이미 진행한 d부터 y가 진행한다. 따라서, x가 b일 때 y가 a, b, c인 case는 무시된다. 즉, two-pointer approach를 쓸 때는 과연 x가 진행하면서 이미 y가 지나친 부분을 상관안해도 되는지 이를 정확히 확인할 필요가 있다. 결국 x는 a부터 i까지 O(N), y도 a부터 i까지 O(N)으로 합 O(N+N) 시간 복잡도가 나오게 된다(x가 a부터 i까지 진행하는 동안 y도 a부터 i까지 한번에 진행하면 된다 보면 기억하기쉽다). 상당히 효율적인 approach로, 이를 사용하기 위해 배열을 임의로 맞추거나(ex) 정렬하거나) x와 y의 시작 위치를 알맞게 바꾸거나 traversing할 배열을 나누거나 합치는 등 다양한 technique 이후 two-pointer approach를 실시한다. 직접 여러 문제 대표 유형을 보면서 어떻게 해당 접근법을 사용하는지 익숙해지자.

examples

🍡 <BOJ S3 3273 두 수의 합>

Q. 서로 다른 양의 정수로 이루어진 한 개의 array에서 서로 다른 두 양의 정수의 합이 X가 되는 쌍의 개수를 구하는 문제 → ① 배열 오름차순 정렬 / ② x는 맨 왼쪽, y는 맨 오른쪽 배치 / ③ 두 포인터가 각각 가리키는 원소의 합이 X보다 크다면 y-=1, X와 맞다면 x+=1, y-=1, X보다 작다면 x+=1

 

🍡 <BOJ S4 2003 수들의 합 2 >

Q. n개의 수로 된 수열에서 i번째부터 j번째 수까지의 합이 M이 되는 경우의 수를 구하는 문제(수열이므로 array 변형 불가) → ① x와 y 모두 배열 맨 왼쪽 위치 / ② x는 고정한 상태에서 누적합이 M이상이 되기 전까지 y 이동, 누적합이 M이라면 ans += 1, 그 다음 x+=1

(부분 수열의 합 A[i] ~ A[j]라고 고정해 놓았기에 누적합으로 바로 대놓고 투 포인터 쓰면 되는 쉬운 문제)  

 

🍡 <BOJ S3 2559 수열 >

Q. n개의 연속된 온도로 이루어진 수열에서 k개의 부분연속수열 최대 누적합 구하는 문제(수열이므로 array 변형 불가) → x와 y모두 배열 맨 왼쪽 위치 /  x는 고정한 상태에서 누적합의 개수가 k개 이상이 되기 전까지 y 이동 / cnt==K라면 ans update와 함께 누적합-=l[x], cnt-=1하고 x 오른쪽 이동 (만약 cnt<K여서 y가 배열 오른쪽 끝까지 다 이동해 더 이상 k개의 누적합을 구할 수 없다면 break)

(k개의 원소로 이루어진 부분연속수열 누적합이라고 i, j 투 포인터 사용은 자명)

 

🍡 <BOJ S4 1940 주몽>

Q. 고유한 번호로 이루어진 갑옷들 중 두 개 갑옷을 골라 M이 되는 경우의 수의 개수를 구하는 문제 (위 3273 두 수의 합과 동일) (다만 N이 15000 이하라 투 포인터 안써도 되는 문제)

 

🍡 <BOJ S1 2531 회전초밥 + G4 15961 회전초밥>

Q. 투 포인터 중 슬라이딩 윈도우 대표 유형. x가 전체 초밥을 돌면서 고정 윈도우 내에 쿠폰 여부에 따라 먹는 초밥 개수 +1 또는 +0. 윈도우가 돌면서 먹을 수 있는 초밥 최댓값 구하는 문제. x와 y모두 첫 초밥부터 시작. y는 index 0 기준 (N-1+k)까지 traverse

 

🍡 <BOJ G4 1806 부분합>

Q. 투 포인터 대표 유형. 고정 수열에서 x와 y 모두 왼쪽 index 부터 시작. 부분합이므로 x 0부터 돌면서 y가 부분합 S이상이 될때까지 진행. 이후 x가 오른쪽으로 이동하고, y는 현재 위치에서 반복적으로 S이상이 될때까지 오른쪽으로 진행. 투 포인터 유형인 이유는, S이상인 부분합 수열에서, 새로운 x일때  y가 굳이 0부터 돌 필요 x. 어차피 S보다 작으므로. 이 때 length까지 추가로 update

 

🍡 <BOJ G3 1644 소수의 연속합 >

Q. 소수만으로 이루어진 배열에서 부분연속수열 누적합이 N인지 알아보는 문제. 에라토스테네스 체로 소수만으로 이루어진 배열을 구하는 것을 제외하고는 위 부분합에서 구하는 투 포인터 알고리즘과 동일

 

🍡 <BOJ G5 2470 두 용액 / G5 2467 용액>

Q. 두 문제 차이는 주어진 배열이 정렬인지 아닌지. 정렬을 해야 투 포인터 알고리즘 사용 가능. 두 용액을 더한 결과가 0에 가장 가까운 쌍을 구하는 문제. x는 왼쪽, y는 오른쪽부터 시작해서, 두 용액을 더한 결과가 양수라면 y를 왼쪽으로, 음수라면 x를 오른쪽으로 이동.

 

🍡 <BOJ G3 2473 세 용액>

Q. 이제 두 용액이 아닌 세 용액의 합이 0에 가까운 쌍을 찾는 문제. N<=5,000이어서 x 한개 반복문으로 잡고 나머지 용액들을 투 포인터로 두 용액 풀이 그대로 적용해 O(nlogn+n*(n+n))에 해결 가능하나, x가 오른쪽으로 이동하면서 x,y,z의 점검 쌍 중복 방지를 위해 y와 z를 0~N-1의 범위가 아닌, x+1~N-1의 범위로 좀 더 시간 단축 가능 (시간복잡도는 동일)

 

🍡 <BOJ G4 13144 List of Unique Numbers>

Q. 고정 수열에서 같은 수가 연속해서 등장하지 않는 부분연속수열의 개수를 구하는 문제. x,y 모두 index 0 왼쪽 시작. x가 오른쪽으로 진행하면서 y가 오른쪽으로 진행한, 이미 중복 유무를 check하였으므로, 그저 ans에 (y-x) 개수만 더해주기. 결론적으로 x와 y모두 한바퀴만 돌 수 있는 시간복잡도 O(N+N) 해결 가능. 투 포인터 아이디어를 떠올려야 하는 문제 

---

Baaarking Dog