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

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

슬라이딩 윈도우 기법은 배열이나 문자열과 같은 선형 데이터 구조에서 특정 범위의 요소들을 효율적으로 처리하기 위한 알고리즘 패러다임.
이 기법은 “창문(window)“처럼 움직이는 부분 배열을 이용하여 시간 복잡도를 획기적으로 개선할 수 있는 강력한 문제 해결 방법이다.

슬라이딩 윈도우 기법은 선형 데이터 구조에서 연속된 요소들을 효율적으로 처리하기 위한 강력한 알고리즘 패러다임으로 이 기법을 이해하고 적용하면 중첩 반복문을 사용하는 시간 복잡도를 O(n²)에서 O(n)으로 줄일 수 있어, 성능 개선에 크게 기여할 수 있다.

슬라이딩 윈도우 기법은 문자열 처리, 배열 연산, 데이터 스트림 처리 등 다양한 분야에서 활용된다.
특히 고정 크기 윈도우와 가변 크기 윈도우 두 가지 유형을 이해하고 상황에 맞게 적용하면, 복잡한 문제도 효율적으로 해결할 수 있다.

이 기법을 마스터하기 위해서는 다양한 문제를 해결하며 경험을 쌓고, 윈도우 상태 관리와 효율적인 업데이트 방법에 대한 이해를 깊게 하는 것이 중요하다.

슬라이딩 윈도우의 기본 개념

슬라이딩 윈도우 기법은 배열이나 문자열의 연속적인 부분집합(부분 배열 또는 부분 문자열)을 고정 크기 또는 가변 크기의 윈도우로 표현하고, 이 윈도우를 왼쪽에서 오른쪽으로 “슬라이딩"하면서 문제를 해결한다. 이 과정에서 중요한 점은 윈도우가 이동할 때마다 모든 요소를 다시 계산하지 않고, 새로 추가되는 요소와 제거되는 요소만 고려하여 결과를 업데이트한다는 것이다.

슬라이딩 윈도우 기법을 사용하면 중첩된 반복문을 사용하는 대신 단일 반복문으로 문제를 해결할 수 있어, O(n²)의 시간 복잡도를 O(n)으로 줄일 수 있다.

슬라이딩 윈도우의 유형

슬라이딩 윈도우 기법은 크게 두 가지 유형으로 나눌 수 있다:

고정 크기 윈도우 (Fixed Size Window)

윈도우의 크기가 처음부터 끝까지 일정하게 유지된다.
예를 들어, “배열에서 연속된 k개 요소의 최대 합 찾기"와 같은 문제에 적용된다.

가변 크기 윈도우 (Variable Size Window)

윈도우의 크기가 문제의 조건에 따라 동적으로 변경된다.
예를 들어, “합이 S 이상이 되는 최소 길이의 연속 부분 배열 찾기"와 같은 문제에 적용된다.

슬라이딩 윈도우 알고리즘의 단계

일반적인 슬라이딩 윈도우 알고리즘은 다음과 같은 단계로 구성된다:

1. 윈도우 정의: 처리할 데이터의 범위를 나타내는 윈도우를 정의한다.
2. 윈도우 초기화: 윈도우의 첫 위치를 설정하고 초기 계산을 수행한다.
3. 윈도우 이동: 윈도우를 한 칸씩 이동하면서 다음을 반복한다:
   • 윈도우에서 빠져나가는 요소 처리 (왼쪽에서 제거)
   • 윈도우로 새로 들어오는 요소 처리 (오른쪽에 추가)
   • 현재 윈도우 상태에 따른 결과 업데이트
4. 최종 결과 반환: 모든 윈도우 위치를 확인한 후 최종 결과를 반환한다.

슬라이딩 윈도우 구현 예제

고정 크기 윈도우 예제: 최대 부분 배열 합

다음은 크기가 k인 연속 부분 배열의 최대 합을 찾는 예제:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def max_sum_subarray(arr, k):
    n = len(arr)
    
    # 입력 검증
    if n < k:
        return "배열 크기가 윈도우 크기보다 작습니다"
    
    # 첫 번째 윈도우의 합 계산
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # 윈도우 슬라이딩
    for i in range(k, n):
        # 새 요소 추가, 이전 요소 제거
        window_sum = window_sum + arr[i] - arr[i - k]
        # 최대값 업데이트
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# 예시
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 3
print(max_sum_subarray(arr, k))  # 출력: 24 (3, 1, 0, 20 중 최대 합은 20+3+1=24)

위 코드에서 시간 복잡도는 O(n).
첫 번째 윈도우의 합을 계산하는 데 O(k) 시간이 소요되고, 이후 각 윈도우의 합을 O(1) 시간에 계산한다.

가변 크기 윈도우 예제: 합이 S 이상인 최소 길이 부분 배열

