슬라이딩 윈도우 패턴

당면한 문제에 따라 알고리즘 문제를 해결하는 데 도움이 되는 패턴이 있습니다. 슬라이딩 창 패턴은 한 위치에서 다른 위치로 배열 또는 숫자가 될 수 있는 창을 만듭니다. 슬라이딩 윈도우 패턴은 데이터가 어떤 식으로든 연속적일 때 배열, 문자열 등의 데이터 하위 집합을 추적하는 데 매우 유용합니다. 특정 조건에 따라 창이 커지거나 닫힙니다.

슬라이딩 윈도우 패턴 인식

역시 슬라이딩 윈도우 패턴은 데이터의 하위 집합을 추적하는 데 매우 유용합니다. 이것은 종종 배열에 있고 데이터는 연속적입니다. 다음은 슬라이딩 윈도우 패턴을 사용하여 해결할 수 있는 예제 문제입니다.

정수 배열과 n이라는 숫자를 받아들이는 maxSubarraySum이라는 함수를 작성하십시오. 이 함수는 배열에 있는 n개의 연속 요소의 최대 합계를 계산해야 합니다.

일부 예제 입력은 다음과 같습니다.maxSubarraySum([1,2,5,2,8,1,5], 2) => 10
maxSubarraySum([1,2,5,2,8,1,5], 4) => 17
maxSubarraySum([4,2,1,6], 1) => 6


maxSubarraySum 문제 해결

다음 솔루션은 시간 복잡도 O(N)입니다. 많은 사람들이 순진하거나 "쉬운"솔루션을 가르치는 것으로 시작할 수 있습니다. 대신 슬라이딩 윈도우 패턴을 사용하는 이 솔루션을 살펴보겠습니다. 이제 이 패턴이 어떻게 작동하는지 이해할 수 있다면 다른 유사한 문제를 인식하기 시작할 것이고 이러한 문제에도 슬라이딩 윈도우 패턴을 적용할 수 있을 것입니다. 또한 이 솔루션에 따라 훨씬 더 나은 시간 복잡도를 얻을 수 있습니다.

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if(arr.length < num) return null;
  for(let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i-num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

그렇다면 이 솔루션은 무엇을 하는 것일까요?
먼저 maxSum과 tempSum이라는 두 변수를 선언합니다. 이들은 코드에서 조금 더 아래에서 사용됩니다. 배열이 유효하지 않은 경우를 확인하는 if 문이 있습니다. Num은 배열에서 합계를 찾는 데 필요한 숫자입니다. 숫자가 배열의 길이보다 크면 유효한 합계를 얻을 수 없으므로 null을 반환합니다.

그런 다음 첫 번째 합계를 만듭니다.
이 예를 들어 3을 전달해 보겠습니다.maxSubarraySum([2,6,9,2,1,8,5,6,3], 3)배열의 시작 부분으로 이동하여 처음 3개의 숫자(2, 6 및 9)를 합산합니다. 이 숫자의 합을 maxSum이라는 변수에 저장합니다. 그런 다음 tempSum을 maxSum과 동일하게 설정합니다(함수 끝에서 maxSum을 반환함). 이제 또 다른 루프를 시작합니다. 시작 부분 또는 인덱스 0에서 시작하는 대신 이미 합산한 처음 3개의 숫자 다음에 루프를 시작합니다. 이 경우 인덱스 3(2)에서 시작합니다.

tempSum은 현재 값 17(2+6+9)을 저장하고 있으며 인덱스 4에서 2를 더하고 인덱스 0에서 2를 뺍니다. 합계를 다시 확인하면 여전히 값이 17입니다. 루프를 다시 반복할 때 tempSum(17)에 1(인덱스 5)을 더하고 6(인덱스 1)을 뺍니다. 새로운 tempSum은 (9+2+1)입니다. for 루프의 마지막 줄은 maxSum과 tempSum 사이의 최대값을 사용합니다. tempSum이 maxSum 값보다 크면 maxSum 값을 덮어씁니다. 그렇지 않으면 계속 반복합니다.

이 솔루션이 O(N) 시간 복잡도에서 작동하는 이유는 무엇입니까?

우리는 백만 자릿수 또는 수백만 자릿수를 가질 수 있습니다. 슬라이딩 윈도우 패턴의 장점은 배열을 한 번만 반복하면 된다는 것입니다.

이 질문과 해결책을 연습하십시오. 그런 다음 더 많은 슬라이딩 윈도우 패턴 문제를 찾기 시작합니다. 한 번 시도해 보세요.

양의 정수 배열과 양의 정수라는 두 개의 매개변수를 받는 minSubArrayLen이라는 함수를 작성하세요. 이 함수는 합계가 함수에 전달된 정수보다 크거나 같은 연속 하위 배열의 최소 길이를 반환해야 합니다. 하나도 없으면 대신 0을 반환합니다.

예:minSubArrayLen([2,3,1,2,4,3], 7) => 2 ([4,3] is the smallest subarray)
minSubArrayLen([4,3,3,8,1,2,3], 11) => 2