최소 스택 / 최소 큐¶

이 글에서는 세 가지 문제를 다룹니다. 먼저 스택에서 가장 작은 원소를 $O(1)$에 찾을 수 있도록 스택을 변형하고, 이어서 큐에 대해서도 같은 작업을 수행하며, 마지막으로 이 자료 구조들을 사용하여 배열에서 고정된 길이의 모든 부분 배열의 최솟값을 $O(n)$에 찾습니다.

스택 변형¶

스택에 원소를 추가하고 제거하는 연산의 점근적 동작은 그대로 유지하면서, 스택에서 가장 작은 원소를 $O(1)$ 시간에 찾을 수 있도록 스택 자료 구조를 변형하려고 합니다. 간단히 상기하자면, 스택에서는 한쪽 끝에서만 원소를 추가하고 제거합니다.

이를 위해 스택에 원소만 저장하는 것이 아니라 쌍으로 저장합니다. 즉, 원소 자체와 그 원소부터 그 아래에 있는 스택 원소들 중의 최솟값을 함께 저장합니다.

stack<pair<int, int>> st;

스택 전체의 최솟값을 찾으려면 stack.top().second 값만 확인하면 된다는 것은 자명합니다.

스택에 새 원소를 추가하거나 제거하는 연산을 상수 시간에 수행할 수 있다는 것 또한 자명합니다.

구현:

원소 추가:

int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
st.push({new_elem, new_min});

원소 제거:

int removed_element = st.top().first;
st.pop();

최솟값 찾기:
```
int minimum = st.top().second;
```

큐 변형 (방법 1)¶

이제 큐에서도 같은 연산을 구현하려고 합니다. 즉, 원소를 끝에 추가하고 앞에서 제거하려고 합니다.

여기서는 큐를 변형하는 간단한 방법을 살펴봅니다. 다만 이 방법에는 큰 단점이 있는데, 변형된 큐가 실제로는 모든 원소를 저장하지 않기 때문입니다.

핵심 아이디어는 최솟값을 결정하는 데 필요한 항목만 큐에 저장하는 것입니다. 즉, 큐를 비내림차순으로 유지하며(다시 말해 가장 작은 값이 맨 앞에 저장됩니다), 물론 아무렇게나 유지하는 것이 아니라 실제 최솟값이 항상 큐에 포함되어 있어야 합니다. 이렇게 하면 가장 작은 원소가 항상 큐의 맨 앞에 위치합니다. 큐에 새 원소를 추가하기 전에 "잘라내기"만 하면 충분합니다. 즉, 큐의 뒤쪽에서 새 원소보다 큰 원소를 모두 제거한 다음 새 원소를 큐에 추가합니다. 이렇게 하면 큐의 순서가 깨지지 않으며, 현재 원소가 이후 어느 단계에서 최솟값이 되더라도 그 원소를 잃지 않습니다. 제거한 원소들은 그 자체로 결코 최솟값이 될 수 없으므로 이 연산은 허용됩니다. 맨 앞에서 원소를 꺼내려 할 때 그 원소가 실제로는 없을 수도 있습니다(더 작은 원소를 추가하면서 앞서 제거했기 때문입니다). 따라서 큐에서 원소를 삭제할 때는 그 원소의 값을 알아야 합니다. 큐의 맨 앞 원소가 같은 값을 가지고 있으면 안전하게 제거할 수 있고, 그렇지 않으면 아무것도 하지 않습니다.

위 연산들의 구현을 살펴봅시다:

deque<int> q;

최솟값 찾기:
```
int minimum = q.front();
```

원소 추가:

while (!q.empty() && q.back() > new_element)
    q.pop_back();
q.push_back(new_element);

원소 제거:

if (!q.empty() && q.front() == remove_element)
    q.pop_front();

이 모든 연산이 평균적으로 $O(1)$ 시간만 걸린다는 것은 자명합니다(모든 원소는 한 번만 추가되고 한 번만 제거될 수 있기 때문입니다).

큐 변형 (방법 2)¶

