[C++/코테] 투 포인터 - 개념, 백준 예제

투 포인터

• 배열에서 원래 이중 for문으로 $O(N^2)$에 처리되는 작업을 2개의 포인터의 움직임으로 $O(N)$에 해결하는 알고리즘
• 투포인터와 이분탐색은 호환되는 문제가 많다.
• 인덱스 하나 차이로 오류가 날 수 있음을 주의해야 한다.

연습문제

백준 2230 수 고르기: https://www.acmicpc.net/problem/2230

✔️ 배열을 정렬한 뒤 st와 en 을 활용하여 차이 값을 구해본다. 이 때 각 st에 대해 모든 en을 보는 것이 아니라, 이전의 en 값을 가지고 있다가 써먹는 것.

✔️반복을 멈추는 조건과 예외처리에 주의한다.

2230번: 수 고르기

백준 1806 부분합: https://www.acmicpc.net/problem/1806

✔️ 배열을 정렬한 뒤 st와 en 을 활용하여 차이 값을 구해본다.

✔️ 투포인터는 $O(N)$, 이분탐색으로 해결하면 $O(NlogN)$ 소요된다.

1806번: 부분합

백준 10025 게으른 백곰: https://www.acmicpc.net/problem/10025

✔️ 투 포인터의 응용형인 슬라이딩도어 알고리즘을 활용할 수 있다.

10025번: 게으른 백곰

---

출처: https://blog.encrypted.gg/1004