윈도우 슬라이딩
윈도우 슬라이딩 혹은 슬라이딩 윈도우 알고리즘이라 불리는 전략입니다.
탐색 알고리즘으로 배열이나 리스트의 일정 범위에 대한 탐색을 할 때, 사용하는 알고리즘입니다.
사용 방법
1.
슬라이딩 윈도우를 실행할 배열을 탐색 배열로 설정합니다.
2.
탐색 배열에서 윈도우의 크기 즉 탐색할 영역의 크기를 설정합니다.(아래의 슬라이딩 윈도우의 탐색 크기는 5입니다.)
3.
끝 점과, 시작 점을 한 칸씩, 옮기면서 계산합니다.
예를 들어, 위의 그림에서 연속된 5칸의 합들 중 가장 큰 값을 찾는 문제가 나왔다면, 해당 문제는 윈도우 슬라이딩을 통해 풀어보실 수 있습니다.
첫 번째로 검색된 합의 값은 1+3+2+6-1 = 11입니다.
두 번째로 검색된 합의 값은 위의 합에서 가장 첫 번째 값을 빼고 마지막 값을 더합니다!
두 번째 값은 11 - 1 + 4 = 14 입니다.
이렇게 첫 번째 값과 마지막 값에 해당하는 값들로 이전 값을 통해 도출하는 방법이 바로 슬라이딩 윈도우의 핵심입니다.
세 번재 값도 마찬가지로 14 - 3 + 1 = 12 입니다.
이런식으로 가장 큰 값을 찾기 위해 마지막 -1,4,1,8,2 까지 계산하면 정답을 찾을 수 있습니다.
코드
윈도우 슬라이딩의 코드입니다.
void WinDowSliding(int[] SearchArray, int Size)
{
var maxSum = 0; // 가장 큰 값 (정답 을 저장합니다.)
var windowSum = 0; // 현재 윈도우 슬라이딩의 값입니다.
var windowStart = 0; // 윈도우 슬라이딩의 시작 Index입니다.
for (int windowEnd = 0; windowEnd < SearchArray.Length; windowEnd++)
{
windowSum += SearchArray[windowEnd];
if (windowEnd >= Size - 1)
{
maxSum = Math.Max(maxSum, windowSum);
windowSum -= SearchArray[windowStart];
windowStart++;
}
}
}
C#
복사
