(문제 해결 패턴) 슬라이딩 윈도우

슬라이딩 윈도우

슬라이딩 윈도우 패턴은 배열을 탐색하는 윈도우(Window, 창)을 만들어

배열 내를 순환하는 패턴이다. 

윈도우는 필요한 만큼의 칸 만큼씩 전진하며 필요한 값을 찾을때까지 동작하게 된다.

이 방법은 배열이나 문자열을 순환하며 부분집합(subset)을 찾아낼 때 아주 유용한 문제 해결 방법이다.

 

문제를 풀면서 확인해보자.

---

/*
Write a function called maxSubarraySum which accepts an array of integers
and a number called n.
The function should calculated the maximum sum of n consecutive elements in the array
*/

/*
해설:
정수로 구성된 어레이와 숫자 n을 인수로 갖는 maxSubarraySum이라는 함수를 작성해라.
함수는 어레이 내 n개의 연속적인 엘리먼트 중 가장 큰 값을 return 한다.
*/

maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2) // 10
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4) // 17
maxSubarraySum([4, 2, 1, 6], 1) // 6
maxSubarraySum([4, 2, 1, 6, 2], 4) // 13
maxSubarraySum([], 4) // null

풀이 전 생각)

• 외부 for문으로 인덱스를 하나씩 뽑고, 내부 for문으로 n개의 연속적인 수 만큼 합을 구한다.
• 큰 값은 따로 변수를 만들어 저장해놓은 뒤 어레이를 순환하는 값과 비교하며
  새로 순환한 값이 클 경우, 변수를 교체한다.
• 끝까지 순회된 뒤, 큰 값을 저장한 변수를 return 한다.
• + 배열에 아무것도 없거나 배열의 크기보다 n의 크기가 크다면 null을 리턴해준다.

---

위와 같은 사고방식을 통해 O(N^2)으로 문제를 해결할 수 있다.

아래는 O(N^2)의 시간복잡도를 가진 Naive한 문제 해결이다.

function maxSubarraySum(arr, num) {
    if (num > arr.length) return null
    let max = -infinity   // (1)
    for (let i = 0; i < arr.length - num + 1; i++) {  // (2)
        let temp = 0;                                 // (3)
        for (let j = 0; j < num; j ++) {             
            temp += arr[i + j]    // (4)
        }
        if (temp > max) {         // (5)
            max = temp
        }
    }
    return max
}

/*
- num이 
(1) 맨 처음 연산이 안된 max는 어떠한 값보다 작아야하므로 -infinity를 할당한다.
(2) for문의 조건문을 보면 맨 뒤 num개의 수만큼 연산을 하지 않는다. 이렇게 하지 않으면 
    배열의 인덱스를 넘어서 계산하므로 이상한 값이 나오게 될 것이다.
(3) temp라는 변수를 선언한다. 이 변수에는 임시로 더해지는 값이 들어가게 된다.
(4) 내부 for문을 통해 i부터 num개의 엘리먼트를 순회한다. 
    i는 외부 for문에서 고정되어있고, j는 0부터 시작하므로,  
    만약 i가 2고, n이 2이라면 arr[2 + 0], arr[2 + 1]의 연산이 temp에 들어가게 될 것이다.
(5) temp가 max보다 커진다면 max값은 temp로 바뀐다.
- 모든 순환이 끝난 뒤 max를 리턴하며 종료된다.
*/

• for문을 이중으로 사용하므로, O(N^2)의 시간복잡도를 갖는다.
• 인덱스를 하나씩 증가시키며, n개만큼 순환을 반복한다.
  이런 이유로 외부 for문은 뒤의 n개만큼 뺀 어레이를 순회한다.
• 내부 for문에서는 고정된 인덱스 i부터 num개 만큼 순회한다.

---

 

이 문제풀이는

슬라이딩 윈도우를 적용하면 O(N)의 시간복잡도로 해결할 수 있다.

 

아래는 슬라이딩 윈도우 방법으로 위의 문제를 해결한 것이다.

function maxSubarraySum(arr, num) {
    let maxSum = 0    // (1) 
    let tempSum = 0   // (1)
    if (arr.length < num) return null  // (2)
    for (let i = 0; i < num; i++) {
        maxSum += arr[i]  // (3) 
    }
    tempSum = maxSum      // (4)
    for (let i = num; i < arr.length; i++) {
        tempSum = tempSum - arr[i - num] + arr[i] // (5)
        maxSum = Math.max(maxSum, tempSum)        // (6)
    }
    return maxSum  // (7)
}

/*
(1) 비교할 숫자를 담을 변수를 만든다.
(2) num이 어레이 길이보다 크다면 null을 반환.
(3) num개만큼 순회해서 maxSum값을 미리 만듦.
(4) ★[중요] 윈도우를 만듦. 첫 윈도우는 maxSum값과 같이 설정.
(5) arr[i - num]의 의미를 잘 파악해야 함. 윈도우에서 이전 첫번째 엘리멘트를 제외하고
    새로운 i 엘리먼트를 채워넣음으로써 num개의 연속된 값을 찾은 것 처럼 함.
(6) Math.max()를 통해 가장 큰 값을 maxSum에 저장함. 그리고 어레이를 계속 순회함.
(7) 순환이 다 끝났으면 maxSum을 리턴함.
*/

 

슬라이딩 윈도우 방법을 통해

어레이 내부의 n개씩 연속된 엘리먼트를 O(N)으로 순회할 수 있다.

 

 

새로 배운 메서드/키워드

• arr.length - num + 1과 같은 것들이 직관적으로 이해가 가지 않는다. 펜으로 계속 써봐야하나 싶다.
• O(N^2) 문제에서도, 마지막 num개 만큼의 것들은 순회하지 않는다는 것을 이해하기 힘들었다.
• 앞으로 슬라이딩 윈도우 방식으로 문제를 풀 때, O(N^2)과 O(N) 방법을 모두 도입 해보아야겠다.
• 슬라이딩 윈도우 기법에서는 윈도우를 미리 만들어야 한다는 것을 머릿속에 넣어야겠다.