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

2024-10-29 11:32:31 | 조회수 103


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

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

1. 슬라이딩 윈도우의 개념과 활용

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

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

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

시간 복잡도

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

2. 슬라이딩 윈도우 예제: 최대 부분 배열 합

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

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

3. 슬라이딩 윈도우의 다양한 응용 사례

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

예제 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과 일치하는 구간을 찾습니다. 패턴의 각 문자 빈도를 저장하고, 슬라이딩 윈도우로 구간의 빈도를 패턴과 비교하여 일치 여부를 확인합니다.

4. 슬라이딩 윈도우의 장점과 한계

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

장점

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

한계

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

이번 글에서는 슬라이딩 윈도우 기법을 통해 배열 내 특정 구간에서 효율적으로 값을 계산하는 방법을 배웠습니다. 슬라이딩 윈도우를 활용하여 시간 복잡도를 개선하고, 다양한 문제 해결 능력을 향상시켜 보세요.


슬라이딩 윈도우: 개념과 문제 해결 - 알고리즘닷컴 19 개의 글