투 포인터 알고리즘과 슬라이딩 윈도우 알고리즘

두 알고리즘의 공통점

투 포인터 알고리즘과 슬라이딩 윈도우 알고리즘은 1차원 배열을 2회 이상 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N) 으로 줄일 수 있다는 공통점이 있다.

두 알고리즘의 차이점

부분 배열 길이의 변화 여부가 두 알고리즘의 차이점이다.

• 투 포인터 알고리즘 - 부분 배열의 길이가 가변적
• 슬라이딩 윈도우 알고리즘 - 부분 배열의 길이가 고정적

투 포인터 알고리즘

연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘

연속되고 가변적인 것이 특징이다.

투 포인터 알고리즘은 2가지 유형이 존재한다.
1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우
2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우

예제

정수로 이루어진 배열에서 연속된 부분 배열의 합이 특정 값(target)을 이루는 부분 배열의 개수를 구하는 문제가 있다고 가정하자.

두 포인터 변수의 이동 조건은 아래와 같다.
1) 부분 배열의 합이 target보다 크거나 같으면 Left += 1 (부분 배열의 길이를 줄여 합을 빼준다)
같을 때 Left를 더해주는 이유: 다음 배열을 탐색하기 위해

2) 부분 배열의 합이 target보다 작으면 Right += 1 (부분 배열의 길이를 늘려 합을 더해준다)

3) 부분 배열의 합이 target과 같으면 count += 1

슬라이딩 윈도우 알고리즘

투 포인터와 유사하지만 길이(크기)가 고정적인 부분 배열을 사용한다는 것이 특징이다.

투 포인터 알고리즘은 부분 배열의 길이가 가변적이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요하다.
하지만, 슬라이딩 윈도우 알고리즘은 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝을 어딘지 알 수 있다.

주어진 문제가 부분 배열의 합을 구하는 것이라고 할 때, 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후 겹치는 부분이 존재한다.
즉, 기존 구간에서 빠지게 되는 왼쪽 값을 삭제하고 새 구간에 포함되는 값을 추가해주면 된다.

🐢 Reference

https://velog.io/@codenmh0822/투-포인터-슬라이딩-윈도우-구간-합-알고리즘
https://coder-in-war.tistory.com/entry/개념-36-Two-Pointer투포인터-Sliding-Window슬라이딩-윈도우
https://ansohxxn.github.io/algorithm/twopointer/