슬라이딩 윈도우 기법🔥

궁금한 여러분👋 안녕하세요! 문제를 해결할 뿐만 아니라 효율적으로 해결하는 알고리즘을 작성하고 기분이 좋아진 적이 있습니까? 이 블로그에서는 그런 느낌을 더 자주 받을 수 있도록 도와주는 알고리즘에 대해 알아봅니다! Sliding Window Technique(SWT) - O(N²)에서 O(N)까지 솔루션(일반적으로 배열과 같은 순차적이고 반복 가능한 데이터 구조를 다루는 문제)의 시간 복잡도를 개선하는 데 도움이 되는 알고리즘으로 이해합니다. 시간 복잡도를 이해하지 못하고 솔루션이 더 빠르게 실행되도록 개선하는 데 도움이 된다는 점만 알고 계십시오.

SWT는 무엇입니까?

대부분의 정의에 따르면 SWT는 무차별 대입(주로 O(N²))) 알고리즘을 선형(O(N)) 알고리즘으로 변환하는 방법입니다.

도움이 되나요?

인터뷰에서 알고리즘을 O(N²)에서 O(N)으로 개선하는 것은 대단한 일입니다(음...적어도 저에게는😅).

그것을하는 방법?

이를 수행하는 방법을 이해하기 위해 문제를 살펴보고 먼저 무차별 대입 솔루션에 대해 생각한 다음 SWT를 적용하여 개선합니다. 그 전에 SWT를 적용하는 방법에 대한 기본 아이디어를 제공하겠습니다(지금은 이치에 맞지 않을 수 있지만 문제를 해결하는 동안 확실히 됩니다!)
배열이 있고 배열에서 가장 큰 요소를 찾고 싶다고 가정해 봅시다. 해결책은 모든 요소를 ​​살펴보고 가장 큰 요소를 추적하는 것일 수 있습니다. SWT 방식으로 표현하면 다음과 같습니다.👇

이제 추측하셨을 것입니다. 창이 왼쪽에서 오른쪽으로 미끄러져(클릭하셨나요?💡), 우리가 본 것 중 가장 큰 요소인지 값을 확인하고 창이 배열의 끝에 도달할 때까지 계속됩니다. 창은 우리가 다루고 있는 문제에 따라 임의의 크기일 수 있습니다. 하나(또는 임의 개수의 요소) 요소 길이이거나 가변 크기일 수 있습니다. 창 크기는 고정되거나 동적일 수 있습니다.

문제

N 양의 정수 배열이 주어지면 3개의 연속 요소의 최대 합을 구합니다.

무차별 대입 방식

내 마음에 오는 첫 번째 솔루션은 3개의 연속 요소의 가능한 모든 하위 배열을 찾고 합계를 찾고 최대값을 추적하는 것입니다. 이를 위해 두 개의 중첩 루프가 필요합니다. 코드에서 이 알고리즘을 살펴보겠습니다.

let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0;  //to keep track of maximum sum.

for (let i = 0; i < arr.length - 3 + 1; i++){
  //Initializing sum
  let sum = 0;
  //Adding 3 elements starting from i
  for (let j = 0; j < 3; j++){
    sum = sum + arr[i + j];
  }
  //Storing the maximum sum
  maxSum = Math.max(sum,maxSum);
}

console.log(maxSum);

이 알고리즘의 시간 복잡도는 O(N*3)이며, 3이 아닌 더 큰 요소 집합인 경우 더 나쁠 수 있습니다.

SWT 접근법

이제 SWT 접근 방식이 어떻게 작동하는지 살펴보겠습니다.


이제 우리가 하고 싶은 것은 크기가 3인 창을 가지고 있고, 합계를 세고 오른쪽으로 미끄러질 때 최대 합계를 추적하는 것입니다. 이제 창에서 한 요소를 오른쪽으로 이동하면 어떻게 되는지 시각화해 보겠습니다. 우리가 실제로 하고 있는 것은 합계에 4번째 요소를 더하고 1번째 요소를 뺀 다음, 창이 배열의 끝에 도달할 때까지 동일한 작업을 반복하는 것입니다. 코드에서 어떻게 보이는지 봅시다.

let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0;  //to keep track of maximum sum.
let sumOfWindow = 0; //to keep track of sum of the window.
let windowSize = 0;

for (let i = 0; i < arr.length + 1; i++){
  if(windowSize == 3){
    console.log('current windows sum is');
    console.log(sumOfWindow);
    //storing the maximum sum
    maxSum = Math.max(maxSum, sumOfWindow);
    //deleting the end element of the window
    sumOfWindow = sumOfWindow - arr[i - 3];
    windowSize--;
  }

   //adding elements to the window.
  sumOfWindow = sumOfWindow + arr[i];
  windowSize++;

}

console.log("The maximum sum is: " + maxSum);

짜잔! 그것은 단일 루프에 있으며 O(N) 시간 복잡도를 의미합니다! 에헴.. To use fewer loops, use more brain 으아아아아 그리고 아마도 몇 줄의 코드가 더 있을 것입니다(항상 그런 것은 아님).
당신은 그것을 가지고 있습니다! Sliding Window Technique !

언제 사용합니까?

배열이나 문자열(예: max continuous subarray , longest non-repeating substrings )과 같은 반복 가능한 데이터 구조의 연속 요소와 관련이 있는 문제를 볼 때 일반적으로 사용하려고 합니다.

이제 SWT에 대해 알았으니 this problem in hackerrank? 문제를 해결해 보시겠습니까? 창의 크기는 동적일 수 있으며 항상 3과 같이 고정된 숫자일 필요는 없습니다.

이 블로그consider buying me a coffee😊 또는 support me in patreon이 마음에 드셨다면 .

이 시리즈의 다른 블로그를 확인하세요.👇