슬라이딩 윈도우 기술

슬라이딩 윈도우 문제는 고정 또는 가변 크기 윈도우가 데이터 구조(일반적으로 배열 또는 문자열)를 통해 이동하여 요소의 연속적인 하위 집합을 기반으로 문제를 효율적으로 해결하는 문제입니다. 이 기술은 주어진 조건 세트에 따라 하위 배열이나 하위 문자열을 찾아야 할 때 사용됩니다.

슬라이딩 윈도우 기술

내용의 테이블

슬라이딩 윈도우 기술이란 무엇입니까?
슬라이딩 윈도우 기술을 사용하는 방법은 무엇입니까?
슬라이딩 윈도우 문제를 식별하는 방법
슬라이딩 윈도우 기술의 사용 사례
슬라이딩 윈도우 기법의 연습 문제

슬라이딩 윈도우 기술이란 무엇입니까?

슬라이딩 윈도우 기술 정의하는 문제를 효율적으로 해결하는 데 사용되는 방법입니다. 창문 또는 범위 입력 데이터(배열 또는 문자열)에 있는 데이터를 가로질러 해당 창을 이동하여 창 내에서 일부 작업을 수행합니다. 이 기술은 특정 합계가 있는 하위 배열 찾기, 고유한 문자가 있는 가장 긴 부분 문자열 찾기, 요소를 효율적으로 처리하기 위해 고정 크기 창이 필요한 문제 해결과 같은 알고리즘에 일반적으로 사용됩니다.

이것을 제대로 이해하기 위해 예를 들어 보겠습니다. 크기 배열이 있다고 가정해 보겠습니다. N 그리고 또한 정수 케이. 이제 정확히 크기를 갖는 하위 배열의 최대 합을 계산해야 합니다. 케이. 이제 이 문제에 어떻게 접근해야 할까요?

이를 수행하는 한 가지 방법은 배열에서 크기 K의 각 하위 배열을 가져와 이러한 하위 배열의 최대 합계를 찾는 것입니다. 이는 O(N)이 되는 중첩 루프를 사용하여 수행할 수 있습니다.²) 시간 복잡도.

하지만 이 접근 방식을 최적화할 수 있을까요?

대답은 '예'입니다. 케이 크기가 지정된 하위 배열을 사용하고 그 합계를 계산하면 0에서 K-1 인덱스까지 하나의 K 크기 하위 배열을 가져와 합계를 계산할 수 있습니다. 이제 반복과 함께 범위를 하나씩 이동하고 결과를 업데이트합니다. 다음 반복에서 왼쪽과 오른쪽 포인터를 클릭하고 아래 이미지에 표시된 대로 이전 합계를 업데이트합니다.

슬라이딩 윈도우 기술

이제 배열의 끝에 도달할 때까지 각 반복마다 다음 방법을 따르십시오.

슬라이딩 윈도우 기술

소수 자바

따라서 K 크기의 각 하위 배열의 합을 다시 계산하는 대신 K 크기의 이전 창을 사용하고 그 결과를 사용하여 합계를 업데이트하고 왼쪽 및 오른쪽 포인터를 이동하여 창을 오른쪽으로 이동한다는 것을 알 수 있습니다. 이 작업은 다음과 같이 최적입니다. 다시 계산하는 대신 범위를 이동하는 데 O(1) 시간이 걸립니다.

포인터를 이동하고 그에 따라 결과를 계산하는 이러한 접근 방식은 다음과 같이 알려져 있습니다. 슬라이딩 윈도우 기술 .

슬라이딩 윈도우 기술을 사용하는 방법은 무엇입니까?

기본적으로 슬라이딩 윈도우에는 두 가지 유형이 있습니다.

1. 고정 크기 슬라이딩 윈도우:

아래 단계에 따라 이러한 질문을 해결하는 일반적인 단계는 다음과 같습니다.

필요한 창 크기(예: K)를 찾으세요.
첫 번째 창에 대한 결과를 계산합니다. 즉, 데이터 구조의 첫 번째 K 요소를 포함합니다.
그런 다음 루프를 사용하여 창을 1씩 슬라이드하고 창별로 결과 창을 계속 계산합니다.

2. 가변 크기 슬라이딩 윈도우:

아래 단계에 따라 이러한 질문을 해결하는 일반적인 단계는 다음과 같습니다.

이러한 유형의 슬라이딩 윈도우 문제에서는 조건이 참이 될 때까지 오른쪽 포인터를 하나씩 증가시킵니다.
어떤 단계에서든 조건이 일치하지 않으면 왼쪽 포인터를 늘려 창 크기를 줄입니다.
이번에도 조건이 만족되면 오른쪽 포인터를 늘리기 시작하고 1단계를 따릅니다.
배열의 끝에 도달할 때까지 다음 단계를 따릅니다.

슬라이딩 윈도우 문제를 식별하는 방법:

