[Algorithm] 16. Sliding Window

슬라이딩 윈도우 알고리즘

• 누적합은 전체의 합계를 구한 다음에 원하는 구역의 데이터의 합계를 계산하는 방식으로 구했다. 그와 비슷하면서 다른 용도로 쓰이는 알고리즘 중의 하나가 슬라이딩 윈도우(Sliding Window)다.
• 슬라이딩 윈도우란 특정 구역의 합계나 평균을 구하는데 유용하다.
• 예를 들어 1년의 기온을 확인하는데 3일간의 평균 기온이 가장 높은 구간은 어디인지 확인할 때, 주식에서 5일간의 평균 거래량을 확인할 때, 회사에서 물건의 판매량이 가장 높은 월이 언제인지 확인할 때 등등 구간을 정해두고 그 구간들 중 최대값을 구할 때 사용한다.

슬라이딩 윈도우 동작 과정

• 아래와 같이 일일 판매량을 기록한 배열이 있다고 했을 때, 5일동안 가장 많이 팔린 구간은 몇개를 팔았는지 확인해보자.

  

• 이런 문제에서 생각할 수 있는 방법은 반복문을 두 번 사용하여 구하는 방법이다.

• 먼저 첫 번째 날짜부터 5번째 날짜까지의 합계를 구한다. 다음으로 두 번째 날짜부터 6번째 날짜까지의 합계를 구한다. 이와 같은 방식으로 모든 날짜에 대해 5일치의 합계를 구하면 쉽게 최대값을 구할 수 있다.

  

• 그러나 배열의 길이가 100만이 넘고, 구해야 할 구간이 10만개가 넘으면 연산을 하는데 시간이 너무 오래 걸리게 된다. 이런 경우 슬라이딩 윈도우가 유용하게 사용될 수 있다.

• 먼저 첫번째 5일치는 정상적으로 계산하여 5 + 3 + 2 + 5 + 7 로 22가 된다. 다음 과정에서 슬라이딩 윈도우 개념이 사용된다.

  

• 앞에서 구한 5개의 합에서 윈도우를 벗어나는 5(첫번째 값)는 빼주고, 새로 윈도우에 들어오는 1은 더해준다. 따라서 22 - 5 + 1로 18이 된다.

  

• 다음 계산 역시 앞에서 구한 18에서 3을 빼주고, 4를 더해준다. 그러면 18 - 3 + 4 로 19가 된다. 이런 방식으로 전체를 계산하면 특정 부분에 대한 최대값을 쉽게 계산할 수 있다.
• 만약 배열의 개수가 100만개이고, 구간이 10만개가 되어도 첫 번째 10만개만 구한다면 그 이후는 더하기 하나, 빼기 하나로 다음 구간을 구할 수 있기 때문에 연산량이 많이 줄게 된다.

슬라이딩 윈도우 구현

'''
- 슬라이딩 윈도우 알고리즘은 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.
    -  배열이나 리스트와 같은 자료구조에서 연속된 부분의 합이나 평균, 최대/최소값 등을 구할 때 유용하다.
- 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법이다.
- 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용하다.
- 투 포인터(two poitners) 알고리즘과 연동하여 많이 쓰인다.
    - 1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 원하는 값을 얻는 형태
- 투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하며, 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점이 있다.

- 동작과정
    1. 처음 k 개의 요소의 합을 계산하여 초기 윈도우의 합으로 설정한다.
    2. 배열을 순회하면서 윈도우를 오른쪽으로 한 칸씩 옮길 때마다 새로운 요소를 더하고 이전 요소를 빼서 새로운 윈도우의 합을 계산한다.
    3. 각 윈도우의 합을 결과 리스트에 추가한다.
'''

def sliding_window_sum(arr, k):
    """
    Args:
    - arr (list): 입력 배열
    - k (int): 윈도우 크기

    Returns:
    - list: 윈도우 크기 k의 부분 배열의 합 리스트
    """
    n = len(arr)
    if n < k:
        return []

    window_sum = sum(arr[:k])
    result = [window_sum]

    for i in range(n - k):
        window_sum += arr[i + k] - arr[i]
        result.append(window_sum)

    return result

# 테스트
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
print(sliding_window_sum(arr, k))  # 출력: [6, 9, 12, 15, 18, 21, 24, 27]

맨 위로 이동 ↑