[알고리즘] 투 포인터와 슬라이딩 윈도우

투 포인터

투 포인터

S, E 혹은 L, R이라는 두가지 변수를 지정하여, 인덱싱을 저장하고자 한다. (두 포인터)

이후 각 포인터들을 이용하여 목표를 달성하자.

문제의 경우는 [3, 7, 2, 1, 6, 9, 11, 14] 라는 배열에서 합이 9인 연속된 부분을 찾는것

S, E 포인터 모두 인덱스 0번에서 시작하여 현재 합이 9보다 작다면 E를 한칸 오른쪽으로, 크다면 S를 한칸 오른쪽으로 이동하며 값을 구한다.

여러가지 방면에서 활용할 수 있으며, 이때 E-S가 일정하다면 슬라이딩 윈도우 라고 한다.

 

 

슬라이딩 윈도우

슬라이딩 윈도우

투 포인터 와 비슷하지만, 두 포인터 사이 간격이 일정해서 마치 유리창을 미닫는 모양이라고 하여 슬라이딩 윈도우라고 불리는 알고리즘

위 그림은 N = 8인 배열에서 K = 3의 길이를 가지는 부분수열의 합이 7인 경우를 찾는 그림이다

나이브하게 접근한다면 N의 길이를 가지는 배열에서 K의 길이를 가지는 부분수열의 합을 모두 검사한다면
부분수열 한번의 검사에 O(K) 번의 시간이 걸리므로 O(N\*K) 의 시간 복잡도가 되겠지만,

슬라이딩 윈도우 기법을 이용한다면 E가 한칸 움직이면서 더해주고, S가 한칸 움직이면서 그 칸을 빼주는 방법으로 연산을 하면 O(N)으로 계산이 가능하다.