11. 투 포인터, 슬라이딩 윈도우 개념

1. 투 포인터 ✌️

1-1. 투포인터란?

• 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘
• 2 개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는다.
• 2 개의 포인터 중에서 start 포인터(왼쪽)는 어떤 조건일 때 증감시키고, end 포인터(오른쪽)는 어떤 조건일 때 증감시킬지 결정해야 한다!!

1-2. 투포인터 알고리즘 문제의 유형

1️⃣ 포인터 2개가 같은 방향으로 진행

• 참고 문제 : https://www.acmicpc.net/problem/2003

2️⃣ 포인터 2개가 양끝에서 시작하여 반대로 진행

• 참고 문제 [BOJ 2470번 두 용액]:
  https://velog.io/@da_na/05.-이진-탐색-문제-BOJ-2470번

3️⃣ 포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동

2. 슬라이딩 윈도우 🪟

2-1. 슬라이딩 윈도우란?

• 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만, 부분 배열의 길이가 고정적이다.
• 투 포인터와 달리 하나의 포인터를 사용해도 된다. 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝을 어딘지 알 수 있다. (시작점 : 1, 배열의 크기 : 3 -> 끝 점 : 1+3-1 = 3)
• 주어진 문제가 부분 배열의 합을 구하는 것이라 할 때, 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에는 겹치는 부분이 존재한다. 즉, 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가해주면 된다.

사진 출처 : https://velog.io/@codenmh0822/투-포인터-슬라이딩-윈도우-구간-합-알고리즘#슬라이딩-윈도우

2-2. 슬라이딩 윈도우의 문제 유형

1️⃣ 구간합

• 기존의 구간의 합이 S 이고 새로운 구간에선 빠지는 맨 앞 원소가 A 고 새로운 구간에 들어오게 된 원소를 B 라고 하면, 새로운 구간의 합은 S - A + B 가 된다.

2️⃣ Anagram 찾기

3. 참고 자료 📚

https://velog.io/@codenmh0822/투-포인터-슬라이딩-윈도우-구간-합-알고리즘#슬라이딩-윈도우
https://ansohxxn.github.io/algorithm/twopointer/