[알고리즘] 슬라이딩 윈도우(Sliding Window)

 

슬라이딩 윈도우(Sliding Window)

---

• 고정된 사이즈의 윈도우(창)이 배열 안을 이동하면서 윈도우 내에 담은 데이터를 이용해 문제를 푸는 알고리즘.
• 차이가 나는 양쪽 끝 원소를 갱신한다.
• 슬라이딩 윈도우는 항상 구간의 너비가 고정되어 주어진다.

 
 

---

 
 

만약, 윈도우의 크기가 3일 경우
 
sw[0] = arr[0] + arr[1] + arr[2]
.
.
.
sw[n] = sw[n-1] - arr[n-1] + arr[n-1+(윈도우크기)]
 

---

 

예제

 
 
Q.  연속된 index n개의 합의 최소를 구하시오. 그리고 합이 최소일 때의 인덱스(a,b)를 구하시오.
(a<=b);
 
 
 
 
1. sw배열에 모두 담고 최소값 구하는 방식

import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		
		int arr[] = {3,15,12,16,4,2,1,13,12};
		
		int sw[]=new int[arr.length];
		
		int n = sc.nextInt();
		
		
		for(int i=0;i<n;i++) {
			sw[0] += arr[i];
		}
		
		int swIdx =1;
		int minn = sw[0];
		int minIdx =0;
		
		while(swIdx<=arr.length-n) {
			
			sw[swIdx]=sw[swIdx-1]-arr[swIdx-1]+arr[swIdx-1+n];
			
			
			if(sw[swIdx]<minn) {
				minn =sw[swIdx];
				minIdx = swIdx;
				
			}
			
			swIdx++;
		}
		
			
		System.out.println("최소: " + minn + " (" + minIdx + " , "+ (minIdx+n-1) + ")");
	
		return;
	}
	

}

 
 
 
 
 
2. sw을 굳이 배열로 만들지 않고 풀이하는 방식

import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		
		int arr[] = {3,15,12,16,4,2,1,13,12};
		int sw=0;
		int n = sc.nextInt();
		
		for(int i=0;i<n;i++) {
			sw += arr[i];
		}
		
		int startIdx =0;
		int endIdx = n;
		
		int minn = sw;
		int minStartIdx =0;
		int minEndIdx =n-1;
		
		while(endIdx<arr.length) {
			
			sw=sw-arr[startIdx]+arr[endIdx];
			
			if(sw<minn) {
				minn =sw;
				minStartIdx = startIdx+1;
				minEndIdx = endIdx;
			}
			
			startIdx++;
			endIdx++;
		}
		
		System.out.println("최소: " + minn + " (" + minStartIdx + " , "+ (minEndIdx) + ")");
	
		return;
	}
	
}