개요
투 포인터 기법처럼 슬라이딩 윈도우 기법도 배열이나 문자열에 사용할 수 있다. 핵심은 요소들이 순서대로 정렬된 반복 가능한 객체에 사용된다는 것이다. 본 글에서는 설명을 간단하게 하기 위해 배열 위주로 설명하지만, 문자열에서의 사용 방식도 전혀 다르지 않다는 것을 알아두자.
배열을 다루는 문제에서 슬라이딩 윈도우는 흔히 사용되는 해결 방식 중 하나이다. 놀랍게도 이 슬라이딩 윈도우는 투 포인터를 이용해 만들어진다! 들어가기에 앞서, 부분 배열이라는 개념을 먼저 이해해야 한다.
부분 배열
배열 내에서 부분 배열이란 연속된 요소들로 구성된 작은 배열을 의미한다. 이 때 모든 요소는 원래 배열 내에 순서대로 인접해 있어야 한다. 예시로 [1, 2, 3, 4]라는 배열이 있을 때, 여기서 만들 수 있는 부분 배열은 다음과 같이 다양하다:
[1],[2],[3],[4][1, 2],[2, 3],[3, 4][1, 2, 3],[2, 3, 4][1, 2, 3, 4]
이렇게 각각의 부분 배열은 시작점과 끝점, 즉 두 개의 인덱스로 나타낼 수 있다. [1, 2, 3, 4] 배열에서 [2, 3]으로 이루어진 부분 배열을 생각해보자. 이 부분 배열은 1이라는 시작점 인덱스와 2라는 끝점 인덱스를 가진다. 이렇게 부분 배열의 시작점을 왼쪽 경계, 끝점을 오른쪽 경계라고 표현할 수 있으며, 이러한 부분 배열을 다른 말로 “윈도우”라고도 부른다.
슬라이딩 윈도우 기법을 언제 사용해야 할까?
슬라이딩 윈도우 기법은 부분 배열을 다루는 문제에서 매우 효율적으로 작동한다. 그러면 우리가 이러한 문제들을 어떻게 파악할 수 있는지 알아보자.
첫째, 문제는 대게 유효한 부분 배열에 대한 명시적이거나 암시적인 제약 조건을 정의한다. 유효한 부분 배열이 되기 위한 두 가지 구성 요소는 다음과 같다:
- 제약 조건: 부분 배열의 어떤 특성을 의미한다. 배열의 합, 고유한 요소의 수, 특정 요소의 빈도 등이 여기에 해당한다.
- 제약 조건에 대한 수치적 제한: 부분 배열이 유효하다고 간주되기 위해 제약 조건이 충족해야 하는 구체적인 숫자 기준이다.
예를 들어, 부분 배열이 유효하다고 선언되는 경우가 있는데, 그 기준은 배열의 합이 10 이하일 때이다. 여기서 제약 조건은 부분 배열의 합이고, 수치적 제한은 <= 10라는 것이다. 따라서 부분 배열의 합이 10 이하인 경우, 그 배열은 제약 조건을 만족시키므로 유효하다.
둘째, 문제는 보통 어떤 방식으로든 유효한 부분 배열을 찾도록 요구한다.
- 가장 흔한 문제는 최적의 유효한 부분 배열을 찾는 것이다. 문제는 어떤 부분 배열이 다른 것보다 더 나은지를 정의한다. 예를 들어, 문제는 가장 긴 유효한 부분 배열을 찾으라고 요청할 수 있다.
- 또 다른 일반적인 문제는 유효한 부분 배열의 수를 찾는 것이다. 이 글의 후반부에서 이 부분을 자세히 살펴볼 것이다.
문제 설명에서 부분 배열에 대해 이야기할 때, 문제 설명을 분석함으로써 슬라이딩 윈도우가 좋은 선택인지 파악해야 한다. 위에서 언급한 것들을 찾을 수 있다면, 슬라이딩 윈도우 기법을 사용하는 것이 바람직하다.
슬라이딩 윈도우 문제가 어떻게 생겼는지 더 잘 이해할 수 있도록, 이 글에서 살펴볼 예제 문제들의 일부를 미리 설명하자면:
- 합계가
k이하인 가장 긴 부분 배열 찾기 "0"이 최대 하나인 가장 긴 부분열 찾기- 곱이
k미만인 부분 배열의 수 찾기
알고리즘
슬라이딩 윈도우의 기본 개념은 유효한 부분 배열만을 대상으로 한다는 점이다. 여기서 부분 배열은, 시작 요소의 인덱스를 나타내는 왼쪽 경계와 마지막 요소의 인덱스를 나타내는 오른쪽 경계로 정의된다. 슬라이딩 윈도우에서는 현재 고려 중인 부분 배열을 나타내는 두 변수, left와 right를 사용한다.
처음에는 left와 right 모두 0으로 설정하여 배열의 첫 번째 요소만을 포함하는 부분 배열을 살펴본다. “윈도우” 크기를 확장하기 위해 right를 증가시킨다. right를 증가시키면, 마치 새 요소를 우리의 윈도우에 “추가”하는 것과 같다.
그러나 새 요소를 추가한 후에 부분 배열이 유효하지 않게 되면 어떻게 될까? 윈도우에서 몇몇 요소를 “제거”하여 다시 유효한 상태로 만들어야 한다. 요소를 “제거”하려면 left를 증가시켜 윈도우를 줄일 수 있다.
요소를 추가하고 제거함으로써, 우리는 윈도우를 입력의 왼쪽에서 오른쪽으로 “슬라이딩”한다. 윈도우의 크기는 계속 변한다. 유효하지 않을 때까지 가능한 한 크게 확장되고, 그 후에는 축소된다. 그러나 항상 right로 슬라이딩되며, 입력의 끝에 도달할 때까지 계속된다.
이 알고리즘이 어떻게 작동하는지 설명하기 위해 구체적인 예를 들어보겠다. 양의 정수 배열 nums와 정수 k가 주어졌다고 가정해보자. 우리는 합계가 k 이하인 가장 긴 부분 배열의 길이를 찾아야 한다. 예시로, nums = [3, 2, 1, 3, 1, 1]이고 k = 5라고 하자.
초기값이 left = right = 0이므로, 우리의 윈도우는 첫 번째 요소인 [3]만을 포함한다. 이제 right를 확장하여 제약 조건이 깨질 때까지 계속한다. left = 0, right = 2일 때 이 상황이 발생하며, 우리의 윈도우는 [3, 2, 1]이 된다. 여기서의 합계는 6으로, k보다 크다. 이제 left에서 윈도우를 줄여 제약 조건이 깨지지 않을 때까지 계속해야 한다. 하나의 요소를 제거하고 나면, 윈도우는 다시 유효하게 된다: [2, 1].
이 알고리즘의 나머지 부분에서 이 3을 영영 제거해버리는 것이 옳은 것일까? 입력값은 양의 정수만을 가지고 있기 때문에, 더 긴 부분 배열은 더 큰 합을 의미한다. 우리는 이미 [3, 2, 1]이 너무 큰 합을 결과로 가져온다는 것을 알고 있다. 따라서 우리가 이 3을 계속 유지한다면 어떠한 유효한 윈도우도 다시 가질 수 없을 것이다. 왜냐하면 오른쪽에서 더 많은 요소들을 추가한다면 합은 더 커질 뿐이기 때문이다. 그래서 우리는 이 알고리즘의 나머지 부분에서 이 3을 제거해버릴 수 있다.
구현
슬라이딩 윈도우 기법의 동작 원리를 이해했으니, 이제 이를 어떻게 구현할지 알아보자. 이 섹션에서는 이전 예제(합이 k 이하인 가장 긴 부분 배열 찾기)를 참고할 것이다.
앞서 설명했듯이, 제약 조건을 식별해야 한다. 이 예제에서의 제약 조건은 윈도우의 합이다. 윈도우에 요소가 추가되거나 제거될 때, 윈도우의 합을 어떻게 추적할 수 있을까? 그 방법 중 하나로, 윈도우를 별도의 배열에 유지하는 방법이 있다. 오른쪽에서 요소를 추가할 때마다 배열에 요소를 추가한다. 왼쪽에서 요소를 제거할 때는 배열에서 해당 요소를 제거한다. 이렇게 하면 현재 윈도우의 합을 항상 별도의 배열에 있는 요소를 합산함으로써 계산할 수 있다.
하지만 이 방법은 매우 비효율적이다. 요소를 제거하고 윈도우의 합을 찾는 것이 $O(n)$의 연산이기 때문이다. 더 좋은 방법은 없을까?
사실 윈도우를 별도의 배열을 만들어서 저장할 필요가 없다. 현재 합을 추적하는 어떤 변수만 있으면 된다. 이 변수를 curr이라고 하자. right에서 새 요소를 추가할 때 curr += nums[right]를 수행한다. 왼쪽에서 요소를 제거할 때는 curr -= nums[left]를 수행한다. 이런 식으로 모든 연산은 $O(1)$에서 수행되도록 할 수 있다.
다음으로, 그렇다면 포인터 left와 right를 어떻게 이동시킬까? 우리는 윈도우를 계속 확장하려고 한다. 또한 윈도우는 항상 right으로 슬라이드한다 - 중간에 몇 번 크기가 줄어들 수는 있지만, 기본적으로 right로의 이동을 멈추지 않는다. right는 항상 앞으로 이동하기 때문에 for 문을 사용하여 입력값에 대해 right를 반복할 수 있다. for 문의 각 반복에서는 요소 nums[right]를 윈도우에 추가할 것이다.
left는 어떨까? left를 이동하면 윈도우가 줄어든다. 윈도우는 유효하지 않아질 때만 줄어든다. curr를 유지함으로써 현재 윈도우가 유효한지 쉽게 판단할 수 있으며, curr <= k 조건을 확인함으로써 판단할 수 있다. 새 요소를 추가했을 때, 윈도우가 유효하지 않게 되면 left에서 여러 요소를 제거한다. 예를 들어, nums = [1, 1, 1, 3]이고 k = 3이라고 하자. 3에 도달하여 윈도우에 요소를 추가할 때, 윈도우는 유효하지 않게된다. 윈도우가 다시 유효해지기 위해선 left에서 요소 세 개를 제거해야 한다.
이는 제거를 수행하기 위해 while 문을 사용해야 함을 의미한다. 조건은 while (curr > k) (윈도우가 유효하지 않은 동안)가 될 것이다. 제거를 수행하기 위해 curr -= nums[left]를 수행하고, while 문의 각 반복에서 left를 증가시킨다.
마지막으로, 어떻게 답을 업데이트할 수 있을까? 각 for 문 반복에서, while 문 이후의 윈도우는 항상 유효한 윈도우가 된다. 여기서 코드를 작성하여 답을 업데이트할 수 있다. 윈도우의 길이에 대한 공식은 right - left + 1 이다.
다음은 위의 모든 설명을 보여주는 의사 코드이다:
1
2
3
4
5
6
7
8
9
10
11
12
13
function fn(nums, k):
left = 0
curr = 0
answer = 0
for (int right = 0; right < nums.length; right++):
curr += nums[right]
while (curr > k):
curr -= nums[left]
left++
answer = max(answer, right - left + 1)
return answer
일반적인 템플릿에 대한 의사 코드는 다음과 같다:
1
2
3
4
5
6
7
8
9
10
function fn(arr):
left = 0
for (int right = 0; right < arr.length; right++):
arr[right]의 요소를 윈도우에 "추가"하기 위한 일부 로직을 수행한다
while WINDOW_IS_INVALID:
arr[left]의 요소를 윈도우에서 "제거"하기 위한 일부 로직을 수행한다
left++
결과를 업데이트하기 위한 일부 로직을 수행한다
슬라이딩 윈도우는 왜 효율적인가?
배열에 대해 부분 배열의 개수는 얼마나 될까? 배열의 길이가 $n$이라면, 길이가 1인 부분 배열은 $n$개 있다. 그 다음으로, 길이가 2인 부분 배열은 $n - 1$개 있다(마지막 인덱스를 제외한 모든 인덱스가 시작 인덱스가 될 수 있다), 길이가 3인 부분 배열은 $n - 2$개 있다, 이런 식으로 길이가 $n$인 부분 배열 1개까지 계속된다. 이러한 규칙에 따라 부분 배열의 총 개수는 $\sum_{k=1}^{n} \frac{k \cdot (n + 1)}{2}$로 나타낼 수 있다(이는 이 수열의 부분 합이다).
시간 복잡도의 관점에서 보면, 모든 부분 배열을 검사하는 어떤 알고리즘도 최소 $O(n^2)$의 시간 복잡도를 가지며, 이는 대부분의 경우에 있어 너무 느리다.
슬라이딩 윈도우 기법은 최대 $2n$번의 윈도우 이동을 보장한다 - right 포인터는 $n$번 이동할 수 있고, left 포인터도 $n$번 이동할 수 있다. 이는 각 윈도우에 대한 로직 처리가 $O(1)$의 시간 복잡도를 가진다면, 슬라이딩 윈도우 알고리즘은 $O(n)$의 시간 복잡도로 실행되며, 이는 훨씬 빠르다는 것을 의미한다.
의문 사항: for 문 내부에 while 문이 있으므로, 시간 복잡도는 $O(n^2)$가 되지 않을까? 사실 여전히 $O(n)$이다. 이러한 현상의 이유는 전체 알고리즘 동작 과정에서 while 문이 총 $n$번만 반복되기 때문이다(변수
left는0에서 시작해n을 초과하지 않고 증가만 한다). 만약 for 문 한 번의 반복 동안 while 문이 $n$번 실행된다면, for 문의 나머지 반복에서는 while 문이 실행되지 않을 것이다. 이런 현상을 우리는 분할 상환 분석이라고 부른다. 이는 for 문 내의 반복에 대한 최악의 경우 시간 복잡도가 $O(n)$이지만, 알고리즘의 전체 실행 시간을 고려하면 $O(1)$으로 평균화된다는 것을 의미한다.
다음은 슬라이딩 윈도우의 몇 가지 예제이다.
예제 1: 합이 k 이하인 가장 긴 부분 배열의 길이
양의 정수들로 이루어진 배열
nums와 정수k가 주어졌을 때, 합이k이하인 가장 긴 부분 배열의 길이를 찾아보자. 이 문제는 위에서 이야기한 바와 같다. 이제 이를 공식적으로 해결해보자.
문제의 목적은 주어진 배열 nums와 정수 k에 대해, 합이 k 이하인 가장 긴 부분 배열의 길이를 찾는 것이다. 이를 위해, 윈도우의 현재 합(curr)을 추적하며, 윈도우의 합이 k 이하인 조건을 만족하도록 윈도우를 조절할 것이다
예를 들어, nums = [3, 1, 2, 7, 4, 2, 1, 1, 5]이고 k = 8인 경우를 살펴보자.
처음에는 윈도우가 비어 있다. 이제 우리는 제약 조건을 만족시키면서 윈도우를 [3, 1, 2]로 확장할 수 있다. 그러나 7을 윈도우에 추가하면, 윈도우의 합이 너무 커져 제약 조건을 벗어나게 된다. 따라서 윈도우의 합이 다시 8 이하가 될 때까지 윈도우를 좁혀야 한다. 이 과정은 윈도우가 [7]로 좁혀질 때까지 진행된다. 이제 다음 요소를 추가하려고 시도할 때, 윈도우는 너무 커져서 이번에는 7을 제거해야 한다. 이렇게 되면 윈도우는 [4]가 된다. 이제 윈도우를 [4, 2, 1, 1]로 확장할 수 있지만, 다음 요소를 추가하면 또 합이 너무 커져 제약 조건에 맞지 않게 된다. 따라서 왼쪽에서 요소를 제거하여 제약 조건을 만족시켜야 한다. 이 과정은 윈도우가 [1, 1, 5]로 좁혀질 때까지 진행된다. 이 과정을 진행하며 찾은 가장 긴 부분 배열은 [4, 2, 1, 1]이며, 이는 정답이 4임을 의미한다.
윈도우의 오른쪽 경계를 이동하여 요소를 추가할 때는 curr에 value를 더하며, 윈도우의 왼쪽 경계를 이동하여 요소를 제거할 때는 curr에서 value를 뺀다. 만약 curr이 k보다 크다면, 요소를 계속 제거하여 curr이 k 이하가 될 때까지 윈도우를 좁힐 수 있다.
예제 1 상세 설명
코드에서 각 변수의 역할은 다음과 같이 요약할 수 있다:
left: 현재 윈도우의 가장 왼쪽 인덱스이다.right: 현재 윈도우의 가장 오른쪽 인덱스이다.curr: 현재 윈도우의 합이다.ans: 지금까지 본 가장 긴 유효 윈도우의 길이이다.
right를 입력값에 대해 반복하면서 윈도우에 요소를 추가한다. nums[right]를 curr에 더함으로써 curr를 업데이트한다. 윈도우가 유효하지 않게 될 때(curr > k), nums[left]를 curr에서 빼서 윈도우에서 요소를 제거한다. 그런 다음 left를 증가시킨다.
윈도우가 다시 유효해질 때까지 이 작업을 수행해야 하므로 while 문을 사용한다. 여기서 윈도우의 크기 공식은 right - left + 1이다. 윈도우가 유효해질 때만 답을 업데이트해주자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findLength(vector<int>& nums, int k) {
// curr은 윈도우의 현재 합이다.
int left = 0, curr = 0, ans = 0;
for (int right = 0; right < nums.size(); right++) {
curr += nums[right];
while (curr > k) {
curr -= nums[left];
left++;
}
ans = std::max(ans, right - left + 1);
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn find_length(nums: Vec<i32>, k: i32) -> i32 {
let (mut left, mut curr, mut ans) = (0, 0, 0);
for right in 0..nums.len() {
curr += nums[right];
while curr > k {
curr -= nums[left];
left += 1;
}
ans = std::cmp::max(ans, (right as i32) - (left as i32) + 1);
}
ans
}
주어진 부분 배열은 left에서 시작하여 right에서 끝나며, 길이는 right - left + 1이다. 이 알고리즘은 for 문 내에서 수행되는 모든 작업이 상환 $O(1)$이므로, 시간 복잡도는 $O(n)$이다. 여기서 $n$은 nums의 길이를 의미한다. 공간 복잡도는 3개의 정수 변수만을 사용하므로 상수이다.
예제 2: 오직 “1”만 포함하는 가장 긴 부분 문자열의 길이
이진 문자열
s가 주어지며, 이는"0"과"1"만을 포함한다. 사용자는"0"하나를 선택하여"1"로 바꿀 수 있다. 그렇다면 오직"1"만을 포함하는 가장 긴 부분 문자열은 얼마나 길게 만들 수 있는가?예를 들어,
s = "1101100111"경우, 답은5가 된다.2번 인덱스에서"0"을"1"로 바꾸면, 문자열은"1111100111"이 되기 때문이다.
이 문자열은 "1"과 "0"만을 포함할 수 있으므로, 이 문제는 “최대 한 개의 "0"을 포함하는 가장 긴 부분 문자열은 무엇인가?”로 바라볼 수 있다. 이 접근 방식은 슬라이딩 윈도우 기법을 사용하여 문제를 쉽게 해결할 수 있도록 한다. 여기서 조건은 window.count("0") <= 1가 되어야 한다. 우리는 현재 윈도우 내의 "0"의 개수를 추적하기 위한 정수형 변수 curr를 사용할 수 있다. 이 변수는 윈도우 내의 "0"의 개수를 계산하는 데 사용된다.
예제 2 상세 설명
입력값은 "1" 또는 "0"만을 포함할 수 있다. 우리는 연속적인 "1"의 최대 길이를 찾아야 한다. 요소가 "1"이 아닌 경우 모두 "0"이기 때문에, 이 문제는 “최대 하나의 0을 포함하는 가장 긴 부분 문자열은 무엇인가?”와 같다. 이유는 그 "0" 하나를 뒤집으면, 해당 부분 문자열의 나머지 문자가 모두 "1"이 됨이 보장되기 때문이다.
문제는 부분 문자열의 길이를 묻고 있으며, 어떤 부분 문자열이 유효한지도 정의하고 있다. 제약 조건은 “부분 문자열 안에 있는 0의 수”이다. 수치적 제한은 <= 1이며, 이에 따라 제약 조건을 추적하기 위한 정수 curr를 사용하면, 윈도우의 유효성을 판단하는 조건은 curr <= 1이 된다.
이제 우리는 이전 예제에서 사용된 동일한 절차를 적용할 수 있다. right라는 포인터를 사용하여 요소들을 순회한다. 각 요소에서 s[right]가 "1"인 경우에는 특별히 할 일은 없다. 만약 "0"이라면, curr 값을 하나 증가시킨다. 만약 윈도우가 유효하지 않게 되면(curr > 1), left의 요소를 제거하기 시작한다. s[left]가 "0"인 경우, curr 값을 감소시킬 수 있다. 요소를 제거하기 위해 left를 증가시키며, 윈도우의 크기는 항상 right - left + 1이다. while 루프가 끝난 후, 윈도우가 유효하다는 것이 확인되면, 이 값을 사용하여 우리의 답을 업데이트한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findLength(string s) {
// curr은 현재 윈도우가 갖고 있는 0의 개수이다.
int left = 0, curr = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
if (s[right] == `0`) {
curr++;
}
while (curr > 1) {
if (s[left] == `0`) {
curr--;
}
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fn find_length(s: &str) -> usize {
let (mut left, mut curr, mut ans) = (0, 0, 0);
let chars: Vec<char> = s.chars().collect();
for right in 0..s.len() {
if chars[right] == `0` {
curr += 1;
}
while curr > 1 {
if chars[left] == `0` {
curr -= 1;
}
left += 1;
}
ans = ans.max(right - left + 1);
}
ans
}
이전 예제와 같이, 이 문제는 각 반복마다 일어나는 작업이 상환 상수 시간에 이루어지므로 $O(n)$의 시간 복잡도를 가진다. 여기서 $n$은 문자열 $s$의 길이를 나타낸다. 더 나아가, 약간의 정수 변수만이 사용되기 때문에 이 알고리즘은 $O(1)$의 공간 복잡도를 가진다.
부분 배열의 수
어떤 문제가 특정 조건을 만족하는 부분 배열의 수를 묻는 경우, 슬라이딩 윈도우 기법을 계속 사용할 수 있지만, 부분 배열의 수를 계산하기 위한 미묘한 수학적 기법을 사용해야 한다.
슬라이딩 윈도우 알고리즘을 적용하여 현재 left와 right로 구성된 윈도우를 가지고 있다고 가정하자. right 인덱스에서 끝나는 유효한 윈도우는 몇 개일까?
현재 윈도우는 (left, right)이며, 이어서 (left + 1, right), (left + 2, right) 등 right에서 (right, right)까지 계속된다(오직 right 위치에 있는 요소만 포함).
right 경계는 고정되어 있고, left 경계에 대해서는 left와 right 사이의 임의의 값(포함된 값)을 선택할 수 있다. 따라서, right 인덱스에서 끝나는 유효한 윈도우의 수는 윈도우의 크기와 같아야 하며, 이는 right - left + 1로 알려져 있다.
예제 3: K보다 작은 부분 배열 곱
양의 정수 배열
nums와 정수k가 주어졌을 때, 부분 배열 내 모든 요소들의 곱이k보다 엄격하게 작은 부분 배열의 수를 반환해보자.예를 들어, 입력이
nums = [10, 5, 2, 6],k = 100인 경우, 결과는8이다.k보다 작은 곱을 가진 부분 배열은 다음과 같다:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
이 문제를 풀이하기 위해 우리가 방금 배운 내용을 적용해보자. 위 설명란의 예제에서 인덱스 2에 도달하면, 곱셈 결과가 너무 커져서 가장 왼쪽의 원소 10을 제거해야 한다. 이제, 윈도우는 유효하며 길이는 2이다. 이 상황은 현재 위치에서 끝나는 두 개의 유효한 부분 배열([2] 및 [5, 2])이 존재한다는 것을 의미한다.
이전 예시들에서는, while 문 이후에 답(최장 길이)을 업데이트했다. 이 경우에는 윈도우가 유효해야 한다는 전제 하에, 현재 윈도우의 크기를 결과에 추가할 수 있다. 윈도우의 유효성을 판단하는 기준은 곱이 k보다 작아야 한다는 것이다.
추가적으로, k <= 1인 경우에는 유효한 윈도우를 갖출 수 없으므로 바로 0을 반환한다.
예제 3 상세 설명
제약 조건은 윈도우 내의 모든 요소의 곱이며, 이는 k보다 작아야 한다. 만약 curr라는 변수를 사용해 윈도우의 현재 곱을 나타내고 있다면, 윈도우가 유효하지 않은 상태가 되는 조건은 curr >= k일 것이다. 윈도우에 요소를 추가할 때는 curr *= nums[right]를 사용하고, 요소를 제거할 때는 curr /= nums[left]를 사용한다.
while 문이 종료되었을 때의 윈도우는 유효한 상태이다. 그 상태에서 right - left + 1 값을 결과에 더하여 윈도우의 크기를 계산할 수 있다. 이렇게 하면, 특정 조건을 만족하는 부분 배열의 수를 찾는 문제에서 슬라이딩 윈도우 기법을 활용할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) {
return 0;
}
int ans = 0, left = 0, curr = 1;
for (int right = 0; right < nums.size(); right++) {
curr *= nums[right];
while (curr >= k) {
curr /= nums[left];
left++;
}
ans += right - left + 1;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fn num_subarray_product_less_than_k(nums: &[i32], k: i32) -> i32 {
if k <= 1 {
return 0;
}
let (mut ans, mut left, mut curr) = (0, 0, 1);
for right in 0..nums.len() {
curr *= nums[right];
while curr >= k {
curr /= nums[left];
left += 1;
}
ans += right - left + 1;
}
ans as i32
}
각 루프의 반복마다 이루어지는 작업은 상환 상수 시간이 소요되므로, 이 알고리즘의 실행 시간은 $O(n)$이며, 여기서 $n$은 nums의 길이를 나타낸다. 공간 복잡도는 $O(1)$이다.
고정 윈도우 크기
앞서 다룬 예제들에서는 윈도우 크기가 동적이었다. 제약 조건을 만족시키는 범위 내에서 가능한 한 오른쪽으로 윈도우를 확장하고, 제약 조건이 위반될 때 왼쪽의 요소를 제거하는 방식이었다. 그러나 때때로 문제에서는 고정된 길이 k를 지정하기도 한다.
이러한 문제는 해결하기 쉽다. 두 인접한 윈도우 간의 차이는 단 두 요소뿐이기 때문이다. 오른쪽에 요소 하나를 추가하고, 윈도우의 길이를 유지하기 위해 왼쪽의 요소 하나를 제거하면 된다.
먼저 첫 번째 윈도우(인덱스 0부터 k - 1까지)를 만든다. k 크기의 윈도우가 준비되면, i 인덱스에 요소를 추가할 경우, i - k 인덱스의 요소를 제거한다. 예를 들어, k = 2이고 현재 인덱스 [0, 1]의 요소를 가지고 있는 상황에서, 2를 추가하면: [0, 1, 2]가 된다. 그러나 윈도우 크기를 k = 2로 유지하기 위해, 2 - k = 0을 제거하면: [1, 2]가 된다.
다음은 이를 위한 의사 코드이다:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fn(arr, k):
curr = 윈도우를 추적하기 위한 데이터
// 첫 번째 윈도우 구축
for (int i = 0; i < k; i++)
첫 번째 윈도우를 구축하기 위해 curr나 다른 변수를 사용하여 작업을 수행한다
ans = 문제의 성격에 따라 여기서 curr와 동일할 수 있는 결과 변수
for (int i = k; i < arr.length; i++)
arr[i]를 윈도우에 추가한다
arr[i - k]를 윈도우에서 제거한다
ans를 업데이트한다
return ans
예제 4: 가장 큰 합을 가진 부분 배열의 합
정수 배열
nums와 정수k가 주어졌을 때, 길이가k인 부분 배열 중 가장 큰 합을 가진 부분 배열의 합을 찾아보자.
우리는 이전에도 언급했듯이, 길이가 k인 윈도우를 만들고 배열을 따라 이동시키는 방법을 사용할 수 있다. 윈도우의 크기가 k를 유지하도록 요소를 추가하거나 제거해야 한다. i 위치에 값을 추가하는 경우, i - k 위치의 값을 제거해야 한다.
첫 번째 윈도우를 만든 후에는, 첫 윈도우의 합을 기준으로 결과 값을 curr에 초기 설정한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findBestSubarray(vector<int>& nums, int k) {
int curr = 0;
for (int i = 0; i < k; i++) {
curr += nums[i];
}
int ans = curr;
for (int i = k; i < nums.size(); i++) {
curr += nums[i] - nums[i - k];
ans = max(ans, curr);
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn find_best_subarray(nums: &Vec<i32>, k: usize) -> i32 {
let mut curr = 0;
// let mut curr: i32 =nums.iter().take(k).sum();
for &num in nums.iter().take(k) {
curr += num;
}
let mut ans = curr;
for i in k..nums.len() {
curr += nums[i] - nums[i - k];
ans = ans.max(curr);
}
ans
}
for 문의 전체 반복은 $n$과 같으며, 여기서 $n$은 nums의 길이를 나타낸다. 각 반복에서의 작업은 일정하여, 이 알고리즘의 시간 복잡도는 $O(n)$이고, 추가적인 공간을 거의 사용하지 않기 때문에 공간 복잡도는 $O(1)$이다.
마무리
슬라이딩 윈도우는 다양한 상황에서 활용 가능한 중요한 패턴이다. 이 글에서는 슬라이딩 윈도우 문제의 기본적인 개념만을 소개하였다는 점을 강조하고 싶다. 많은 슬라이딩 윈도우 문제들이 해시맵을 사용하므로, 해시맵에 대해 배운 후에 다양한 슬라이딩 윈도우 문제를 추가로 다룰 예정이다.
보너스 문제
- 643. Maximum Average Subarray I
- 1004. Max Consecutive Ones III
- 209. Minimum Size Subarray Sum
- 1456. Maximum Number of Vowels in a Substring of Given Length
- 1208. Get Equal Substrings Within Budget
출처: Leetcode