슬라이딩 윈도우 기법

난이도 쉽게
자주 묻는 질문 아마존 광신자
배열 슬라이딩 윈도우 기술 스크립터 이론조회수 38

시작하기 전에 슬라이딩 윈도우 기술은 무엇입니까? 그것이하는 일과 그것이하는 일이이 개념의 요령을 작은 문제로 이해하게 해준다.

주어진 정렬 정수의 경우, 크기 k의 모든 부분 배열에서 최소 합계를 찾는 작업이 있습니다.

입력 : {1,4,0,3,5,2,6,1}

k = 4

출력 : 크기 4의 최소 합계 하위 배열은 (0,3)입니다.

접근 방식 -1

브 루트 포스

인덱스 0에서 n-k + 1까지 k 요소의 합을 고려하여 모든 하위 배열에서 최소 합을 찾아 보겠습니다.

가능한 모든 연속 하위 배열을 얻은 다음 모두에서 최소 합계를 찾으십시오.

코드 조각으로 이해해 보겠습니다.

슬라이딩 윈도우 기법을위한 자바 코드

import java.util.*;
public class brute
{
  public static int maxk(int nums[],int k)
  {
    int min=Integer.MAX_VALUE;
    for(int i=0;i<nums.length-k+1;i++)
    {
      int sum=0;
      for(int j=i;j<i+k;j++)
      {
        sum=sum+nums[j];
      }
      min=Math.min(min,sum);
    }
    return min;
  }
  public static void main(String args[])
  {
    int a[]={1,4,0,3,5,2,6,1};
    int k=4;
    int ans=maxk(a,k);
    System.out.println(ans);
  }
}

슬라이딩 윈도우 기법을위한 C ++ 코드

#include<iostream>
using namespace std;
int mins(int a,int b)
{
  if(a>b)
    return b;
  else
    return a;
}
int maxk(int nums[],int k,int l)
{
  int min=9999;
  for(int i=0;i<l-k+1;i++)
  {
    int sum=0;
    for(int j=i;j<i+k;j++)
    {
      sum=sum+nums[j];
    }
    min=mins(min,sum);
  }
  return min;
}
int main()
{
  int a[]={1,4,0,3,5,2,6,1};
  int k=4;
  int l=sizeof(a)/sizeof(a[0]);
  int ans=maxk(a,k,l);
  cout<<ans;
}
{1,4,0,3,5,2,6,1}
4

(0,3)

슬라이딩 윈도우 기법에 대한 복잡성 분석

위의 접근 방식에 대한 시간 복잡성 = O (n ^ 2)

그러나이 시대에 O (n ^ 2) 솔루션을 원하는 사람은 빠르고 격렬합니다.

우리는 그것을 최적화해야합니다. 우리는 무엇을해야 하는가?

새로운 기술을 추천합니다.

슬라이딩 윈도우는 무엇입니까?

이 개념은 나무를 기어 오르려는 애벌레와 같은 느낌 / 같습니다.

창문은 무엇입니까?

창은 그것을 통해 이동하는 배열의 시퀀스 부분입니다.

충분히 명확하지 않습니까?

다음은이를 명확히하는 그림입니다.

슬라이딩 윈도우 기법
크기 2 배열에 대한 크기 6의 슬라이딩 윈도우

위 그림에서 크기 2의 빨간색 영역 (창)이 배열을 통해 미끄러집니다.

I을 시작으로, j를 창의 끝 인덱스로 취하면 배열을 통해 이동할 때 둘 다 2 씩 증가하여 크기 XNUMX의 슬라이딩 윈도우를 제공합니다.

이제 우리가 가지고있는 새로운 개념으로“슬라이딩 윈도우 기법”같은 문제를

접근 방식 -2

슬라이딩 윈도우

  • 처음 k 개 숫자의 합을 계산하고 합산

타다! 첫 번째 윈도우의 합계가 완료되었습니다.

  • 각 창에서 합계를 구합니다.
    • 마지막 창, 즉 배열에서 오래된 데이터 제거 [current_start-1]
    • 새로운 데이터, 즉 배열 추가 [previous_end + 1]
    • 따라서 창을 슬라이딩
  • 모든 창에서 합계의 최소값을 찾습니다.

짜잔! 이제 O (n) 시간에 같은 문제를 해결할 수 있습니다.

슬라이딩 윈도우 기법을위한 자바 코드

import java.util.*;
public class brute
{
  public static int maxk(int nums[],int k,int n)
  {
    //If the array does not contain k elements it is not eligible
    if(n<k)
      return -1;
    //Declaring the minimum
    int min=0;
    //Finding the sum of first k elements
    for(int i=0;i<k;i++)
      min=min+nums[i];
    int cur=min;
    //As the sliding window moves 
    //We move the start and end index by 1
    for(int i=k;i<n;i++)
    {
      //Thus we remove the initial index value
      cur=cur-nums[i-k]+nums[i];
      //And add the current index value
      min=Math.min(cur,min);
    }
    return min;
  }
  public static void main(String args[])
  {
    int a[]={1,1,0,3,2,2,6,1};
    int k=5;
    int n=a.length;
    int ans=maxk(a,k,n);
    System.out.println(ans);
  }
}

슬라이딩 윈도우 기법을위한 C ++ 코드

#include<iostream>
using namespace std;
    int mins(int a,int b)
    {
    	if(a>b)
    		return b;
    	else
    		return a;
    }
    int maxk(int nums[],int k,int n)
  {
    //If the array does not contain k elements it is not eligible
    if(n<k)
      return -1;
    //Declaring the minimum
    int min=0;
    int i=0;
    //Finding the sum of first k elements
    for(i=0;i<k;i++)
      min=min+nums[i];
    int cur=min;
    //As the sliding window moves 
    //We move the start and end index by 1
    for(i=k;i<n;i++)
    {
      //Thus we remove the initial index value
      cur=cur-nums[i-k]+nums[i];
      //And add the current index value
      min=mins(cur,min);
    }
    return min;
  }
  int main()
  {
    int a[]={1,1,0,3,2,2,6,1};
    int k=5;
    int n=8;
    int ans=maxk(a,k,n);
    cout<<ans;
  }
{1,1,0,3,2,2,6,1}
5
(0,4)

복잡성 분석

시간 복잡도 = O (n)

여기에 있습니다. 고정 슬라이딩 윈도우 개념 설명!

새로 인수 한 사람과 함께 연습 해보는 건 어떨까요 문제에 대한 지식?

참조

Translate »