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

투 포인터와 슬라이딩 윈도우 비교

• 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야할 경우 O(N^2) 이상의 시간 복잡도를, 부분 배열을 활용하여 O(N) 으로 줄일 수 있다는 공통점이 있음
• 부분 배열 길이의 변화 여부에 차이점이 있음
  • 투 포인터 알고리즘 : 가변적인 부분 배열의 길이
  • 슬라이딩 윈도우 알고리즘 : 고정적인 부분 배열의 길이

---

투 포인터(Two Pointer)

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

다음과 같이 두 개의 유형이 존재

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

투 포인터의 변수

• 포인터 변수 이름 : Left, Right(Start, End)
• 목표로하는 값 변수 이름 : Target(일반적인 경우)
• 두 포인터의 의미가 중요함 [Left, Right) 를 의미함(배열 arr 의 부분배열은 arr[Left] 부터 arr[Right-1] 까지의 부분배열임)
  

두 포인터 변수의 이동 조건 (수행에서의 핵심 로직)

• 부분 배열의 합이 특정 값(Target) 을 이루는 부분 배열의 개수를 구하는 경우를 예시로함

1. 부분 배열의 합이 Target 값보다 크거가 같으면 Left 를 1 증가 (부분배열의 길이를 줄여 합을 빼줌)

   if (sum >= Target) Left++;

2. 부분 배열의 합이 Target 값보다 작으면 Right 를 1 증가 (부분 배열의 길이를 늘려 합을 더함)

   if (sum < Target) Right++;

3. 부분 배열의 합이 Target과 같다면 결과 값(count) 를 1 증가

   if (sum == Target) count++;

※ 1 에서 부분 배열의 합이 Target 과 같은 경우에도 Left 를 증가시키는 이유

• 다음 배열을 탐색해야 하기 때문
• 아래 그림과 같이 동작하게됨
  

• 중간 생략

투 포인터 대표 문제

2003번: 수들의 합 2

3273번: 두 수의 합

---

슬라이딩 윈도우

투 포인터와 유사하나, 크기가 고정적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘

미닫이 창문을 왼쪽에서 오른쪽으로 밀면서 창문 안의 존재하는 것들을 처리한다고 생각하면 됨

크기가 고정적이기 때문에 포인터 변수를 2개를 둘 필요가 없음

즉, 고정적인 부분 배열의 크기를 나타내는 변수가 있으면 포인터 하나로도 시작과 끝을 알 수 있음

구현 방법

주어진 문제가 부분 배열의 합을 구하는 문제일 경우

오른쪽으로 한칸 옮기더라도, 옮기기전 부분 배열과 옮기고 난 후의 부분 배열에는 겹치는 부분이 존재함

즉, 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값을 삭제하고 새 구간에 포함되는 값을 추가해주면됨

슬라이딩 윈도우 대표문제

10025번: 게으른 백곰

2075번: N번째 큰 수