이것은 방법 1을 변형한 것입니다. 어떤 원소를 제거해야 하는지 모르는 상태에서도 원소를 제거할 수 있기를 원합니다. 이는 큐에 각 원소의 인덱스를 함께 저장하면 가능합니다. 또한 지금까지 추가한 원소와 제거한 원소의 개수도 기억해 둡니다.

deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;

최솟값 찾기:
```
int minimum = q.front().first;
```

원소 추가:

while (!q.empty() && q.back().first > new_element)
    q.pop_back();
q.push_back({new_element, cnt_added});
cnt_added++;

원소 제거:

if (!q.empty() && q.front().second == cnt_removed) 
    q.pop_front();
cnt_removed++;

큐 변형 (방법 3)¶

여기서는 $O(1)$에 최솟값을 찾도록 큐를 변형하는 또 다른 방법을 살펴봅니다. 이 방법은 구현이 다소 더 복잡하지만, 이번에는 실제로 모든 원소를 저장합니다. 또한 맨 앞의 원소를 그 값을 모르더라도 제거할 수 있습니다.

핵심 아이디어는 이 문제를 이미 해결한 스택 문제로 환원하는 것입니다. 따라서 두 개의 스택으로 큐를 흉내 내는 방법만 익히면 됩니다.

두 개의 스택 s1과 s2를 만듭니다. 물론 이 스택들은 $O(1)$에 최솟값을 찾을 수 있도록 변형된 형태입니다. 새 원소는 스택 s1에 추가하고, 원소 제거는 스택 s2에서 합니다. 어느 시점이든 스택 s2가 비어 있으면 s1의 모든 원소를 s2로 옮깁니다(이렇게 하면 사실상 그 원소들의 순서가 뒤집힙니다). 마지막으로 큐의 최솟값을 찾으려면 두 스택의 최솟값을 구하기만 하면 됩니다.

따라서 모든 연산을 평균 $O(1)$에 수행합니다(각 원소는 스택 s1에 한 번 추가되고, s2로 한 번 옮겨지며, s2에서 한 번 꺼내집니다)

구현:

stack<pair<int, int>> s1, s2;

최솟값 찾기:

if (s1.empty() || s2.empty()) 
    minimum = s1.empty() ? s2.top().second : s1.top().second;
else
    minimum = min(s1.top().second, s2.top().second);

원소 추가:

int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
s1.push({new_element, minimum});

원소 제거:

if (s2.empty()) {
    while (!s1.empty()) {
        int element = s1.top().first;
        s1.pop();
        int minimum = s2.empty() ? element : min(element, s2.top().second);
        s2.push({element, minimum});
    }
}
int remove_element = s2.top().first;
s2.pop();

고정 길이의 모든 부분 배열에서 최솟값 찾기¶

길이가 $N$인 배열 $A$와 $M \le N$이 주어졌다고 가정합시다. 이 배열에서 길이가 $M$인 각 부분 배열의 최솟값을 찾아야 합니다. 즉, 다음을 구해야 합니다:

$$\min_{0 \le i \le M-1} A[i], \min_{1 \le i \le M} A[i], \min_{2 \le i \le M+1} A[i],~\dots~, \min_{N-M \le i \le N-1} A[i]$$

이 문제를 선형 시간, 즉 $O(n)$에 해결해야 합니다.

이 문제를 해결하는 데에는 세 가지 변형 큐 중 어느 것을 사용해도 됩니다. 풀이는 명확합니다. 배열의 처음 $M$개 원소를 추가하고 그 최솟값을 찾아 출력한 뒤, 다음 원소를 큐에 추가하고 배열의 첫 번째 원소를 제거한 다음 다시 최솟값을 찾아 출력하는 식으로 계속합니다. 큐의 모든 연산은 평균적으로 상수 시간에 수행되므로, 전체 알고리즘의 복잡도는 $O(n)$입니다.

최소 스택 / 최소 큐¶

스택 변형¶

큐 변형 (방법 1)¶

큐 변형 (방법 2)¶

큐 변형 (방법 3)¶

고정 길이의 모든 부분 배열에서 최솟값 찾기¶

연습 문제¶