PS. 슬라이딩 윈도우 그리고 투포인터

오늘은 투 포인터 관련 문제를 풀다가, 이전부터 정리하고 싶었던 두 가지 기법을 정리하려고 한다. 간단히 개념만 정리하고 끝내겠다.

먼저 슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다. 네트워크에서 사용되던 알고리즘을 문제 풀이에 응용한 경우라고 한다.

투 포인터랑 다른 점은 고정 사이즈의 윈도우를 사용해서 순회를 하는 방식이다. 그리고 투포인터는 보통 정렬 배열을 대상으로 하는데 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다는 차이가 있다. 

그리고 투포인터는 꼭 뭐 앞에서 순차적으로 찾을 필요 없이 양쪽에서 다가와도 되고 문제마다 다르다. 물론 슬라이딩 윈도우도 다르긴 하다. 근데 일단 슬라이딩 윈도우는 사이즈를 고정한 점이 가장 큰 차이다. 

다음은 백준에서 볼 수 있는 슬라이딩 윈도우 대표적인 문제다

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

15961번: 회전 초밥

중복되는 값이 나오기 때문에 이 부분이 따로 처리해줘야 하는 부분인데, 그거 말고는 사이즈 유지하면서 값을 확인해 주면 된다. 보통 슬라이딩 윈도우 풀 때 우선순위 큐나 데크를 많이 사용한다.  

이번에는 투포인터 문제를 보자, 전형적인 투포인터 문제다.

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

1806번: 부분합

보통 이렇게 주어진 배열 내에서 조건에 해당하는 걸 완전 탐색으로 찾으려면 시간 초과가 나기 때문에 투포인터로 많이 접근한다. 포인터 1,2 선언해서 움직이면서 조건에 맞으면 그에 따라 포인터들을 움직이면서 구하는데, 여기서는 값이  원하는 값보다 작다면 한쪽 포인터를 키우고 여기서는 2라고 하자. 만약 값이 조건의 값 이상이면 일단 찾았으니까 답 갱신해주고 1번 포인터를 움직인다. 생각해보면 당연한 게 우리가 만족시키려는 조건을 맞춘 상태니까 줄여가면서 또 찾아보는 거다. 그리고 아니면 다시 2번 움직여주고.  뭐 문제마다 차이가 있는데 보통 이런 식으로 포인터 두 개로 한 번만 돌면서 조건에 맞는 답을 찾아낼 수 있다. 여기서는 O(N) 시간 복잡도를 가진다고 한다.

 

 

참고 및 출처: <파이썬 알고리즘 인터뷰> (박상길 지음 책만 ,2020)