슬라이딩 윈도우 기법이란? - 5525 IOIOI 파이썬

슬라이딩 윈도우(Sliding Window) 기법이란?

1. 개념

슬라이딩 윈도우(Sliding Window) 기법은 배열이나 문자열 같은 연속된 데이터를 일정한 범위(윈도우)로 탐색할 때, 불필요한 중복 연산을 줄이는 알고리즘 기법입니다.

2. 핵심 원리

• 윈도우 크기를 일정하게 유지하면서 한 칸씩 이동하며 값을 업데이트합니다.
• 새롭게 추가되는 값만 반영하고, 필요 없는 이전 값은 제거하여 중복 계산을 최소화합니다.
• 보통 O(N)에 처리 가능하므로 브루트포스(완전 탐색) O(N^2)보다 훨씬 빠름.

---

🔹 슬라이딩 윈도우의 동작 방식

예를 들어, 길이가 N인 배열에서 크기 k의 윈도우를 사용하여 연속된 부분 합을 구하는 문제를 생각해보겠습니다.

🔸 브루트포스(완전 탐색) 방식 (O(N*k))

모든 부분 배열을 하나씩 탐색하여 합을 구하면 O(N*k)의 시간 복잡도를 가집니다.

arr = [1, 2, 3, 4, 5, 6]
k = 3  # 윈도우 크기
n = len(arr)

max_sum = 0
for i in range(n - k + 1):
    window_sum = sum(arr[i:i+k])  # 매번 부분 배열의 합을 새로 계산 (비효율적)
    max_sum = max(max_sum, window_sum)

print(max_sum)  # 출력: 15

• sum(arr[i:i+k])이 매번 O(k) 연산이 필요하여 전체 O(N*k)

---

🔸 슬라이딩 윈도우 방식 (O(N))

한 번 계산한 window_sum을 이전 값만 제거하고 새로운 값만 추가하여 효율적으로 구할 수 있습니다.

arr = [1, 2, 3, 4, 5, 6]
k = 3  # 윈도우 크기
n = len(arr)

window_sum = sum(arr[:k])  # 첫 번째 윈도우의 합
max_sum = window_sum

for i in range(n - k):
    window_sum += arr[i + k] - arr[i]  # 이전 값 제거하고, 새로운 값 추가
    max_sum = max(max_sum, window_sum)

print(max_sum)  # 출력: 15

• 매번 O(k) 연산을 하지 않고 O(1) 연산만 수행
• 결과적으로 전체 시간 복잡도는 O(N)

---

🔹 슬라이딩 윈도우를 활용한 문자열 탐색 예제

백준 실버1 - 5525번: IOIOI

문자열 "IOI" 패턴을 찾는 문제에서, 슬라이싱 대신 인덱스를 활용하면 O(M × N) → O(M)으로 최적화 가능!

N = int(input())
M = int(input())
S = input()

ans, i, cnt = 0, 0, 0

while i < (M - 1):
    if S[i:i+3] == "IOI":
        i += 2  # "IOI"를 찾았으면 i를 2칸 이동 (중복 검사 방지)
        cnt += 1
        if cnt == N:
            ans += 1
            cnt -= 1  # 중복된 "IOI" 체크를 위해 감소
    else:
        i += 1
        cnt = 0  # 패턴이 끊기면 다시 시작

print(ans)

• 윈도우를 유지하며 한 칸씩 이동하면서 중복된 계산을 방지 (O(M))
• cnt -= 1을 활용하여 연속적인 "IOI" 패턴을 효율적으로 체크

---

🔹 슬라이딩 윈도우가 유용한 경우

1. 고정된 크기의 연속된 구간을 다룰 때 (예: K개의 연속된 숫자의 합)
2. 연속된 패턴을 찾을 때 (예: "IOI" 패턴 탐색)
3. 중복 계산을 줄이고 싶을 때 (예: 최댓값, 최솟값 갱신)
4. 투 포인터와 함께 사용하면 효율적인 문제 해결 가능 (예: 부분 배열의 합이 특정 값이 되는 경우)

---

🔹 요약

방식	시간 복잡도	특징
완전 탐색(브루트포스)	O(N*k)	모든 경우를 다 확인 (비효율적)
슬라이딩 윈도우	O(N)	불필요한 연산 없이 한 칸씩 이동하며 갱신 (효율적)

---

📌 팁

1. 슬라이싱(S[i:i+k])은 사용하지 말고, 직접 인덱싱(S[i])을 활용하자.
2. 윈도우 크기가 k인 경우, 새롭게 추가되는 값과 제거되는 값만 다루면 O(1) 연산이 가능.
3. 투 포인터(Two Pointer) 기법과 결합하면 더 강력한 문제 해결이 가능.