슬라이딩 윈도우 알고리즘(feat. 투 포인터) 문제 유형

😎 슬라이딩 윈도우 알고리즘

🎃 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘.

• 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용하다.
• 해당 윈도우에 포함된 데이터의 특정 속성(합, 최대값, 최소값 등) 빠르게 계산할 때 사용.
• 문제 풀이 시, 주로 사용되는 경우로는 배열과 그 부분 배열을 어떤 조건 하에서 계산하는 경우에 주로 사용한다. ex) 구간 합 구하기, 부분 문자열 구하기 등에 활용

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

이런 슬라이딩 윈도우와 함께 자주 언급되는 알고리즘으로 투 포인터 알고리즘이 있다.

• 투 포인터와 슬라이딩 윈도우 알고리즘은 선형 공간(1차원 배열(*리스트))을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있다.

• 두 알고리즘의 차이점은??

🏈 부분 배열 길이의 변화 여부

쉽게 말해서, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적이다.

😀 속성 계산 및 갱신

윈도우 내의 데이터에 대한 원하는 속성(합, 평균, 최대값)을 계산하고, 필요한 경우 이 정보를 갱신하면서 진행.

슬라이딩 윈도우 장점

효율성

각 이동 시마다 전체 윈도우를 다시 계산하는 대신, 윈도우에서 제거되는 요소와 추가되는 요소만을 고려하여 계산을 최적화 할 수 있다.

백준 DNA 비밀번호, 회전 초밥(2531) 문제 풀어보기