[D-27] 자료구조 - 투 포인터 & 슬라이딩 윈도우

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

2개의 포인터를 가진 알고리즘 풀이 방식으로,
슬라이딩 윈도우의 경우 범위를 유지한 채 이동하는 알고리즘을 말한다.

 

투 포인터와 슬라이딩 윈도우의 차이

---

📍 투 포인터

2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
알고리즘이 매우 간단하다.
시작 인덱스, 종료 인덱스를 투 포인터로 지정한 후 문제에 접근한다.

 

✅ 투 포인터 이동 원칙

A[i] + A[j] > K: j--;  // 번호의 합이 K보다 크므로 큰 번호 index를 내린다.
A[i] + A[j] < K: j++;  // 번호의 합이 K보다 작으므로 작은 번호 index를 올린다.

A[i] + A[j] == K: i++; j--; count++;  // 양쪽 포인터를 모두 이동시키고 count를 증가시킨다.

투 포인터 알고리즘

---

📍 슬라이딩 윈도우

2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 알고리즘이다.
투 포인터 알고리즘과 매우 비슷하고 원리도 간단하다.

 

슬라이딩 윈도우 알고리즘

 

✅ 슬라이딩 윈도우와 덱(deque)

정렬 알고리즘을 사용하지 않고도
슬라이딩 윈도우와 덱을 이용해 정렬 효과를 볼 수 있다.

 

✅ 덱(deque)

양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조를 말한다.
왼쪽에서는 addFirst(), removeFirst() 함수가 삽입, 삭제 역할을 하고,
오른쪽에서는 addLast(), removeLast()함수가 삽입, 삭제 역할을 한다.

 

덱(deque) - 삽입

덱(deque) - 삭제