슬라이딩 윈도우: 개념과 문제 해결

슬라이딩 윈도우(Sliding Window)는 연속된 구간의 값을 빠르게 계산할 때 사용하는 효율적인 기법입니다. 이 기법은 주어진 배열에서 연속된 부분 배열의 합, 최댓값 또는 최솟값을 구하는 문제를 해결할 때 자주 사용됩니다.

슬라이딩 윈도우 기법은 고정된 크기의 윈도우를 배열의 처음부터 끝까지 이동시키며, 각 구간의 값을 효율적으로 계산하는 방법입니다. 기존의 단순한 반복문으로 부분 배열을 구하면 불필요한 중복 연산이 발생할 수 있지만, 슬라이딩 윈도우는 이전 구간의 계산 결과를 재사용하여 더 빠르게 값을 계산합니다.

슬라이딩 윈도우의 주요 활용 예

• 최대 혹은 최소 부분 배열 합: 특정 크기의 연속된 부분 배열 중 최대 또는 최소 합을 구할 때 유용합니다.
• 고정된 크기의 평균 계산: 연속된 구간의 평균을 빠르게 계산합니다.
• 패턴 매칭: 특정 패턴과 일치하는 구간을 찾는 문제에서 효과적입니다.

시간 복잡도

슬라이딩 윈도우의 시간 복잡도는 일반적으로 $$O(N)$$입니다. 모든 구간을 독립적으로 계산하는 것이 아닌, 이전 구간의 결과를 재사용하므로 매우 효율적입니다.

다음 예제는 고정된 크기의 부분 배열 중에서 최대 합을 찾는 문제를 해결합니다. 슬라이딩 윈도우 기법을 사용하면 이전 합을 재사용하여 최댓값을 빠르게 계산할 수 있습니다.

Python 코드 예제:
def max_subarray_sum(arr, k):
    # 초기 윈도우의 합을 계산합니다
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # 윈도우를 배열 끝까지 이동하며 최대 합을 찾습니다
    for i in range(len(arr) - k):
        # 윈도우에서 이전 요소는 빼고, 다음 요소를 더해 합을 업데이트합니다
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)  # 최댓값 갱신

    return max_sum

# 예제 사용
arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_subarray_sum(arr, k))  # 출력: 9 (부분 배열 [5, 1, 3]의 합)
                

설명: max_subarray_sum 함수는 크기 k인 부분 배열 중 최댓값을 찾습니다. 초기 윈도우의 합을 계산한 후, 윈도우를 오른쪽으로 한 칸씩 이동하면서 이전 요소는 빼고 다음 요소는 더하여 합을 업데이트합니다. 이를 통해 매번 새로운 합을 계산할 필요 없이 효율적으로 값을 구할 수 있습니다.

슬라이딩 윈도우는 최대 부분 배열 합 외에도 다양한 문제에 적용할 수 있습니다. 대표적인 예로는 특정 구간 내의 값들을 조건에 따라 처리하는 문제와 특정 패턴을 탐색하는 문제가 있습니다.

예제 1: 특정 구간의 평균 계산

고정된 크기의 연속된 구간의 평균을 구하는 문제에서 슬라이딩 윈도우를 사용해 효율적인 풀이가 가능합니다.

Python 코드 예제:
def sliding_window_average(arr, k):
    # 초기 윈도우의 합을 계산합니다
    window_sum = sum(arr[:k])
    averages = [window_sum / k]

    # 윈도우를 배열 끝까지 이동하면서 평균을 구합니다
    for i in range(len(arr) - k):
        # 윈도우의 다음 요소를 추가하고 이전 요소를 제거해 합을 업데이트합니다
        window_sum = window_sum - arr[i] + arr[i + k]
        averages.append(window_sum / k)  # 구간 평균을 리스트에 추가합니다

    return averages

# 예제 사용
arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]
k = 3
print(sliding_window_average(arr, k))  # 출력: [2.0, 3.67, 2.33, 3.0, 1.0, 4.33, 3.67]
                

설명: sliding_window_average 함수는 크기 k의 부분 배열 평균을 계산합니다. 첫 번째 윈도우의 합을 계산한 후, 이전 요소를 빼고 새로운 요소를 더하여 이동하면서 평균을 계산합니다. 이를 통해 반복적인 합산 작업을 최소화하고, 효율적인 평균 계산이 가능합니다.

예제 2: 패턴 매칭을 위한 슬라이딩 윈도우

슬라이딩 윈도우는 문자열 내에서 특정 패턴을 찾거나 패턴과 일치하는 구간을 탐색하는 문제에 매우 유용합니다.

Python 코드 예제:
def find_pattern(s, pattern):
    # 패턴의 길이를 가져옵니다
    k = len(pattern)
    pattern_count = {}
    window_count = {}

    # 패턴의 각 문자 빈도를 저장합니다
    for char in pattern:
        pattern_count[char] = pattern_count.get(char, 0) + 1

    # 초기 윈도우 설정
    for char in s[:k]:
        window_count[char] = window_count.get(char, 0) + 1

    # 패턴과 일치하는 윈도우 위치를 저장할 리스트
    result = []

    # 슬라이딩 윈도우를 사용해 패턴 매칭을 확인합니다
    for i in range(len(s) - k):
        if window_count == pattern_count:
            result.append(i)  # 현재 윈도우가 패턴과 일치하는 경우

        # 윈도우에서 왼쪽 문자 제거
        start_char = s[i]
        window_count[start_char] -= 1
        if window_count[start_char] == 0:
            del window_count[start_char]

        # 윈도우에 오른쪽 문자 추가
        end_char = s[i + k]
        window_count[end_char] = window_count.get(end_char, 0) + 1

    if window_count == pattern_count:
        result.append(len(s) - k)  # 마지막 윈도우 확인

    return result

# 예제 사용
s = "bacdgabcda"
pattern = "abcd"
print(find_pattern(s, pattern))  # 출력: [0, 5, 6]
                

설명: find_pattern 함수는 주어진 문자열 s에서 특정 패턴 pattern과 일치하는 구간을 찾습니다. 패턴의 각 문자 빈도를 저장하고, 슬라이딩 윈도우로 구간의 빈도를 패턴과 비교하여 일치 여부를 확인합니다.

슬라이딩 윈도우 기법은 부분 배열의 합, 평균 등을 효율적으로 구할 수 있으나, 윈도우 크기가 가변적이거나 복잡한 조건이 필요할 경우 적용이 어려울 수 있습니다.

장점

• 이전 계산 결과를 재사용하여 중복 계산을 줄이므로 $$O(N)$$의 시간 복잡도로 효율적입니다.
• 단일 반복 구조를 사용하여 코드가 간결하고 이해하기 쉽습니다.

한계

• 윈도우 크기가 가변적이거나 복잡한 조건이 추가되는 경우, 알고리즘 적용이 어려워질 수 있습니다.
• 특정 유형의 문제에서는 슬라이딩 윈도우의 장점을 살리기 어렵습니다.