다음은 합이 S 이상이 되는 최소 길이의 연속 부분 배열을 찾는 예제:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def min_length_subarray_with_sum(arr, S):
    n = len(arr)
    
    # 현재 윈도우의 합과 시작 인덱스
    current_sum = 0
    window_start = 0
    
    # 최소 길이 (초기값은 무한대)
    min_length = float('inf')
    
    for window_end in range(n):
        # 현재 요소를 윈도우에 추가
        current_sum += arr[window_end]
        
        # 현재 윈도우의 합이 S 이상이면, 윈도우 크기를 줄여봄
        while current_sum >= S and window_start <= window_end:
            # 현재 윈도우 길이 계산 및 최소 길이 업데이트
            window_length = window_end - window_start + 1
            min_length = min(min_length, window_length)
            
            # 왼쪽 요소 제거 및 시작 인덱스 이동
            current_sum -= arr[window_start]
            window_start += 1
    
    # 합이 S 이상인 부분 배열이 없는 경우
    if min_length == float('inf'):
        return 0
    
    return min_length

# 예시
arr = [2, 3, 1, 2, 4, 3]
S = 7
print(min_length_subarray_with_sum(arr, S))  # 출력: 2 (부분 배열 [4, 3]의 길이)

이 알고리즘의 시간 복잡도도 O(n).
각 요소는 최대 두 번씩만 처리된다 (한 번은 window_end로, 한 번은 window_start로).

슬라이딩 윈도우 기법의 응용 사례

슬라이딩 윈도우 기법은 다음과 같은 다양한 문제에 적용할 수 있다:

1. 문자열 처리 문제

   • 가장 긴 중복 없는 부분 문자열 찾기
   • 특정 문자들을 모두 포함하는 최소 윈도우 부분 문자열 찾기
   • 아나그램 패턴 찾기

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   def longest_substring_without_repeating_chars(s): char_set = set() # 현재 윈도우의 문자 집합 max_length = 0 window_start = 0 for window_end in range(len(s)): current_char = s[window_end] # 중복 문자가 발견되면 윈도우 시작점 이동 while current_char in char_set: char_set.remove(s[window_start]) window_start += 1 # 현재 문자를 집합에 추가 char_set.add(current_char) # 현재 윈도우 길이 계산 및 최대 길이 업데이트 window_length = window_end - window_start + 1 max_length = max(max_length, window_length) return max_length # 예시 s = "abcabcbb" print(longest_substring_without_repeating_chars(s)) # 출력: 3 ("abc")

2. 배열 처리 문제

   • K개 요소의 최대/최소 합
   • 합이 특정 값이 되는 부분 배열 찾기
   • 최대 평균 부분 배열 찾기

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   def find_max_average_subarray(arr, k): n = len(arr) # 첫 번째 윈도우의 합 계산 window_sum = sum(arr[:k]) max_sum = window_sum # 윈도우 슬라이딩 for i in range(k, n): window_sum = window_sum + arr[i] - arr[i - k] max_sum = max(max_sum, window_sum) # 평균 반환 return max_sum / k # 예시 arr = [1, 12, -5, -6, 50, 3] k = 4 print(find_max_average_subarray(arr, k)) # 출력: 12.75

3. 데이터 스트림 처리

   • 이동 평균 (Moving Average) 계산
   • 실시간 데이터 분석 및 이상치 탐지
   • 네트워크 패킷 모니터링

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

   class MovingAverage: def __init__(self, size): self.size = size self.queue = [] self.window_sum = 0 def next(self, val): # 윈도우가 가득 찼으면 가장 오래된 요소 제거 if len(self.queue) == self.size: self.window_sum -= self.queue.pop(0) # 새 요소 추가 self.queue.append(val) self.window_sum += val # 현재 평균 반환 return self.window_sum / len(self.queue) # 예시 mavg = MovingAverage(3) print(mavg.next(1)) # 출력: 1.0 print(mavg.next(10)) # 출력: 5.5 print(mavg.next(3)) # 출력: 4.66… print(mavg.next(5)) # 출력: 6.0 (1이 제거되고 5가 추가됨)

슬라이딩 윈도우 기법의 장단점

장점

• 효율성: O(n²)의 시간 복잡도를 O(n)으로 줄일 수 있다.
• 메모리 효율성: 추가 메모리 사용이 최소화된다.
• 알고리즘 단순화: 복잡한 문제를 간단한 단계로 나눌 수 있다.
• 증분 계산: 이전 계산 결과를 재사용하여 효율성을 높인다.

단점

• 적용 제한: 모든 문제에 적용할 수 있는 것은 아니다. 주로 선형 데이터 구조와 관련된 문제에 적합하다.
• 구현 복잡성: 특히 가변 크기 윈도우는 구현이 복잡할 수 있다.
• 윈도우 경계 처리: 윈도우의 시작과 끝 부분 처리에 주의가 필요하다.

슬라이딩 윈도우 기법 활용을 위한 팁