이러한 문제는 일반적으로 최대값/최소값 찾기가 필요합니다. 하위 배열 , 하위 문자열 특정 조건을 만족하는 것입니다.
하위 배열 또는 하위 문자열 '의 크기 케이' 일부 문제에 출제됩니다.
이러한 문제는 O(N)으로 쉽게 풀 수 있습니다.²) 중첩 루프를 사용한 시간 복잡도, 슬라이딩 윈도우를 사용하여 이를 해결할 수 있습니다. 에) 시간 복잡도.
필요한 시간 복잡도: O(N) 또는 O(Nlog(N))
제약: N <= 10⁶, N이 배열/문자열의 크기인 경우.

슬라이딩 윈도우 기술의 사용 사례:

1. 크기가 K인 모든 하위 배열의 최대 합계를 찾으려면 다음을 수행하세요.

크기의 정수 배열이 주어지면 'N', 우리의 목표는 다음의 최대 합계를 계산하는 것입니다. '케이' 배열의 연속 요소.

입력 : arr[] = {100, 200, 300, 400}, k = 2
출력 : 700

입력 : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
출력 : 39
크기 4의 하위 배열 {4, 2, 10, 23}을 추가하여 최대 합계를 얻습니다.

입력 : arr[] = {2, 3}, k = 3
출력 : 유효하지 않은
전체 배열의 크기가 2이므로 크기가 3인 하위 배열은 없습니다.

순진한 접근 방식: 그럼 문제를 분석해보자 무차별 접근 방식 . 첫 번째 인덱스부터 시작하여 다음 인덱스까지 합산합니다. k번째 요소. 가능한 모든 연속 블록이나 k 요소 그룹에 대해 이 작업을 수행합니다. 이 방법에는 중첩된 for 루프가 필요하며 외부 for 루프는 k 요소 블록의 시작 요소로 시작하고 내부 또는 중첩 루프는 k번째 요소까지 합산됩니다.

다음은 위의 접근 방식을 구현한 것입니다.

C++

 // O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

씨

 // O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>숫자2) ? 숫자1 : 숫자2; } // k 크기의 하위 배열에서 최대 합계를 반환합니다. int maxSum(int arr[], int n, int k) { // 결과 초기화 int max_sum = INT_MIN;  // i로 시작하는 모든 블록을 고려합니다.  for (int i = 0; i< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

자바

 // Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

파이썬3

 # code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

씨#

 // C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

자바스크립트

 function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

PHP

  // code ?>// k 크기의 하위 배열의 // 최대 합을 찾는 O(n*k) 솔루션 // k 크기의 하위 배열에서 최대 합을 반환합니다. function maxSum($arr, $n, $k) { // 결과 초기화 $max_sum = PHP_INT_MIN ; // i로 시작하는 // 모든 블록을 고려합니다. for ( $i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>

산출

24>

시간 복잡도: 두 개의 중첩 루프가 포함되어 있으므로 O(k*n)입니다.
보조 공간: 오(1)

슬라이딩 윈도우 기술 적용:

선형 루프를 사용하여 n항 중 처음 k개 요소의 합을 계산하고 그 합을 변수에 저장합니다. window_sum .
그런 다음 배열이 끝에 도달할 때까지 선형으로 탐색하고 동시에 최대 합계를 추적합니다.
k 요소 블록의 현재 합계를 얻으려면 이전 블록에서 첫 번째 요소를 빼고 현재 블록의 마지막 요소를 추가하면 됩니다.

아래 표현을 보면 창이 어레이 위에서 어떻게 미끄러지는지 명확하게 알 수 있습니다.

배열을 고려해보세요 도착[] = {5, 2, -1, 0, 3} 및 값 케이 = 3 및 N = 5
CTC 전체 형태

이는 인덱스 0부터 시작하여 초기 창 합계를 계산한 초기 단계입니다. 이 단계에서 창 합계는 6입니다. 이제 maximum_sum을 current_window, 즉 6으로 설정합니다.

이제 단위 인덱스만큼 창을 슬라이드합니다. 따라서 이제 창에서 5를 버리고 창에 0을 추가합니다. 따라서 5를 뺀 다음 0을 더하여 새 창 합계를 얻습니다. 따라서 이제 창 합계는 1이 됩니다. 이제 이 창 합계를 maximum_sum과 비교하겠습니다. 더 작으므로 maximum_sum을 변경하지 않습니다.

마찬가지로, 이제 다시 한 번 단위 인덱스만큼 창을 밀어 새 창 합계를 2로 얻습니다. 다시 이 현재 창 합계가 지금까지의 maximum_sum보다 큰지 확인합니다. 다시 한 번 더 작으므로 maximum_sum을 변경하지 않습니다.
따라서 위 배열의 경우 maximum_sum은 6입니다.

위의 접근 방식에 대한 코드는 다음과 같습니다.

C++

 // O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>

