Sliding Window

Sliding Window(슬라이딩 윈도우)란 수행 과정에서 필요한 전체 메모리를 할당하는 것이 아닌 매 수행마다 필요한 부분만큼만을 저장하여 사용함으로 메모리를 절약, 공간 복잡도를 낮추는 기법이다. 즉, 수행한 이후에 사용하지 않게 되는 기록을 버림으로 매 순간 필요한 정보들만을 저장, 이용한다. 이러한 형태가 실제로 필요한 메모리 할당들을 지정된 크기의 창문에 할당한 이후, 그 메모리를 창문으로 밀어넣음으로서 매 순간에는 창문 크기 내의 정보만을 이용하는 것과 같아 Sliding Window라고 불린다.

창문                                    창문에 밀어넣을 배열        

창문과 배열에서 값의 이동

피보나치 함수를 예로 들어보자.

Fn+1 = Fn + Fn - 1 (n > 2) , F2 = 1, F1 = 1

DP를 이용하여 임의의 N에 대해 N번째 피보나치 값을 구할 경우, 전체 배열을 N개 선언함으로 계산할 수 있다.

이를 Sliding Window를 이용하여 계산할 경우, 매 순간마다 k, k-1 번째 항의 값만을 알고 있으면 k+1번째 항의 값을 구할 수 있음을 알 수 있다. 이를 통해 배열을 3개만을 할당함으로 N번째 값까지 구할 수 있다.

메모리를 접근하는 과정이 정적이지 않은 경우에는 Sliding Window를 사용할 수 없지만, 동적인 형태로 반복 수행가능한 경우 Sliding Window 기법을 통해 메모리를 효과적으로 절약할 수 있다.

문제

BOJ - 내려가기

POJ - Sliding Window