1. 문제 유형 파악: 연속된 부분 집합이나 부분 배열을 다루는 문제인지 확인한다.
2. 고정/가변 윈도우 결정: 문제의 조건에 따라 적절한 윈도우 유형을 선택한다.
3. 윈도우 상태 추적: 윈도우의 현재 상태를 효율적으로 추적할 방법을 고민한다.
4. 증분 계산 최적화: 윈도우 이동 시 전체를 다시 계산하지 않고 증분만 계산한다.
5. 경계 조건 처리: 배열의 시작과 끝 부분, 그리고 윈도우 크기가 배열 크기보다 큰 경우 등의 경계 조건을 신중하게 처리한다.

복잡한 슬라이딩 윈도우 문제와 해법

최소 윈도우 부분 문자열 (Minimum Window Substring)

문제: 문자열 S와 문자열 T가 주어졌을 때, S에서 T의 모든 문자를 포함하는 최소 길이의 부분 문자열을 찾는다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

from collections import Counter

def min_window_substring(s, t):
    if not s or not t:
        return ""
    
    # t의 문자 빈도수 계산
    target_counter = Counter(t)
    required = len(target_counter)
    
    # 윈도우 변수 초기화
    window_start = 0
    formed = 0  # 만족된 고유 문자 수
    window_counts = {}  # 현재 윈도우의 문자 빈도수
    
    # 결과 변수 (윈도우 길이, 왼쪽 경계, 오른쪽 경계)
    result = float('inf'), 0, 0
    
    # 윈도우 확장
    for window_end in range(len(s)):
        # 현재 문자를 윈도우에 추가
        char = s[window_end]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # 현재 문자가 목표에 있고, 빈도수가 일치하면 형성된 문자 수 증가
        if char in target_counter and window_counts[char] == target_counter[char]:
            formed += 1
        
        # 모든 필요 문자가 포함되었으면 윈도우 축소 시도
        while window_start <= window_end and formed == required:
            char = s[window_start]
            
            # 현재 윈도우가 더 작으면 결과 업데이트
            if window_end - window_start + 1 < result[0]:
                result = (window_end - window_start + 1, window_start, window_end)
            
            # 왼쪽 문자 제거 및 윈도우 시작점 이동
            window_counts[char] -= 1
            if char in target_counter and window_counts[char] < target_counter[char]:
                formed -= 1
            
            window_start += 1
    
    # 결과 반환
    if result[0] == float('inf'):
        return ""
    return s[result[1]:result[2] + 1]

# 예시
s = "ADOBECODEBANC"
t = "ABC"
print(min_window_substring(s, t))  # 출력: "BANC"

최대 연속 1의 개수 III (Max Consecutive Ones III)

문제: 0과 1로 이루어진 배열이 주어지고, 최대 k개의 0을 1로 바꿀 수 있을 때, 연속된 1의 최대 개수를 찾는다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def longest_ones(nums, k):
    window_start = 0
    max_consecutive_ones = 0
    max_zeros_flipped = 0  # 현재 윈도우에서 1로 바꾼 0의 개수
    
    for window_end in range(len(nums)):
        # 현재 요소가 0이면 플립 카운트 증가
        if nums[window_end] == 0:
            max_zeros_flipped += 1
        
        # 허용된 플립 횟수를 초과하면 윈도우 축소
        while max_zeros_flipped > k:
            if nums[window_start] == 0:
                max_zeros_flipped -= 1
            window_start += 1
        
        # 현재 윈도우 길이 계산 및 최대값 업데이트
        max_consecutive_ones = max(max_consecutive_ones, window_end - window_start + 1)
    
    return max_consecutive_ones

# 예시
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
k = 2
print(longest_ones(nums, k))  # 출력: 6

실전 문제 해결 전략

슬라이딩 윈도우 기법을 효과적으로 활용하기 위한 문제 해결 전략:

1. 문제 분석: 문제가 연속된 요소의 부분집합을 처리하는가?
   • 연속된 k개 요소를 처리하는 경우 → 고정 크기 윈도우
   • 특정 조건을 만족하는 부분 배열을 찾는 경우 → 가변 크기 윈도우
2. 윈도우 상태 정의: 윈도우 내부 상태를 어떻게 표현할 것인가?
   • 합, 평균, 최대값, 최소값
   • 문자 빈도수, 고유 문자 수
   • 조건 충족 여부
3. 상태 업데이트 전략: 윈도우 이동 시 상태를 어떻게 효율적으로 업데이트할 것인가?
   • 이전 윈도우 → 현재 윈도우로 변경 시 O(1) 시간에 업데이트 방법 고민
   • 제거되는 요소와 추가되는 요소의 영향 계산
4. 결과 업데이트 조건: 어떤 조건에서 최종 결과를 업데이트할 것인가?
   • 최대값/최소값 업데이트 조건
   • 특정 조건 충족 시 결과 기록

참고 및 출처