[알고리즘] 두 포인터 (Two Pointers)

개요

두 포인터(Two Pointers) 혹은 슬라이딩 윈도우(Sliding Window)라고 부른다.

1차원 배열에서 2개의 포인터를 조작하며 값을 얻는 기법이다.

 

본문

예를 들어 1차원 배열에서 구간 합의 경우의 수를 찾는 문제가 있다고 하자.

브루트포스

위와 같이 브루트포스로 경우의 수를 찾게 된다면 O(N^2)가 될 것이다.

N의 범위가 10만을 넘기기만 해도 시간 초과가 나버리게 된다.

이럴 때 필요한게 두 포인터다.

 

두 포인터(Two Pointers)

front와 back 처럼 두 개의 포인트를 잡고 시작한다.

현재 합이 20보다 작으므로 b를 뒤로 움직여 부분합을 증가시킨다.

합이 20보다 커질 때 까지 b 포인터를 뒤로 움직인다.

20이 된 경우의 수가 있다면 count를 증가시킨다.

위처럼 합이 20보다 커졌을 경우 아래처럼 f를 뒤로 움직여 부분합을 감소시킨다.

위와 같은 루틴을 f와 b가 둘 다 마지막에 도달할 때까지 반복한다.

이렇게 되면 O(N)의 결과를 만들어낼 수 있다.

단 f가 b를 넘어가지 않도록 주의해야 한다.

또한 위와 같은 방식의 투 포인터는 값들이 양수 일 때만 가능하다.

음수가 존재할 경우 포인터를 다음으로 움직였을 때 부분합이 커진다는 보장이 없기 때문에 불가능하다.

 

단, 상황에 따라 양쪽 끝에서 투 포인터를 시작하는 경우도 있다. 이경우 음수도 가능하다.

슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우

기본적으로 두 포인터와 유사하다.

다만 두 포인터를 일정 간격을 두고 함께 증가시킨다.

대표적으로 1차원 배열에서 연속된 N개의 원소의 합이 S가 되는 경우의 수를 구할 때 사용할 수 있다.

 

 

이 외에도 정렬 후 양 끝에서 두 포인터를 잡고 시작하는 방법,

한 개의 포인터를 고정하고 두 개의 포인터를 이동하며  세 개의 원소의 합을 구하는 방법 등 여러 가지 활용이 있다.