[알고리즘] 투 포인터(two pointer), 슬라이딩 윈도우(Sliding window)

이 두 알고리즘은 O(N2)이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다. 이 두 알리고리즘의 차이점으로 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 슬라이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적이다.

투 포인터 (two pointer)

투 포인터 알고리즘은 배열에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘이다.

투 포인터 알고리즘에서는 대표적으로 두 개의 유형이 존재한다.

• 2개의 포인터 변수 시작점이 배열의 시작점인 경우
• 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점 0 과 끝점 arr.length-1 에 위치한 경우

투 포인터로 해결해야하는 문제에서는 모든 배열의 값들을 탐색하여 특생 조건을 일치시키는 개수 또는 최소/최대값을 찾는 문제이다. 두 개의 포인터 변수를 이동해가면서 부분 배열을 구하고 원하는 값을 찾으면 된다.

---

슬라이딩 윈도우 (Sliding window)

슬라이딩 윈도우 알고리즘은 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 해결하는 알고리즘이다. 오른쪽으로 한 칸씩 옮기면서 기존 구간에서 가장 왼쪽 칸의 값을 삭제하고 새 구간의 값을 추가해주는 방식으로 탐색한다.