[자료구조/알고리즘] 슬라이딩 윈도우 알고리즘

1️⃣ 슬라이딩 윈도우란?

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘
• 배열이나 리스트의 요소의 일정 범위 값을 비교할 때 사용하면 매우 유용
• 배열과 그 부분 배열을 어떤 조건하에서 계산하는 경우에 주로 사용
• 예) 구간 합 구하기, 부분 문자열 구하기 등

2️⃣ 구간마다 일일이 합을 구할 경우 vs 슬라이딩 윈도우 알고리즘을 활용할 경우

1. 구간마다 일일이 합을 구할 경우

• 앞에서 구했던 값이 있음에도 불구하고 다음 번에 또 구하고.. 또 구하고.. 시간복잡도가 늘어날 수밖에 없다 -> 효율성이 떨어짐

2. 슬라이딩 윈도우 알고리즘을 활용할 경우

• 최초 윈도우에 대해서만 값을 구하고
• 한 칸씩 윈도우를 밀 때에는 이전 구간 합을 활용함 -> 효율성 좋음 
• 윈도우에서 빠진 원소의 값을 빼주고 윈도우에 들어온 원소의 값을 더해줌

3️⃣ 문제

const solution = (elements) => {
    const sumSet = new Set();
    
    const len = elements.length;
    for (let i=1; i<=len; i++) { // 연속 부분 수열의 길이
        // 슬라이딩 윈도우 
        let sum = 0;
        for (let j=0; j<len; j++) { // 연속 부분 수열 시작 지점의 인덱스
            if (j === 0) { // 최초 한 번의 창문에 대해서만 직접 합을 구하기
                for (let k=0; k<i; k++) {
                    sum += elements[k];
                }
            }
            else { // 이후 창문들에 대해서는 이전에 구한 합을 활용하기
                sum -= elements[j-1]; // 윈도우에서 빠진 값 빼주고
                sum += elements[(j+i-1) % len]; // 윈도우에 들어온 값 더하기
            }
            sumSet.add(sum);
        }
    }
    
    // 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return
    return sumSet.size;
}

 

- 참고 블로그

https://velog.io/@dianestar/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%97%B0%EC%86%8D-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%95%A9%EC%9D%98-%EA%B0%9C%EC%88%98-JavaScript-%EA%B5%90%EA%B3%B5-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8A%A4%ED%84%B0%EB%94%94-48%EC%A3%BC%EC%B0%A8

[프로그래머스] 연속 부분 수열 합의 개수 (JavaScript) | 교공 알고리즘 스터디 48주차