슬라이딩 윈도우 알고리즘

그림 한 장 Summary

슬라이딩 윈도우 알고리즘을 사용하는 경우

1차원 배열에서 부분적으로 특정 합이나 값을 구해야 하는 경우

왜 슬라이딩 윈도우 알고리즘을 사용하는가?

위 사용 예시에서 특정 K개의 합을 구하는데 O(N), 그것을 배열의 개수 N 개만큼 구해야 하므로 O(N)이 든다.

이 것을 동시에 시행하므로 O(N^2)이 걸린다.

하지만 배열이 200,000과 같이 큰 경우 일일이 계산해주면 시간 초과가 난다. (20만 * 20만 = 400억)

그래서 슬라이딩 윈도우를 통해 이 문제를 O(N)으로 해결할 수 있다.

백준 2559번 문제로 예를 들면,

psum 배열에 합계를 누적하여 저장하고

그 다음 두 번째 for문 안에서는 연속된 k일 간의 온도합이 가장 큰 값을 계속 갱신시킨다.

위와 같이 2~3번째의 합을 구할 때는 위에서 이미 연산된 값에다가 배열의 0번째 인덱스는 빼주고, 2번째 인덱스는 추가해주면 된다.

하나 더 예시를 들어보자.

위 백준 2559번 문제 경우에서 만약에 연속적인 3일간의 온도 합 중 가장 큰 온도의 값을 구해야 한다고 가정 했을 때,

위 그림처럼 일일이 3 + (-2) + (-4) 계산하고 최댓값 최신화하고,

(-2) + (-4) + (-9) 계산하고 최댓값 최신화하고, (-4) + (-9) + (0) 계산하고 최댓값 최신화하고 .....

이렇게 하면 중복 연산이 발생하여 비효율적이다.

연속적인 3일간의 온도 합이 아니라 10000일간의 온도 합이면 10000번을 더하는 연산을 또 N 번 해주어야 하기 때문이다.

이 과정을 효율적으로 바꾸기 위해 3 + (-2) + (-4) 를 계산한 것을 psum 이라는 변수에 넣어두고, 그 다음부터는 앞에 있는 것은 빼주고 뒤에 있는 것은 더해주면 된다.

처음에는 3+(-2)+(-4) 연산 결과인 -3을 psum에 저장해두고,

그 다음은 psum에 저장된 값에서 배열의 0인덱스 값은 빼주고, 배열의 3인덱스 값은 더해주면 된다.

그 다음은 psum에 저장된 값에서 배열의 1인덱스 값은 빼주고, 배열의 4인덱스 값은 더해주면 된다.

.... 이 것을 배열의 끝까지 해주면 된다.

그것을 구현한 것이 아래 코드와 같다.

		int max = Integer.MIN_VALUE;// 온도의 합이 최대가 되는 값
		// 0 번째 인덱스부터 K 번째 인덱스까지의 합 
		int curSum = 0;
		for(int i=0; i<K; i++) {
			curSum += temperature[i];
		}
		
		max = max > curSum ? max : curSum;
		
		// 슬라이딩 윈도우 알고리즘
		for(int i=0; i<N-K; i++) {
			curSum -= temperature[i];
			curSum += temperature[i+K];
			
			max = max > curSum ? max : curSum;
		}

카랑현석

슬라이딩 윈도우 알고리즘

그림 한 장 Summary