슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)

1. 슬라이딩 윈도우 알고리즘 (Sliding Window)

( 슬라이딩 윈도우 알고리즘 간단 예제 )
1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 구한다고 가정해보면 아래 5가지의 경우의 수가 나옵니다.

[1, 2, 3], 4, 5, 6, 7
1, [2, 3, 4], 5, 6, 7
1, 2, [3, 4, 5], 6, 7
1, 2, 3, [4, 5, 6], 7
1, 2, 3, 4, [5, 6, 7]

다음으로 합을 계산하는 고정된 크기의 배열의 변화를 보면 [1,2,3] => [2,3,4] => [3,4,5] ... => [5,6,7]입니다. 그렇다면 어떻게 최소한의 계산으로 다음 배열의 합을 구할 수 있을까요?

- 먼저 처음 배열 [1,2,3] 의 합을 구합니다. == 6
- 다음 배열은 [2,3,4]는 [1,2,3] 배열에서 맨 앞 값이 빠지고, 그다음 값인 4가 들어온 모습입니다. 따라서 합은 (6-1+4) == 9 입니다.
- 이러한 규칙을 바탕으로 보면 다음 배열의 값은 전 배열에서  처음 원소를 빼고 다음에 들어올 원소를 더해주면 된다는 것을 알 수 있습니다!!

 

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말합니다.
• 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법입니다.
• 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용합니다.
• 투 포인터(two poitners) 알고리즘과 연동하여 많이 쓰입니다.
  * 1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 원하는 값을 얻는 형태

이미지 출처 : https://velog.io/@zwon/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window

위 이미지를 참고하여 보면, 투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하며, 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점이 있습니다.

 

2. 문제 풀이 - 슬라이딩 윈도우 알고리즘

백준 21921번 : 블로그

21921번: 블로그

function solution(input) {
    let N = Number(input[0].split(' ')[0])
    let X = Number(input[0].split(' ')[1])
    let numArr = input[1].split(' ').map((dr) => Number(dr));

    let curV = 0; // 현재 값
    let maxV = 0; // 최대 값
    let maxC = 0; // 최대 값의 카운트

    for (let i = 0; i < N - X + 1; i++) {

        // 1)번 처음 값은 디폴트로 구해줌 (defalut 값)
        if (i == 0) {
            for (let j = 0; j < X; j++) {
                curV += numArr[j];
            }
            maxV = curV;
            maxC = 1;
        }
        // 다음 값 부터 ~
        else {

            // 2)번 전체적으로 한칸씩 오른쪽으로 이동한다고 생각해보면
            // 한칸 이동한 맨 왼쪽 값은 빼고
            // 한칸 이동한 맨 오른쪽 값은 더해준다!
            curV = curV - numArr[i - 1] + numArr[i + X - 1];

            // 3)번
            if (curV == maxV) {
                maxC += 1;
            } else if (curV > maxV) {
                maxV = curV;
                maxC = 1;
            }
        }
    }

    return maxV == 0 ? 'SAD' : [maxV, maxC].join('\n');
}

// '/dev/stdin'
const input = require('fs').readFileSync('stdin').toString().trim().split('\n');
console.log(solution(input));

• 주어진 배열에서 고정된 개수의 범위에서의 합에서 최댓값과 그 최댓값이 몇 번 나오는지 구하는 전형적인 슬라이딩 윈도우 문제입니다.
• 1) 번 항상 구간의 넓이가 X로 고정되어 있으므로 처음 인덱스가 0 일 때 초기 합산 값을 구합니다.
• 2) 번 그다음부터는 한 칸씩 이동한다고 생각하고 맨 왼쪽 인덱스 값을 빼주고 추가될 맨 오른쪽 값을 더해가면서 최소한의 계산을 통해 합산 값을 재계산합니다.
• 3) 번 최대 값과 비교하면서 카운트를 세주면 끝!

 

3. 문제 풀이 - 투 포인트

백준 2003번 : 수들의 합 2

2003번: 수들의 합 2

function solution(input) {

    let answer = 0;

    let N = Number(input[0].split(' ')[0]); // 배열의 원소 수
    let M = Number(input[0].split(' ')[1]); // sums 값
    let numArr = input[1].split(' ').map((dr) => Number(dr)); // 주어진 숫자 배열

    let sIdx = -1; // 시작하는 지점의 idx
    let fIdx = -1; // 끝나는 지점의 idx
    let sums = 0; // 시작~끝 값의 합

    while (true) {

        // 끝 idx가 배열의 마지막 값까지 올때까지 => 시작, 끝 idx 둘 다 체크
        if (fIdx < N - 1) {
            /* 합이 결과(M)보다 작은 경우 끝 idx 한칸 이동 : 합이 작으므로 끝 idx 값 더한 후 한칸 이동 */
            if (sums < M) {
                sums += numArr[++fIdx];
            }
            /* 합이 결과(M)보다 같거나 큰 경우 시작 idx 한칸 이동 : 합이 크므로 시작 idx 값 뺸 후 한칸 이동 */
            else {
                sums -= numArr[++sIdx];
            }
        }
        // 끝 idx가 배열의 마지막에 오면 : 시작 idx만 옮겨주면 
        else {
            sums -= numArr[++sIdx];
        }

        if (sums == M) answer += 1;

        if (fIdx >= N - 1 && sIdx >= N - 1) break;
    }

    return answer
}

// '/dev/stdin'
const input = require('fs').readFileSync('stdin').toString().trim().split('\n');
console.log(solution(input));

• 시작, 종료 인덱스가 불규칙적으로 바뀔 수 있는 전형적인 투 포인트 문제입니다.
• 현재까지 더한 값이 M(같아야 하는 값) 보다 작으면 종료 인덱스를 한 칸 이동시켜 해당 값을 더해주고, 값이 같거나 작으면 시작 인덱스를 한 칸 이동시킨 값을 빼줍니다. (저는 시작, 종료 인덱스를 -1부터 시작했으므로, ++ 해준 값을 기준으로 더하거나 빼줬습니다.)
• 만일 종료 인덱스가 배열의 마지막 값 일 때(더 이상 종료 인덱스를 증가시킬 수 없을 때)는 시작 인덱스만 증가시켜 줍니다.
• 종료 조건은 시작, 종료 인덱스가 모두 배열의 마지막 값일 때로 잡아 줬습니다.

 

 

슬라이딩 윈도우 알고리즘은 사용 조건에 맞으면 연산 시간 단축에 매우 효과적이며, 해당 알고리즘을 바탕으로 푸는 변형 문제 또한 많으니, 기본 개념에 대해 잘 숙지할 필요가 있다! 또한 투 포인트 알고리즘도 같이 공부하자~