투 포인터(Two Pointer)

개념

---

1차원 배열에서 두 개의 포인터를 이용해서 하나의 포인터를 이용해서 탐색할 때 보다 시간 복잡도를 줄일 수 있는 알고리즘입니다.

 

 

설명

---

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

2003번: 수들의 합 2

해당 문제를 가지고 설명하겠습니다.

 

이 문제는 수열의 연속된 숫자의 합이 일정한 수 M이 되는 경우의 수를 물어보는 문제입니다.

 

문제를 해결하기 위해서 보통 드는 생각은 수열의 첫 번째 숫자부터 그다음 숫자들을 더해 나가다가 M이 되면 카운트하고 M을 넘어버리면 다시 두 번째 숫자부터 숫자들을 더해나가는 방법이 있습니다.

하지만 해당 방법은 O(N^2)으로 시간제한을 초과하게 됩니다.

 

이럴 때 투 포인터를 적용하게 됩니다.

 

1.  시작 포인터(s), 끝 포인터(e)를 인덱스 0에 놓습니다.
2.  e를 늘리면서 숫자들을 더해나갑니다.
3.  더한 수가 M이라면 경우의 수에 +1, 더한 숫자가 M보다 크다면 더하는 것을 멈춥니다
4.  더한 수가 M보다 작을 때까지 s를 늘리면서 숫자들을 빼 나간다.
5.  포인터들이 모든 숫자들을 탐색할 때까지 2 ~ 4 과정을 반복한다.

 

s가 인덱스 0, e가 인덱스 4에 있다고 생각했을 때

s를 인덱스 1로 늘리면서 인덱스 0의 숫자를 빼면 인덱스 2, 3, 4의 숫자들을 더한 것 같은 효과를 주게 됩니다.

이를 통해 시간 복잡도를 O(N)으로 줄여나갑니다.