길이가 $N$인 수열 ${a_n}$에서 연속되는 $K$개의 원소의 합 중 가장 큰 값을 구하여라.
보기에는 간단해 보이는 이 문제, 어떻게 해결할 수 있을까?
방법1: 모두 계산해보기
가장 먼저 떠오르는 방법은 반복문을 이용해 모두 다 계산해보는 방법이다.
가능한 모든 범위에 대해 합을 구한 후, 최댓값을 출력하면 정답이 나오게 된다.
answer = -float('inf')
for i in range(N - K + 1):
answer = max(answer, sum(a[i:i+K]))
print(answer)
위 방식의 시간 복잡도는 $O(NK)$이다.
방법2: 불필요한 연산 줄이기 (슬라이딩 윈도우)
방법1의 방법을 표로 나타내면 아래와 같다.
$i = 0$에서 $i = 1$로 갈 때, 식에서 $a[0]$이 사라지고 $a[k+1]$이 추가되었다.
마찬가지로, $i$가 1씩 증가할 때마다 맨 앞의 숫자가 하나 사라지고 맨 뒤에 원소가 숫자가 하나 추가된다.
이는 이 두 숫자를 제외한 원소들의 합은 앞에서 이미 계산했음에도 또 다시 계산이 이루어지고 있다는 것을 의미한다.
위의 표에서도 한 원소가 여러 번 계산되고 있는 것을 확인할 수 있다.
앞에서 구한 합을 재활용하기
앞에서 구한 합을 재활용하는 방식으로 표를 다시 만들어보자.
$i$가 증가할 때마다 모든 값을 계산하는 것이 아니라 앞선 결과에서 사라지는 원소를 빼고 추가되는 원소만 더해주는 방식이다.
이렇게 하면 $i$가 증가할 때마다 해야 하는 연산을 상수 시간만에 수행할 수 있으므로 시간 복잡도가 $O(N)$으로 줄어든다.
슬라이딩 윈도우?
지금까지 이야기한 방식으로 $K=3$일 때의 상황을 새로운 그림으로 표현해보자.
회색이 테두리가 앞에서 말한 사라지는 원소이고, 주황색 테두리가 추가되는 원소이다.
위 그림처럼, 고정된 사이즈의 윈도우를 이동시키면서 문제를 해결해나가는 알고리즘을 슬라이딩 윈도우라고 부른다.
(윈도우의 크기를 고정시키지 않는 경우도 있는데, 이는 투 포인터 알고리즘이라고 부른다.)
구현해보기(코드)
now = answer = sum(a[:K])
for i in range(K, N):
now = now - a[i - K] + a[i]
answer = max(answer, now)
print(answer)
$i=0$인 경우의 합을 계산해둔 뒤, 이 값과 슬라이딩 윈도우 알고리즘을 이용해 문제를 $O(N)$의 시간 복잡도로 해결해였다.
구간 합이 아닌 최댓값/최솟값을 구하려면? (Monotone Queue Optimization)
구간 합이 아닌 최댓값/최솟값을 구할 때도 슬라이딩 알고리즘을 쓸 수 있을까?
구간 합과는 달리, 최댓값/최솟값의 경우 이전 연산과의 식을 세우기 어려우며, 그렇다고 해서 매 구간마다의 최댓값/최솟값을 구해버리면 $O(NK)$의 시간이 걸린다.
이 경우 모노톤 큐(Monotone Queue)를 사용하면 $O(N)$만에 처리할 수 있다.
모노톤 큐?
모노톤 큐(혹은 단조 큐)는 내부 원소들이 단조(Monotonic) 증가/감소 상태를 유지하는 큐(또는 덱)를 의미한다.
모노톤 큐를 이용한 구간 최댓값은 아래와 같은 방식으로 구할 수 있다.
- 큐의 맨 뒤 원소를 확인하면서 유효하지 않은(앞으로 영향력을 미칠 수 없는) 값들을 pop한다.
(이 과정을 통해 큐는 단조 감소 상태가 유지된다.) - 큐의 맨 뒤에 새로 추가할 원소를 추가한다.
- 큐의 맨 앞 원소를 확인하면서 범위에 해당하지 않는 값들을 pop한다.
- 1 ~ 3 과정을 끝낸 큐의 맨 앞 원소가 구간 최댓값이다.
이제 다음 구간(윈도우)에서 1 과정부터 다시 진행한다.
예시
$[1, 8, 4, 6, -3, 9]$에서 크기가 3인 각 구간의 최댓값을 구해보자.
먼저 맨 처음 원소인 1을 모노톤 큐에 추가한다.
이 때, 3번 과정(범위에 해당되는지 확인)을 위해 원소의 인덱스 값도 함께 큐에 넣어주어여 한다.
즉, 모노톤 큐는 [(1, 0)]인 상태가 된다.
다음 원소는 8이며, 모노톤 큐의 맨 뒤부터 탐색하면서 앞으로 영향력을 미칠 수 없는 값들을 pop한다.
현재는 구간 최댓값을 구하고 있으므로, 현재 원소(8)보다 작거나 같은 값들을 pop해주어야 한다.
현재 원소보다 앞에 있으면서 8보다 작은 값들은 앞으로 절대 구간 최댓값이 될 수 없기 때문이다.
따라서 모노톤 큐의 상태는 [(8, 1)]로 바뀐다.
다음 원소 4는 8보다 작으므로 [(8, 1), (4, 2)]가 된다. 따라서 $a[0]$ ~ $a[2]$ 구간의 최댓값은 8이다.
그 다음 원소 6은 4보다 크고 8보다 작으므로 [(8, 1), (6, 3)]이 된다. 따라서 $a[1]$ ~ $a[3]$ 구간의 최댓값은 8이다.
다음 원소 -3이 들어가면 모노톤 큐는 [(8, 1), (6, 3), (-3, 4)]가 된다.
이때, 큐의 맨 앞 원소는 인덱스 1의 숫자이므로 구간 범위 밖의 숫자이다. ($4 - 1 \geq 3$)
따라서 (8, 1)이 빠져 [(6, 3), (-3, 4)]가 되므로 $a[2]$ ~ $a[4]$ 구간의 최댓값은 6이다.
마지막 원소 9는 모노톤 큐의 다른 숫자들보다 크므로 [(9, 5)]가 되며, 따라서 $a[3]$ ~ $a[5]$ 구간의 최댓값은 9이다.
구현해보기(코드)
collections의 deque을 사용하여 코드를 작성하였다.
from collections import deque
dq = deque()
for i in range(N):
while dq and dq[-1][0] <= a[i]: dq.pop() # 앞으로 영향을 미치지 못하는 값 제거
dq.append((a[i], i)) # 값 추가
while dq[0][1] <= i - K: dq.popleft() # 범위 밖의 값 제거
if i >= K - 1:
print(f"a[{i-K+1}]부터 a[{i}]까지의 최댓값은 {dq[0][0]}")
모노톤 큐는 슬라이딩 윈도우 말고도 DP 최적화 등에 사용할 수 있는 자료구조이니 알아두면 좋다.
관련 문제 (BOJ)
- [2559] 수열: 슬라이딩 윈도우로 구간 합을 구하는 기본적인 문제
- [15961] 회전 초밥: 슬라이딩 윈도우로 이런 것도 할 수 있다!
- [3988] 수 고르기: 모노톤 큐 최적화를 활용한 슬라이딩 윈도우 (이 문제는 다양한 풀이가 가능하다.)
