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

[ 1 ] 기본내용

슬라이딩 윈도우는 이전에 포스팅한 투 포인터(Two Pointers) 알고리즘과 원리가 유사한 알고리즘이다. 

투 포인터 알고리즘은 2개의 포인터를 활용하여 부분 배열의 길이를 유동적으로 활용하거나 2개의 특정 원소 값에만 접근하는 반면, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 특징이 있다.

 

"한 정수 배열에서 길이가 3인 부분 배열 중 합이 가장 큰 부분 배열은 무엇인가?"라는 문제가 있다고 가정하자.

 

- arr = [3, 5, 2, 1, 7, 4, 10, 6, 8, 9]

위 배열이 주어졌을 때 가장 큰 부분 배열의 합을 구하기 위해서 중첩 반복문을 활용할 수 있을 것이다. 하지만, 중첩 반복문을 활용할 경우 시간 복잡도가 O(N^2)이기 때문에 효율적이지 않다. 이때 슬라이딩 윈도우 알고리즘을 활용한다면 시간 복잡도를 O(N)으로 줄일 수 있다.

 

슬라이딩 윈도우 알고리즘의 핵심은 "중복된 데이터를 다시 계산하지 않고 재사용하는 것"이다.

위 배열의 첫 번째 부분 배열인 arr[0] + arr[1] + arr[2] 을 계산했다고 가정하자.

그 다음은 두 번째 부분 배열인 arr[1] + arr[2] + arr[3] 을 계산해야 할 것이다.

 

이때 주목해야 할 것은 첫 번째 부분 배열과 두 번째 부분 배열에서 arr[1] + arr[2] 가 중복된다는 것이다.

즉, 첫 번째 부분 배열 계산 이후 두 번째 부분 배열을 계산할 때 중복된 arr[1] + arr[2] 는 재사용하고, arr[0] 은 삭제, arr[3] 은 추가하는 작업만 해준다면 시간 복잡도를 줄일 수 있는 것이다.

 

마찬가지로 세 번째 부분 배열을 계산할 때에도 arr[2] + arr[3]은 재사용하고, arr[1] 은 삭제, arr[4]는 추가하는 작업만 하면 된다.

이 모습이 창틀에 크기가 3인 창문을 놓고 이동하는 모양과 같아서 "슬라이딩 윈도우"라는 이름이 지어지게 되었다.

 

다음은 모든 부분 배열의 합을 슬라이딩 윈도우를 활용하여 출력하는 소스코드이다.

 

public class SlidingWindow {

	public static void main(String[] args) {
		
		int[] arr = {3, 5, 2, 1, 7, 4, 10, 6, 8, 9};
		int M = 3;
		
		int sum = 0;
		int cnt = 0;
		
		for(int i = 0; i < arr.length; i++)
		{
			sum = sum + arr[i];
			cnt++;
			
			if(cnt >= M)
			{
				System.out.println(sum);
				sum = sum - arr[i-M+1];
			}
		}
        //10 8 10 12 21 20 24 23 이 출력된다.
	}

}

 

최대 부분 배열의 합을 구하는 소스코드는 다음과 같다.

 

public class SlidingWindow {

	public static void main(String[] args) {
		
		int[] arr = {3, 5, 2, 1, 7, 4, 10, 6, 8, 9};
		int M = 3;
		
		int sum = 0;
		int cnt = 0;
		int max = 0;
		
		for(int i = 0; i < arr.length; i++)
		{
			sum = sum + arr[i];
			cnt++;
			
			if(cnt >= M)
			{
				if(max < sum)
				{
					max = sum;
				}
				sum = sum - arr[i-M+1];
			}
		}
		
		System.out.println(max);
		// 최대 부분 배열의 합인 24 출력
	}

}