Sliding-Window, Two Pointers 알고리즘

이 글은 슬라이딩 윈도우와 투 포인터 알고리즘을 정리하는 글입니다. 비슷한 성향의 알고리즘이라 한 포스팅에 같이 정리해봅니다.

01  Sliding Window

창문이 옮겨간다는 이름의 이 알고리즘 풀이 방식은 고정된 범위(창문)가 자동으로 옮겨가면서(=구간의 길이가 같음) 창문 내에 있는 데이터를 이용해 조건에 해당하는 답을 반환하게 된다. 시간복잡도가 O(n)이다.

교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법으로 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리한다.

배열이나 리스트의 요소들의 일정 범위 값을 비교할 때 사용되며, 배열의 정렬 여부에 관계 없이 활용 가능하다.

예시문제

 

문제 원문 및 설명 링크

크기가 num인 부분배열의 최대 합을 반환하는 함수를 정의한다.
Input: [2, 6, 9, 2, 1, 8, 5, 6, 3]
num : 3

//1. 결과 부분 집합과 최대 합을 임시 합과 비교하여 추적하는 두 변수를 정의
function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
}

//2. 배열의 길이가 num보다 작으면 loop 전에 null을 반환
function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
}

//3. index 0부터 num의 크기만큼 loop하고, 모든 요소를 tempSum에 추가
function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
    for(let i = 0; i < num; i++) {
       tempSum += arr[i];    
    }
}

//4. tempSum을 maxSum 변수로 설정하고 num부터 다시 배열을 반복하여 새 tempSum을 얻음 
/*
새로운 tempSum은 배열의 슬라이딩 윈도우에 의해 달성되므로 새 하위 집합의 이전 요소를 빼고 
새 요소를 추가할 수 있음
*/
function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
    for(let i = 0; i < num; i++) {
       tempSum += arr[i];    
    }
    maxSum = tempSum;
    for(let i = num; i < arr.length; i++) {
       tempSum = tempSum - arr[i - num] + arr[i];
    }
}

//5. maxSum과 tempSum을 비교하고 더 큰 합계를 maxSum으로 설정하고 maxSum 반환
function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
    for(let i = 0; i < num; i++) {
       tempSum += arr[i];    
    }
    maxSum = tempSum;
    for(let i = num; i < arr.length; i++) {
       tempSum = tempSum - arr[i - num] + arr[i];
       maxSum = Math.max(tempSum, maxSum);       
    }      
    return maxSum;
}

//결과: 19

02  Two Pointers

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태의 알고리즘이다. Sliding Window와는 다르게 구간의 길이는 가변적이다. 위와 마찬가지로 시간복잡도는 O(n)이며, 주로 정렬된 배열을 대상으로 활용된다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
(맨 처음에는 start = end = 0이며, 항상 start<=end을 만족해야 한다.)
2. 현재 부분 합이 M과 같다면, 카운트한다.
3. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다.
4. 현재 부분 합이 M 보다 크다면, start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2~4 과정 반복

 

즉, start와 end 를 무조건 증가시키는 방향으로만 변화시켜가면서 도중에 부분 배열의 합이 정확히 M이 되는 경우를 세는 것이다.

while (left <= right && right < n) {
    if (sum < m) {
            ~~
            if (right < n) {
                right += 1;
                sum += arr[right];
                //Right를 이동시켜줄때마다 변한 Right에 위치하는 값을 sum에 추가시켜주고
            }
        }
        else if (sum >= m) {
    
            ~~
 
            if (left <= right) {
                sum -= arr[left];
                left++;
                //Left를 이동시켜줄때마다 변한 Left에 위치하는 값을 빼줘야한다.
            }
        }
}

 

---

참고 링크

https://velog.io/@hanei100/TIL-Sliding-Window

https://naivep.tistory.com/52

https://ji-musclecode.tistory.com/37

https://mmirann.github.io/algorithm/concept/2021/12/10/twopointers_slidingwindow.html

https://window6kim.tistory.com/24

https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md

https://medium.datadriveninvestor.com/javascript-algorithm-2-sliding-window-66622c7cb4f8