algorithm
슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘 기본 정보

슬라이딩 윈도우 알고리즘은 주어진 대형 버퍼 또는 어레이의 특정 창 크기에 대해 필요한 작업을 수행하는 데 사용됩니다. 창은 첫 번째 요소에서 시작하여 한 요소 씩 바로 이동합니다. 목적은 각 창에있는 최소 k 개의 숫자를 찾는 것입니다. 이것은 일반적으로 슬라이딩 윈도우 문제 또는 알고리즘으로 알려져 있습니다.

예를 들어 주어진 배열의 모든 n 요소에서 최대 또는 최소 요소를 찾으려면 슬라이딩 윈도우 알고리즘이 사용됩니다.

예:

입력 배열 : [1 3 -1 -3 5 3 6 7]

창 크기 : 3

입력 배열의 3 요소마다 최대 요소 :

+---------------------------------+---------+
|      Windows Position           |   Max   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |    3    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |    3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |    5    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |    5    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    6    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    7    |
+---+---+----+----+---+-----------+---------+

입력 배열의 3 요소마다 최소 요소 :

+---------------------------------+---------+
|      Windows Position           |   Min   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |   -1    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |   -3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |   -3    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |   -3    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    3    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    3    |
+---+---+----+----+---+-----------+---------+

3 요소의 합계를 찾는 방법 :

방법 1 :

첫 번째 방법은 빠른 정렬을 사용하는 것입니다. 피벗이 K 번째 위치에 있으면 오른쪽에있는 모든 요소가 피벗보다 크기 때문에 왼쪽에있는 모든 요소가 자동으로 지정된 배열의 K 개의 가장 작은 요소가됩니다.

방법 2 :

K 요소의 배열 유지, 주어진 입력 배열의 첫 번째 K 요소로 채 웁니다. 이제 K + 1 요소에서 현재 요소가 보조 배열의 최대 요소보다 작은 지 확인하십시오. 그렇다면이 요소를 배열에 추가하십시오. 위의 솔루션의 문제는 최대 요소를 추적해야한다는 것입니다. 아직도 실행할 수 있습니다. 정수 집합에서 최대 원소를 어떻게 추적 할 수 있습니까? 생각 해봐. 최대 힙을 생각하십시오.

방법 3 :

큰! O (1)에서 우리는 가장 작은 K 요소로 이미 선택된 K 요소 중에서 최대 요소를 얻습니다. 현재 설정된 최대 값이 새로 고려 된 요소보다 큰 경우, max를 제거하고 K 가장 작은 요소의 집합에서 새로운 요소를 도입해야합니다. 힙 속성을 유지하려면 다시 Heapify하십시오. 이제 N의 배열에 K 개의 최소 요소를 쉽게 얻을 수 있습니다.

우주 보조 장치 : O(n)

시간 복잡성 : O(n)

C #에서 슬라이딩 윈도우 알고리즘 구현

public class SlidingWindow
{
    public static int[] MaxSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var max = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] > max) max = input[i + j];
            }
            result[i] = max;
        }
        return result;
    }

    public static int[] MinSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var min = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] < min) min = input[i + j];
            }
            result[i] = min;
        }
        return result;
    }

    public static int[] MainMax(int[] input, int n)
    {
        return MaxSlidingWindow(input, n);
    }

    public static int[] MainMin(int[] input, int n)
    {
        return MinSlidingWindow(input, n);
    }
}