슬라이딩 윈도우 메소드

3.1 슬라이딩 윈도우 메소드 정의

슬라이딩 윈도우 (Sliding Window) 메소드는 배열이나 문자열 문제를 해결할 때 사용되는 기술로, 고정된 부분 배열(또는 부분 문자열)을 데이터를 통해 이동시키면서 최적의 해결책을 찾는 기술이야. 이 방법을 통해 고정 크기의 윈도우 내에서 요소를 처리하고, 문제 조건에 따라 윈도우를 동적으로 변경할 수 있어.

이 기술은 특히 배열이나 문자열과 같은 데이터 시퀀스와 관련된 문제에서 유용하며, 보다 단순한 접근 방식에 비해 시간 복잡성을 줄이는 데 도움이 돼.

기본 원칙

• 윈도우 초기화: 윈도우의 시작과 끝 위치를 초기 위치로 설정해.
• 윈도우 이동: 한쪽 끝으로 요소를 추가하고 다른 쪽 끝으로 요소를 제거하면서 윈도우 경계를 순차적으로 이동해.
• 윈도우 처리: 각 단계에서 현재 윈도우에 대한 필요한 계산을 수행해.

슬라이딩 윈도우 메소드의 시간 및 공간 복잡성

시간 복잡성:

• O(n) — 대다수의 경우, 포인터나 윈도우가 배열을 선형적으로 이동하며 윈도우의 가능한 모든 위치를 검사하기 때문이야.

공간 복잡성:

• O(1) — 현재 값들을 저장하기 위해 고정된 양의 추가 메모리를 사용하는 경우야.
• O(k) — 크기 k의 현재 윈도우 내의 요소를 저장해야 하는 경우야.

3.2 최대 합 부분 배열 찾기

고정 크기의 부분 배열에서 최대 합 찾기

문제:

최대 합을 갖는 고정 크기 k의 부분 배열을 찾아.

해결책:

슬라이딩 윈도우 메소드를 사용하여 현재 부분 배열의 합계를 유지하고 윈도우를 이동하며 최대 합계를 갱신해.

시간 복잡성: O(n).

Python 코드 예제:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 문자열 내 모든 아나그램 찾기

문제:

주어진 부분 문자열 p의 모든 아나그램을 문자열 s에서 찾아.

해결책:

슬라이딩 윈도우 메소드를 사용하여 현재 윈도우의 문자 빈도 사전을 유지하고 이를 부분 문자열의 빈도 사전과 비교해.

시간 복잡성: O(n).

Python 코드 예제:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 최소 부분 배열 찾기

주어진 값을 초과하는 합계를 가진 최소 부분 배열 찾기

문제:

요소의 합이 주어진 값 S를 초과하는 최소 부분 배열을 찾아.

해결책:

슬라이딩 윈도우 메소드를 사용하여 오른쪽 경계를 확장하여 합계가 S를 초과할 때까지 계속하고, 부분 배열의 길이를 최소화하기 위해 왼쪽 경계를 이동해.

시간 복잡성: O(n).

Python 코드 예제:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len