[바미] 슬라이딩 윈도우 기법

시작

안녕하세요. 지난번에 체스판 다시 칠하기문제를 풀면서 사용한 윈도우 슬라이딩 기법에 대해 자세히 알아보기 위해 포스팅을 해보려 합니다.

슬라이딩 윈도우 기법?

체스판 다시 칠하기 문제에서 설명했듯이 슬라이딩 윈도우 기법은 배열이나 리스트의 항목을 순차적으로 탐색할 때 사용하는 알고리즘 기법 중 하나입니다. 이 기법은 "창" 또는 "윈도우"라고 할 수 있는 고정된 크기의 부분 배열이나 서브 리스트를 이동시키면서 문제를 해결합니다. 이 윈도우는 데이터 구조를 통해 한 번에 한 항목씩 앞으로 이동하면서 연속적인 데이터의 범위를 처리합니다.

 

보통 슬라이딩 윈도우 기법은 아래와 같은 상황에서 사용하면 굉장히 유용합니다.

• 배열이나 리스트에서 고정된 크기의 윈도우를 슬라이드하면서, 각 윈도우에 대한 최대값 또는 최소값을 찾아야 할 때
  • 또는 주어진 배열에서 모든 k-크기 서브 배열의 최대 합을 찾아야 할 때
• 문자열 검색에서 패턴 매칭을 수행할 때
  • 슬라이딩 윈도우를 사용하여 주어진 패턴과 텍스트의 부분 문자열을 비교하는 형태로 사용합니다.
• 데이터 스트림이나 시계열 데이터에서 연속적인 데이터 포인트들의 평균, 중앙값, 또는 표준편차 등을 계산할 때

---

예제 코드

최대값을 구하는 예제

function maxSum(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    // 최초 윈도우의 합 계산
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // 슬라이딩 윈도우를 이동하면서 최대 합 갱신
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

이 예제에서는 배열 arr에서 크기 k의 윈도우를 슬라이딩하면서 윈도우에 포함된 항목들의 최대 합을 계산합니다. 

 

먼저 첫 번째 윈도우의 합을 계산하고, 그 다음으로 윈도우를 한 칸씩 오른쪽으로 이동시키면서 새로운 항목을 추가하고, 가장 왼쪽의 항목을 제거합니다. 이 과정에서 각 스텝마다 최대 합을 갱신하는 형태를 가집니다.

문자열 검색에서의 패턴 매칭 예제

function naiveSearch(text, pattern) {
    let count = 0;
    const n = text.length;
    const m = pattern.length;

    for (let i = 0; i <= n - m; i++) {
        let j;
        for (j = 0; j < m; j++) {
            if (text[i + j] !== pattern[j]) break;
        }
        if (j === m) { // 패턴이 일치하는 경우
            count++;
            console.log("Pattern found at index:", i);
        }
    }

    return count;
}

const text = "THIS IS A TEST TEXT";
const pattern = "TEST";
const result = naiveSearch(text, pattern);
console.log("Total occurrences found:", result);

이 예제에서는 주어진 텍스트에서 특정 패턴을 찾기위해 텍스트를 한 글자씩 슬라이딩하면서, 각 위치에서 패턴의 길이만큼 문자를 비교합니다. 패턴이 완전히 일치하면 해당 위치를 출력하죠.

 

이 방법은 간단하다는 장점이 있지만 텍스트와 패턴의 길이가 길어질수록 비효율적이게 된다는 단점이 있습니다.

데이터 스트림에서의 연속 데이터 포인트의 평균 계산

function slidingWindowAverage(arr, k) {
    let sum = 0;
    let result = [];
    for (let i = 0; i < k; i++) sum += arr[i];
    result.push(sum / k);

    for (let i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k];
        result.push(sum / k);
    }

    return result;
}

const data = [10, 20, 30, 40, 50, 60, 70, 80, 90];
const k = 4;
console.log("Sliding window averages:", slidingWindowAverage(data, k));

이 예제에서는 배열의 각 요소에 대해 크기 k의 윈도우를 이용해 평균을 계산해줍니다. 

첫 번째 윈도우의 평균을 계산한 후, 윈도우를 한 요소씩 슬라이딩하면서 새로운 요소를 추가하고 가장 오래된 요소를 제거합니다. 

이를 통해 각 윈도우의 평균을 효율적으로 계속 업데이트 할 수 있게 됩니다.

---

마무리

슬라이딩 윈도우 기법은 특히 데이터가 크고 연속적인 처리가 필요한 경우에 효율적으로 문제를 해결할 수 있게 해줍니다. 

반복적인 계산을 줄이고 각 단계에서의 계산량을 최소화하여 전체적인 성능을 향상시킬 수 있습니다.