Sliding window와 Two pointer


작성일 : 2018-06-21 00:30:27
조회수 : 1320


본문

Sliding window 와 Two pointer는 연속된 부분수열(또는 구간) 에서 정답을 찾아야 되는 문제에서 $O(N^2)$의 시간복잡도를 $O(N)$ 으로 줄일 수 있는 획기적인 알고리즘입니다.


기본적으로 start pointer(sp)와 end pointer(ep)를 잡고 구현하는 것은 동일하지만, 두 기법의 차이는 Sliding window는 $len(ep-sp)$이 항상 일정한 반면, Two pointer에서는 가변적으로 변할 수 있다는 것이 차이입니다.


대표적인 Two pointer를 사용할 수 있는 문제는 "특정 수열에서 연속된 부분수열 중 합이 $S$가 되는 수열의 개수를 구하는" 문제입니다. 이를 Brute force로 구현하려고 하면 시작점에 대해 존재할 수 있는 모든 길이를 다 검사하는 방식의 구현이 되어 $O(N^2)$이 되지만, Two pointer를 이용하여 합이 $S$보다 작으면 ep를 증가시키고, $S$보다 같으면 정답을 증가시키는 방식으로 구현합니다.


Sliding window를 적용할 수 있는 문제는 수열의 연속된 부분수열 중 길이가 $l$인 부분수열에 대해, 합이 최대(최소)인 수열을 구하는 문제에 적용할 수 있습니다. 포인터를 움직일 때마다 ep에 있는 값을 더하고, sp를 움직이기 전 가리키고 있는 값을 빼주고 움직이면 됩니다.

Sliding window와 Two pointer - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.