슬라이딩 윈도우 알고리즘과 투 포인터 알고리즘

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

고정된 윈도우(특정 범위를 나타내는 말)의 내부 요소값을 이용하여 문제를 풀이하는 알고리즘

위의 사진에서는 윈도우의 범위가 5이다.

첫번째는 1, 3, 2, 6, -1 이 윈도우 내에 있고

두번째에는 3, 2, 6, -1, 4 가 윈도우 내에 존재한다.

첫번째에서 두번째로 넘어갈 때, 맨 앞에 위치한 1은 윈도우 내에서 제거되고,
1을 제외한 3, 2, 6, -1 은 재사용되며 그 뒤로 새로운 요소인 4가 추가가 된다.

 

슬라이딩 윈도우 알고리즘는 재사용이 중요하다고 생각한다.

고정된 범위를 가지고 움직이는 윈도우 내에 있는 요소들을 움직이는 만큼 앞에 있는 요소를 제거하고
나머지 값은 재사용하며 그 뒤에 새로운 값들을 배정해 사용한다.

 

시간복잡도 : O(N + K)  (배열의 크기 = N, 고정된 윈도우의 크기 = K)

 

그렇다면 코드로 작성하면 어떻게 될까?

예제의 문제를 보도록 하자

 

프로그래머스

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) {
                sum = elements.slice(0, i).reduce((acc, cur) => acc + cur, 0);
            }
            else {
                sum -= elements[j-1];
                sum += elements[(j+i-1) % len];
            }
            sumSet.add(sum);
        }
    }
    return sumSet.size;
}

위의 문제에서 1, 2, 3, 4, 5...elements.length 까지 길이를 같는 윈도우 내에 있는 수들의 합을 중복 없이 구하는 문제이다.

let sum = 0;
for (let j=0; j<len; j++) {
    if (j === 0) {
        sum = elements.slice(0, i).reduce((acc, cur) => acc + cur, 0);
    }
    else {
        sum -= elements[j-1];
        sum += elements[(j+i-1) % len];
    }
    sumSet.add(sum);
}

이 for문에서 슬라이딩 윈도우 알고리즘이 사용되었는데,
각 길이의 맨 처음 구해진 윈도우의 수들의 합은 처음 따로 구해주고
나머지 합들은 기존에 구해진 sum에서 이전 수를 빼주고 새로 들어올 수를 더하며 문제를 풀었다.

 

정리

• 고정된 사이즈의 범위 내에서 있는 데이터를 이용
• 교집합되는 데이터를 공유하며, 윈도우가 이동하며 밀리는 데이터와 새로 들어오는 데이터를 갱신
• 배열이나 리스트의 일정 범위 값을 비교, 확인 할 때 유용하다.

 

투 포인터(Two Pointer) 알고리즘

리스트에 순차적으로 접근 시 두개의 요소의 위치를 기록하며 처리하는 알고리즘이다.

정렬된 두 리스트의 합집합에도 사용된다.

 

시간복잡도 : O(N)

 

예시

배열에서 배열의 순서대로 더한 값이 M이 되는 경우의 수를 구해라

위의 그림에 앞서 처음에는 시작과 끝을 표시하는 s와 e는 index 0 부터 시작된다.

그리고 e의 index가 1 증가해 s = 0, e = 1에서 s와 e 사이에 있는 요소들의 합은 1이며,

다음 사진에서는 3, 그 다음에는 6이 된다.

이때 요소들의 합이 5가 되는 경우에 answer += 1이 되므로,
합이 M보다 크면 s의 index를 1 증가시켜 똑같은 동작을 반복해 진행한다.

그리고 s가 배열의 끝에 도달하면 과정이 종료된다.