슬라이딩 윈도우, 왼쪽을 줄이는 타이밍이 전부다

부분 배열 문제를 보면 이중 for문부터 손이 간다. 모든 시작점에서 모든 끝점까지 돌리면 O(n²), 당연히 시간 초과. 그런데 "연속된 부분 배열"이라는 조건이 붙어 있다면, 오른쪽을 한 칸 늘렸을 때의 변화를 왼쪽을 줄여서 상쇄할 수 있는지가 핵심이다. 이게 슬라이딩 윈도우의 본질이고, 결국 왼쪽 포인터를 언제 움직이느냐에 모든 게 달려 있다.

#고정 크기는 쉽다

윈도우 크기가 K로 정해져 있으면 고민할 게 없다. 처음 K개 원소의 합을 구해놓고, 오른쪽을 한 칸 늘리면서 왼쪽을 한 칸 빼면 끝이다. "크기 K인 부분 배열의 최대 합"이 대표적.

def max_sum_fixed(arr, k):
    window = sum(arr[:k])
    best = window
    for r in range(k, len(arr)):
        window += arr[r] - arr[r - k]
        best = max(best, window)
    return best

패턴만 알면 거의 실수할 일이 없다. 문제는 다음이다.

#가변 크기 — 왼쪽을 줄이는 조건이 전부

윈도우 크기가 정해지지 않은 문제. "합이 S 이상인 가장 짧은 부분 배열", "서로 다른 문자가 K개 이하인 가장 긴 부분 문자열" 같은 유형에서 실력 차이가 확 벌어진다.

뼈대는 항상 이렇게 생겼다:

left = 0
for right in range(len(arr)):
    # 1. arr[right]를 윈도우에 추가
    # 2. 조건이 깨지면 left를 전진
    while 조건_위반(window):
        # arr[left]를 윈도우에서 제거
        left += 1
    # 3. 현재 윈도우로 정답 갱신

이 뼈대에서 진짜 어려운 건 2번이다. "조건이 깨졌다"를 어떻게 판단하느냐.

"합이 S 이상인 최소 길이" 문제를 보자. 오른쪽을 확장하면서 현재 합이 S 이상이 되면, 왼쪽을 줄여서 아직 S 이상인지 확인한다. 줄여도 되면 계속 줄이고, 안 되면 멈추고 다시 오른쪽을 확장한다.

def min_subarray_len(s, arr):
    left = 0
    total = 0
    result = float('inf')
    for right in range(len(arr)):
        total += arr[right]
        while total >= s:
            result = min(result, right - left + 1)
            total -= arr[left]
            left += 1
    return result if result != float('inf') else 0

여기서 핵심 인사이트 하나. while 안에서 정답을 갱신한다. "조건을 만족하는 동안" 윈도우를 줄이면서 최솟값을 계속 업데이트하는 거다. 반대로 "최대 길이"를 구하는 문제라면 while 바깥에서 갱신한다 — 조건을 만족하는 가장 큰 상태에서 기록해야 하니까. 이 차이를 놓치면 답이 엉뚱하게 나온다.

시간복잡도가 O(n²) 아니냐고 물어보는 사람이 꼭 있다. left가 매번 0부터 시작하는 게 아니라 절대 뒤로 안 돌아간다는 점이 핵심이다. right가 n번, left도 전체에서 최대 n번 이동하니까 총 O(2n) = O(n).

#자주 출제되는 변형 3가지

최대 K번 교체 허용 — 최대 길이 구하기. LeetCode 424번(Longest Repeating Character Replacement)이 대표. 윈도우 안에서 가장 많은 문자의 개수를 세고, 나머지 문자 수가 K를 초과하면 왼쪽을 줄인다. 사람들이 자주 빠지는 함정은 max_count를 매번 정확히 갱신하려는 것인데, 사실 max_count는 줄어들 필요가 없다. 윈도우가 유효하지 않으면 크기를 줄이되 max_count는 "역대 최댓값"으로 남겨둬도 정답에 영향을 주지 않는다. 처음엔 직관적이지 않지만 증명하면 맞다.

해시맵으로 빈도 관리. "서로 다른 문자 종류가 K개 이하인 가장 긴 부분 문자열" 같은 조건은 해시맵으로 각 문자의 빈도를 추적해야 한다. 오른쪽 문자를 넣고, 종류 수가 K를 초과하면 왼쪽 문자의 빈도를 줄인다. 빈도가 0이 되면 해시맵에서 삭제하고 종류 수를 차감한다. 프로그래머스의 "보석 쇼핑" 문제가 정확히 이 패턴이다. 전체 보석 종류를 먼저 세고, 윈도우 안에 모든 종류가 포함되는 최소 구간을 찾는다.

두 배열에 걸친 윈도우. 덜 알려져 있지만 간간이 나온다. 배열 두 개를 합쳐놓고 윈도우를 굴리거나, 원형 배열에서 처음과 끝이 이어진 경우 배열을 두 번 이어붙이고 윈도우 크기를 n 이하로 제한하는 트릭이 있다. 백준의 원형 수열 관련 문제들이 이 패턴을 쓴다.

#슬라이딩 윈도우처럼 생겼는데 아닌 것

"연속 부분 배열"이라는 단어만 보고 반사적으로 윈도우를 꺼내면 위험하다. 적용 가능 여부를 가르는 건 딱 하나 — 왼쪽 포인터를 전진시키는 것이 항상 윈도우의 "비용"을 줄이는 방향인가?

양수 배열의 합? 왼쪽을 빼면 합이 줄어드니까 OK. 문자 종류 수? 빈도가 0이 되면 종류가 줄어드니까 OK. 그런데 음수가 섞인 배열의 합은? 왼쪽 원소가 음수면 빼는 게 오히려 합을 늘린다. 단조성이 깨진다. "부분 배열의 최대 곱"도 마찬가지다 — 음수끼리 곱하면 양수가 되니까 왼쪽을 줄이는 게 개선인지 악화인지 알 수 없다.

이럴 땐 프리픽스 합에 자료구조를 얹거나(세그먼트 트리, 정렬된 셋), 아예 DP로 접근해야 한다. 카카오 2026 상반기 코테에서도 부분 배열 문제가 나왔는데 음수 조건이 숨어 있어서 윈도우로 풀다가 시간을 날린 후기가 꽤 보인다.

"오른쪽 확장 = 악화 방향, 왼쪽 축소 = 개선 방향"이라는 단조성이 성립하는지를 먼저 확인하자. 이 판별 한 번이면 10초 안에 윈도우 쓸지 말지 결정할 수 있다.