투 포인터

투 포인터는 배열과 리스트가 주어졌을 때 탐색의 시간 복잡도를 줄이는 목적의 알고리즘이다.

구간, 연속된, 두 수, 세 수 등의 키워드가 보인다면 투 포인터를 떠올려보자.
정렬되어 있다면 투 포인터일 확률이 더 높다.

투 포인터의 설명

주어진 원소의 수가 10,000,000과 같이 너무나 크다고 가정하자.
이럴 때 O(n^2)의 시간 복잡도를 내는 연산은 시간 초과가 된다.

구간을 유지하면서 줄이거나 늘릴 수는 없을까? 라는 생각에서 출발한다.

두 개의 포인터

투 포인터의 이름과 같이 두 개의 포인터를 사용한다.
하나는 구간의 시작, 하나는 구간의 끝을 가리키는 포인터다.

이 두 개의 포인터가 가리키는 구간 내부에서 문제의 조건이 주어진다.

1 2 3 4 5
↑     ↑
S     E

S = 시작 포인터
E = 종료 포인터

포인터의 이동

포인터의 이동은 구간의 끝을 가리키는 포인터가 배열의 끝이나 주어진 수에 도달했을 때 종료된다.

예를 들어, 15를 만드는 연속된 수 구간을 찾는다고 가정하자.
구간의 끝을 가리키는 포인터가 15를 넘어간다면 불필요한 탐색이 발생한다.

따라서 여기서 포인터의 이동은 끝을 가리키는 포인터가 15를 가리키면 종료된다.

또한 포인터는 다음의 조건을 만족할 때 이동한다.

• 시작 포인터: 비교 조건보다 현재 조건이 큰 경우
• 종료 포인터: 비교 조건보다 현재 조건이 작은 경우

시작 포인터의 이동은 수를 제외하는 것이고, 종료 포인터의 이동은 수를 추가하는 것이다.

투 포인터의 예시

연속된 자연수의 구간 중 합이 15가 되는 구간의 개수를 구한다고 해보자. 대충 생각나는 조합은 다음과 같다.

※ 1 + 2 + 3 + 4 + 5
※ 4 + 5 + 6
※ 7 + 8
※ 15

먼저 포인터의 이동 조건을 결정한다.

• 시작 포인터: 구간의 합이 15보다 클 경우
• 종료 포인터: 구간의 합이 15보다 작을 경우

이를 토대로 코드를 작성한다.

while(end_index != 15)
{
    if(sum == 15)
    {
        count++;
        end_index++;
        sum += end_index;
    }
    else if(sum > 15)
    {
        sum -= start_index;
        start_index++;
    }
    else
    {
        end_index++;
        sum += end_index;
    }
}