Sliding Window & Two Pointers

개인적으로 공부한 내용을 정리하였습니다. 틀린 부분은 피드백을 주시면 감사하겠습니다. - JAY -

두 알고리즘의 공통점과 차이점

먼저, 나는 두 알고리즘은 서로 굉장히 비슷한 알고리즘이라고 생각한다.
개인적으로는 Sliding Window가 Two Pointers와 아주 유사하다고 생각한다.
두 알고리즘은 길이가 N인 배열 속에서 순서대로 값들을 이용해서 목푯값을 찾아낸다.
그 과정에서 두 알고리즘은 두 개의 포인터를 사용한다.
하지만!!!
Sliding Window 는 항상 구간의 넓이가 고정되어있고,
Two pointers 는 구간의 넓이가 조건에 따라서 유동적으로 변한다.
그리고 두 알고리즘의 시간 복잡도는 O(N)이다

아직 시간복잡도에 대한 개념이 정확하지 않아서, 참고했던 블로그를 아래에 첨부한다.
https://blog.chulgil.me/algorithm/

개념 정리를 도와줄 예제

길이가 9인 정수 배열 속에서 정수들의 합이 5인 조합을 찾아보기로 하자.

arr[9] = {1, 2, 3, 4, 5, -4, 3 , 1 ,1}

Two Pointers 방법

전제조건

• 시작점과 끝점을 가리키는 두 개의 포인터 사용 -> st_ptr , end_ptr
• 맨 처음에는 둘 다 0을 가리킨다.
• st_ptr < 9 일 때까지 반복한다.
• 항상 end_ptr >= st_ptr 이여야 한다.
• 만약 구간의 합이 5 이상, 또는 end_ptr 가 배열의 끝에 도달했으면, st_ptr++
• 그렇지 않다면 end_ptr++
• 구간의 합이 5이면 count 개수를 하나 추가한다.
  
  원래 처음 시작은 두 포인터 모두 0을 가리키고 있는데, 그 부분은 생략됐다.
  Two pointers는 그림처럼 두 개의 포인터의 구간은 조건에 따라서 유동적으로 변한다.
  즉, 두 포인터는 조건에 맞춰서 배열의 처음부터 끝까지 증가하면서,
  특정 구간의 값들의 합이 5가 되는 경우를 세는 것이다.!!

Sliding window 방법

전제조건

• 시작점과 끝점을 가리키는 두 개의 포인터 사용 -> st_ptr , end_ptr
• st_ptr 과 end_ptr은 구간의 처음과 끝을 가리킨다.
• 구간은 정해진 크기만큼 배열의 끝에 도달할 때까지 한 칸씩 증가한다. (구간의 크기는 3이라고 가정한다.)
• 구간의 합이 5이면 count 개수를 하나 추가한다.
  
  원래 처음 시작은 두 포인터 모두 0을 가리키고 있는데, 그 부분은 생략됐다.
  구간의 크기는 고정된 상태로 배열의 끝까지 증가하면서 목푯값인 5를 찾으면 count 개수를 추가하였다.
  아래 그림을 보면 현재 구간의 합은 이전 구간의 합과 겹치는 부분이 있다는 규칙을 찾아낼 수 있다.
  이 규칙은 나중에 sliding window 알고리즘 문제를 풀 때 계산하는 식을 조금 더 간단하게 구현할 수 있을 것 같다.
  

최종 결론

두 알고리즘의 개념이 크게 어렵지 않아서 이해하는데 어려움은 없었다.
하지만, 많은 문제를 풀어보면서 내 것으로 만드는 노력은 당연히 필요할 것이다.