알고리즘, 문제 해결 패턴, Sliding Window

Sliding Window

Sliding Window는 프로그래밍에서 배열이나 문자열과 같은 연속된 데이터 구조 내에서 부분 집합의 합, 평균, 최대값 또는 최소값 등을 효율적으로 계산하기 위해 사용하는 알고리즘 기법입니다. 이 기법은 고정된 크기나 가변 크기의 윈도우를 사용하여 문제를 해결합니다.

기본 개념

Sliding Window의 기본 개념은 다음과 같습니다:

1. 윈도우 설정: 초기 윈도우 크기나 시작점을 설정합니다.
2. 윈도우 이동: 데이터를 한 번에 하나씩 이동하면서 윈도우 내 값을 갱신합니다.
3. 결과 갱신: 윈도우 내 값을 기준으로 필요한 결과를 갱신합니다.

예제

예제 1: 고정된 크기의 윈도우를 사용한 최대 합 찾기

다음은 고정된 크기의 윈도우를 사용하여 배열 내 연속된 요소들의 최대 합을 찾는 예제입니다.

function maxSubarraySum(arr, num) {
    if (arr.length < num) return null;

    let maxSum = 0;
    let tempSum = 0;

    for (let i = 0; i < num; i++) {
        maxSum += arr[i];
    }
    tempSum = maxSum;

    for (let i = num; i < arr.length; i++) {
        tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(maxSum, tempSum);
    }

    return maxSum;
}

console.log(maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2)); // 10

시간 복잡도

Sliding Window를 사용하는 알고리즘의 시간 복잡도는 일반적으로 O(n)입니다. 이는 데이터를 한 번만 순회하면서 문제를 해결하기 때문입니다.

활용 예시

Sliding Window 기법은 다음과 같은 다양한 문제에서 유용하게 사용됩니다:

• 고정된 크기의 윈도우 내 최대/최소 합 또는 평균 계산
• 가변 크기의 윈도우를 사용하여 특정 조건을 만족하는 최소/최대 길이 부분 배열 찾기
• 문자열 내 특정 패턴 찾기
• 배열 내 연속된 부분 배열의 합 또는 곱 계산

이 기법은 특히 배열이나 문자열과 같은 연속된 데이터 구조에서 효율적으로 부분 집합을 분석하고 처리하는 데 매우 유용합니다.