투 포인터
-
배열에서 기존에 이중 for문을 통해 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘
-
투 포인터에서는 i=0일 때 계산하면서 얻은 정보가 그 다음인 i=1일때 사용한다
-
이분탐색으로 투 포인터 문제를 풀 수 있는 경우도 많으며, 반대로 이분탐색 문제를 투 포인터 문제로 풀 수 있는 경우도 많다
-
투 포인터 문제를 푸는 경우 종료 조건을 잘 정의하는 것이 중요하다!!!
-> 인덱스 하나 차이로 틀리는 경우 종종 발생 -
두 개의 포인터가 한 배열안에서 왼쪽에서 오른쪽으로 이동하는 경우, 한 배열의 양 끝에서 가운데로 오는 경우, 두 배열을 사용하는 경우 등 몇 가지 종류가 있으니 알아둘 것!!
<예제>
https://www.acmicpc.net/problem/2230
- 투 포인터 활용!
- 먼저 정렬을 수행한다!
- arr[ end ] - arr[ start ] 가 문제에서 주어진 값 보다 크면 end 이후 인덱스는 start를 빼는 연산을 할 필요가 없다
-> end는 유지한 채 start를 하나 증가시킨다 - 두 포인터 모두 같은 배열 안에서 왼쪽->오른쪽 이동
https://www.acmicpc.net/problem/1806
- 위 문제와 유사하게 start, end 변수를 통해 풀이 가능
- 합을 나타내는 sum 변수 또한 정의한다
- 두 포인터 모두 같은 배열 안에서 왼쪽->오른쪽 이동
매 순간 최선을 다하자