슬라이딩 윈도우 기법

소개

슬라이딩 윈도우 기술은 프로그램 속도를 늦추는 일부 중복 계산을 줄이는 데 사용됩니다. 시간 복잡도를 O(n^2)에서 O(1) 공간 복잡도로 O(n)으로 줄일 수 있습니다.

왜 사용합니까?

우선 시간 복잡도와 O(1) 공간 복잡도를 줄입니다. 그래서 예를 들어 이해합시다 ..
따라서 우리는 배열에서 k개의 연속 정수의 최대 합을 찾고자 합니다.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> arr = {5,2,6,7,7,3,2,1,3,9};
    int final_max = 0;
    for(int i=0;i<arr.size()-5;i++){
        int temp_max = 0;
        for(int j=i;j<i+5;j++){
            temp_max += arr[j];
        }
        if(temp_max>final_max){
            final_max = temp_max;
        }
    }
    cout << final_max << endl;
    return 0;
}

하지만 위 프로그램의 시간복잡도는 O(nk)

무차별 접근


위의 이미지에서 볼 수 있듯이 무차별 접근 방식은 k 길이(여기서는 k=5)의 모든 패턴을 확인합니다. 위의 코드를 이 이미지와 비교하면 이해가 될 것입니다.

여기서 k=5이므로 O(n)과 O(nk)에서 큰 차이를 만들지는 않지만 k가 너무 크면 어떻게 됩니까? 그러면 프로그램의 실행 시간에 영향을 미치므로 지금 무엇을 해야 합니까? 위의 코드를 O(n)에 구현할 수 있습니까?

답은 YES입니다!! , 슬라이딩 윈도우를 사용하여 위 코드 O(n)의 시간 복잡도를 줄일 수 있습니다.

슬라이딩 윈도우는 어떻게 작동합니까?

이제 슬라이딩 윈도우가 어떻게 작동하는지 봅시다.
작은 배열로 간단한 시각적 정보를 제공하겠습니다.

{5,2,6,7,7,3,2,1,3,9}
for k=3 (because k=5 is too much to write)
{5,2,6} --> first 3 elements
{2,6,7} --> remove 5 and add 7 
{6,7,7} --> remove 2 and add 7
{7,7,3} --> remove 6 and add 3
{7,3,2} --> remove 7 and add 2
{3,2,1} --> remove 7 and add 1
{2,1,3} --> remove 3 and add 3
{1,3,9} --> remove 2 and add 9

두 번째 예를 들어 이해합시다.

 {5, 7, 1, 4, 3, 6, 2, 9, 2}
 k=5
 {5,7,1,4,3} --> first 5
 {7,1,4,3,6} --> remove 5 and add 6
 and so on.

위의 이미지에서 볼 수 있듯이 한 번에 한 단계씩 움직입니다. 이것이 실제로 작동하는 방식입니다.

코딩하자

슬라이딩 윈도우 기술을 사용하여 배열에서 k 연속 정수의 최대 합계에 대한 코드입니다.

#include<iostream>
#include<vector>
using namespace std;
int sum_of_k_ele(vector<int> arr,int k){
    int sum = 0;
    for(int i=0;i<k;i++){
        sum += arr[i];
    }
    return sum;
}
int main(){
    vector<int> arr = {5,2,6,7,7,3,2,1,3,9};
    int k=3;
    // below function will be used only once 
    // for finding sum of first k digits
    int final_sum = sum_of_k_ele(arr,k);

    int temp_sum = final_sum;
    for (int i=k;i<arr.size();i++){
        temp_sum = temp_sum - arr[i-k];
        temp_sum = temp_sum + arr[i];
        if(temp_sum>final_sum){
            final_sum = temp_sum;
        } 
    }
    cout << final_sum << endl;

    return 0;
}

언제 사용합니까?

지정된 문자열 또는 배열과 같은 최고값 또는 최소값이나 대상 값에서 하위 범위를 찾는 경우.

문자열이나 배열처럼 반복 가능한 데이터 구조를 포함합니다.

O(n^2) 또는 (2^n)을 사용하여 무차별 대입 솔루션이 있을 수 있는 경우

더 많은 예...

Find all anagrams in a string --> Solution

Permutation in string --> Solution

참고 : 위 질문의 솔루션은 일반 코드입니다.

## 참조

Stackoverflow

medium

감사합니다 😊😊