자바

 // Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>

파이썬3

 # O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>

씨#

 // C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

자바스크립트

PHP

  // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a  // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>

산출

24>

시간 복잡도: O(n), 여기서 N 입력 배열의 크기입니다. 도착[] .
보조 공간: 오(1)

2. 주어진 값보다 큰 합을 갖는 가장 작은 하위 배열:

배열이 주어지면 도착[] 정수와 숫자 엑스 , 작업은 주어진 값보다 큰 합을 가진 가장 작은 하위 배열을 찾는 것입니다.

접근하다:

우리는 슬라이딩 윈도우 기술을 사용하고 윈도우의 시작과 끝을 표시하기 위해 시작과 끝이라는 두 개의 포인터를 유지함으로써 이 문제를 해결할 수 있습니다. 창의 합이 X보다 작거나 같을 때까지 끝 포인터를 계속 증가시킬 수 있습니다. 창의 합이 X보다 커지면 창의 길이를 기록하고 시작 포인터를 창의 합까지 이동하기 시작합니다. X보다 작거나 같아집니다. 이제 합계가 X보다 작거나 같게 되면 끝 포인터를 다시 증가시키기 시작합니다. 배열의 끝에 도달할 때까지 시작 및 끝 포인터를 계속 이동합니다.

3. 음수가 아닌 정수 배열에서 주어진 합계를 가진 하위 배열을 찾습니다.

배열이 주어지면 도착[] 음수가 아닌 정수와 정수 합집합 , 주어진 항목에 추가되는 하위 배열을 찾습니다. 합집합 .

접근하다:

하위 배열의 모든 요소가 양수이므로 하위 배열의 합이 다음보다 크다면 아이디어는 간단합니다. 주어진 금액 그러면 현재 하위 배열에 요소를 추가하는 것이 주어진 합계와 같을 가능성이 없습니다. 따라서 아이디어는 유사한 접근 방식을 사용하는 것입니다. 슬라이딩 윈도우 .

빈 하위 배열로 시작합니다.
합계가 다음보다 작아질 때까지 하위 배열에 요소를 추가합니다. 엑스 ( 주어진 합계 ) .
합계가 다음보다 큰 경우 엑스 ,에서 요소를 제거합니다. 시작 현재 하위 배열의

4. 문자열 자체의 모든 문자를 포함하는 가장 작은 창:

접근하다:

기본적으로 문자 창은 두 개의 포인터를 사용하여 유지됩니다. 시작 그리고 끝 . 이것들 시작 그리고 끝 포인터를 사용하여 창 크기를 각각 축소하거나 늘릴 수 있습니다. 창에 주어진 문자열의 모든 문자가 포함될 때마다 창은 왼쪽에서 축소되어 추가 문자를 제거한 다음 길이가 지금까지 발견된 가장 작은 창과 비교됩니다.
현재 창에서 더 이상 문자를 삭제할 수 없으면 다음을 사용하여 창 크기를 늘리기 시작합니다. 끝 문자열에 있는 모든 고유 문자가 창에도 있을 때까지. 마지막으로 각 창의 최소 크기를 찾습니다.

슬라이딩 윈도우 기법의 연습 문제:

문제	문제 링크
주어진 합계로 하위 배열 찾기	해결하다
슬라이딩 윈도우 최대값(K 크기의 모든 하위 배열의 최대값)	해결하다
합이 K인 가장 긴 하위 배열	해결하다
크기가 k인 하위 배열의 최대(또는 최소) 합계 찾기	해결하다
다른 문자열의 모든 문자를 포함하는 문자열의 가장 작은 창	해결하다 언제나 모키토
반복되는 문자가 없는 가장 긴 부분 문자열의 길이	해결하다
크기가 k인 모든 창의 첫 번째 음의 정수	해결하다
크기가 k인 모든 창에서 고유 요소 수 계산	해결하다
문자열 자체의 모든 문자를 포함하는 가장 작은 창	해결하다
최소 k개 숫자를 포함하는 가장 큰 합계 하위 배열	해결하다

TechCodeview

슬라이딩 윈도우 기술이란 무엇입니까?

슬라이딩 윈도우 기술을 사용하는 방법은 무엇입니까?

1. 고정 크기 슬라이딩 윈도우:

2. 가변 크기 슬라이딩 윈도우:

슬라이딩 윈도우 문제를 식별하는 방법:

슬라이딩 윈도우 기술의 사용 사례:

1. 크기가 K인 모든 하위 배열의 최대 합계를 찾으려면 다음을 수행하세요.

2. 주어진 값보다 큰 합을 갖는 가장 작은 하위 배열:

3. 음수가 아닌 정수 배열에서 주어진 합계를 가진 하위 배열을 찾습니다.

4. 문자열 자체의 모든 문자를 포함하는 가장 작은 창:

슬라이딩 윈도우 기법의 연습 문제:

관련 기사: