[알고리즘] 투 포인터 알고리즘

사용하는 경우

1차원 배열이 있을 경우 리스트에 순차적으로 접근해야 할 때 두 지점을 설정해 해결하는 것.

예를 들어 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 경우

모든 케이스를 조사하는 경우 시간 복잡도는 O(N^2)이 된다.

하지만 투 포인터를 사용하는 경우 end 포인터가 배열의 끝까지 도달하면 종료되기 때문에 복잡도는 O(N)이다.

(시간 복잡도 빅-오 표기법에서는 상수항을 무시하기 때문에 O(2N)같은건 없다!)

 

과정

위의 케이스에서 M = 5라고 가정하고 배열의 구간 합이 5가 되는 지점을 찾는다고 하자

현재 start = 0 end = 0이며, 합 S = 두 포인터가 같기 때문에 0.

end가 뒤로 움직일 때는 새로 포함한 원소를 S에 더하고, start가 뒤로 움직일 때는 새로 넘긴 원소를 S에서 빼는 식으로 현재 [start, end)의 합 S를 매번 쉽게 구할 수 있다.

start = 0, end = 1, S = 1

아직 목표 5에 도달하지 못했다. end 포인터를 + 1

start = 0, end = 2, S = 1 + 2 

end를 1칸 옮기고 기존 S의 값 1에 새로운 값 2를 더하기

start = 0, end = 3, S = 1 + 2 + 3

마찬가지, S = 6이 목표값 5를 넘었다. S > M이 되는 경우 end가 아닌 start 포인터가 바뀐다

start = 1, end = 3, S = 1 + 2 + 3 - 1

이 경우 정답 cnt 를 + 1 해준다. 첫 번째 5 발견

다음 과정으로 넘어가기. S = 1 + 2 + 3 - 1 - 2

S = 3으로 5보다 작아졌다. S < M이라면 다시 end 포인터가 움직인다.

여기서 2번째로 S = 5인 지점을 만났으므로 cnt를 1 증가시켜 준다.

start = end인 경우가 나오면 다시 end를 움직인다

세 번째로 S = 5인 지점을 만난다.

그 이후 조건에 맞춰 포인터를 증가시키다 보면, end가 배열 끝을 가리키게 되어 더이상 증가할 수 없는 상태가 된다.

end = 배열의 길이 N인 경우 종료해도 된다. 더 이상 M이 될 구간이 존재하지 않기 때문.