투 포인터 알고리즘

Line Sweeping 알고리즘

라인을 탐색하면서 무언가를 하는 알고리즘

사실 교차점이나 집합 등 까지 들어가면 고급 알고리즘이지만 

코딩테스트에서는 정렬을 해놓고 순서대로 탐색 하는 정도만 나온다.

 

투 포인터

선형 자료구조에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 배열 또는 원하는 값을 찾는 문제를 풀 때 주로 사용되는 알고리즘.

'정렬된 배열' 에서 두 수의 합 찾기, 연속된 부분배열의 합 찾기에 사용된다.

 

예시 ) 많은 수의 숫자들이 있을 때,

이 중 두개를 합친 값이 x인 순서쌍의 갯수 구하기 문제

 

이를 이중 for문으로 돌리면 시간초과한다.

 

왼쪽 포인터를 0번, 오른쪽 포인터를 맨 뒤로 두고

이게 x라면 왼쪽을 한칸 뒤로 보내거나 오른쪽을 한칸 앞으로 보낸다. (*이는 문제마다 다르다. 두개를 동시에하면 안됨!!!)

while( left < right ) 로 실행해서 겹치는 경우 종료됨. 

 

투 포인터의 핵심은 low와 hi가 각각 한 방향으로 진행해야한다는 점. (왔다갔다하면안된다)

 

예제 2

 

이 문제의 경우에는

low와 hi를 0으로 두고서 뒤쪽 방향으로 증가시키면서 풀었다!

sum이 같거나 큰 경우 low를 진행,

sum이 작은 경우 hi를 진행.

 

구간합을 구하는 경우 sum을 따로 관리해서 그 값에서 빼는 것을 잊지말자!

 

 

예제 3

https://www.acmicpc.net/problem/13144

 

a 포인터를 앞부터 뒤로 이동시키다가 같은 수를 만나면 

그 이전까지 a가 포함해서 만들 수 있었던 모든 경우의 수 (a - b) = 6 만큼을 ret에 합산하고

b 포인터를 다음 위치로 이동시켜서 1을 연산에서 아예 제외시킨다 

 

그 다음 a 를 다음 칸으로 갔는데 또다시 중복 수인 2가 나와버렸음.

따라서 2로 만들 수 있었던 경우의 수 인 ( a - b ) = 6 만큼을 ret 에 합산하고 진행한다.

 

a가 끝 n 까지 도달해버리면

남은 숫자들인 3, 1, 2 가지고 모든 조합을 만들면 되는데, 

따져보면 연속된 숫자인 경우만 포함하니까

(3) (1) (2)

(3, 1) (1, 2)

(3, 1, 2)

등차수열의 합으로 구할 수 있다. (이게 등차수열의 합이다! 가 아니라 따져보니까 등차수열의 합)