슬라이딩 윈도: 움직이는 연속 구간의 상태를 재사용하기
슬라이딩 윈도는 배열이나 문자열의 연속 구간을 유지하며 양끝을 이동하는 기법이다. 이전 구간과 다음 구간이 많은 원소를 공유한다는 점을 이용해 필요한 정보를 증분 갱신한다. 고정 길이 윈도와 조건에 따라 길이가 달라지는 윈도는 논리가 다르다.
새 구간 전체를 다시 합산하는 대신 나가는 값과 들어오는 값을 반영한다.
고정 길이 합은 들어오고 나가는 값만 바뀐다
[2,1,5,3,4]에서 길이 3 첫 구간 합은 8이다. 한 칸 옮기면 2를 빼고 3을 더해 9, 다시 1을 빼고 4를 더해 12가 된다. 매번 세 값을 모두 더하지 않고 상태를 유지한다.
def maximum_window_sum(values, window_size):
if not 1 <= window_size <= len(values):
raise ValueError("Invalid window size")
current_sum = sum(values[:window_size])
best_sum = current_sum
for right in range(window_size, len(values)):
outgoing = values[right - window_size]
incoming = values[right]
current_sum += incoming - outgoing
best_sum = max(best_sum, current_sum)
return best_sum
초기 합 O(k), 이후 각 이동 O(1)이므로 총 O(n), 추가 상태는 O(1)이다. 최대값 초기화를 0으로 해서는 모든 합이 음수일 때 틀릴 수 있다. 첫 유효 구간의 합으로 시작하면 그 문제를 피한다.
가변 길이에는 단조 조건이 필요하다
양수 배열에서 합이 목표 이상인 가장 짧은 구간을 찾을 때는 오른쪽을 늘려 합을 키우고, 조건을 만족하면 왼쪽을 줄이면서 더 짧은 답을 시험할 수 있다. 원소가 양수이므로 왼쪽을 제거하면 합이 줄어드는 방향이 예측 가능하다.
음수가 있으면 이 단조성이 깨진다. [1,-1,5], 목표 5에서 전체가 조건을 만족해 왼쪽 1을 제거하면 합이 4가 된다. 여기서 줄이기를 멈추면 -1도 제거하여 [5]를 얻는 더 짧은 해를 놓친다. 같은 코드가 임의 정수에도 맞는 것은 아니다.
두 포인터가 각각 오른쪽으로만 n번 이동하면 중첩 반복문이 있어도 전체 O(n)일 수 있다. 한 단계에서 많이 줄어드는 비용을 전체 이동 횟수로 합산해야 한다. 매 단계에 포인터를 되돌리면 이 보장은 사라진다.
합은 나가는 값을 뺄 수 있지만 최댓값은 간단히 뺄 수 없다. 현재 최댓값이 윈도 밖으로 나가면 다음 후보가 필요해 단조 덱 같은 보조 구조를 사용한다. 상태마다 가능한 추가·제거 연산이 다르다.
윈도는 반드시 연속 구간이라는 조건을 유지한다. 임의 부분집합을 고르는 문제와 혼동해서는 안 된다. 문제의 조건이 이동 방향과 맞는지, 상태를 올바르게 제거할 수 있는지 확인할 때 이 기법이 효율적인 알고리즘이 된다.
문자열에서는 문자별 빈도를 상태로 유지할 수 있다. 윈도에서 마지막 한 글자가 나가면 종류 수를 줄이는 조건까지 정확히 갱신해야 한다.