이 문제에서는 크기가 n인 배열 arr[]가 주어집니다. 우리의 과제는 주어진 배열에서 모든 윈도우(window) 크기에 대해 최솟값들 중 최댓값을 찾는 것입니다.
문제 설명
윈도우 크기가 1부터 n까지 변할 때, 각 윈도우 크기마다 해당하는 부분 배열(subarray)들을 고려하고, 각 부분 배열의 최솟값을 구한 뒤, 그 최솟값들 중 최댓값을 계산해야 합니다.
입력 예제
arr[] = {4, 1, 2, 4, 5, 1, 2, 4}출력 예제
5 4 2 1 1 1 1 1
설명
윈도우 크기 :
1 => 윈도우 { (4), (1), (2), (4), (5), (1), (2), (4) } => 최솟값 = {4, 1, 2, 4, 5, 1, 2, 4} => 최솟값들의 최댓값 = 5
2 => 윈도우 { (4, 1), (1, 2), (2, 4), (4, 5), (5, 1), (1, 2), (2, 4) } => 최솟값 = {1, 1, 2, 4, 1, 1, 2} => 최솟값들의 최댓값 = 4
3 => 윈도우 { (4, 1, 2), (1, 2, 4), (2, 4, 5), (4, 5, 1), (5, 1, 2), (1, 2, 4) } => 최솟값 = {1, 1, 2, 1, 1, 1} => 최솟값들의 최댓값 = 2
4 => 윈도우 { (4, 1, 2, 4), (1, 2, 4, 5), (2, 4, 5, 1), (4, 5, 1, 2), (5, 1, 2, 4) } => 최솟값 = {1, 1, 1, 1, 1} => 최솟값들의 최댓값 = 1
5 => 윈도우 { (4, 1, 2, 4, 5), (1, 2, 4, 5, 1), (2, 4, 5, 1, 2), (4, 5, 1, 2, 4) } => 최솟값 = {1, 1, 1, 1} => 최솟값들의 최댓값 = 1
6 => 윈도우 { (4, 1, 2, 4, 5, 1), (1, 2, 4, 5, 1, 2), (2, 4, 5, 1, 2, 4) } => 최솟값 = {1, 1, 1} => 최솟값들의 최댓값 = 1
7 => 윈도우 { (4, 1, 2, 4, 5, 1, 2), (1, 2, 4, 5, 1, 2, 4) } => 최솟값 = {1, 1} => 최솟값들의 최댓값 = 1
8 => 윈도우 { (4, 1, 2, 4, 5, 1, 2, 4) } => 최솟값 = {1} => 최솟값들의 최댓값 = 1해결 접근 방법
가장 단순한 해결 방법은 크기 1부터 n까지의 모든 윈도우를 만드는 것입니다. 각 윈도우 크기에 대해 해당 길이의 모든 부분 배열을 탐색하고, 각 부분 배열의 최솟값을 구한 후, 그 최솟값들 중 최댓값을 결과로 반환합니다.
각 윈도우 크기 반복이 끝날 때마다 해당 크기에 대한 최솟값들의 최댓값을 출력하면 됩니다.
이 솔루션의 동작을 보여주는 프로그램입니다.
예제
#include <iostream>
using namespace std;
void printMaxMinWindowK(int arr[], int n, int k) {
int maxMin = -1;
int minEle = -1;
for (int i = 0; i <= n-k; i++) {
minEle = arr[i];
for (int j = 1; j < k; j++) {
if (arr[i+j] < minEle)
minEle = arr[i+j];
}
if (minEle > maxMin)
maxMin = minEle;
}
cout<<maxMin<<endl;
}
int main() {
int arr[] = {4, 1, 2, 4, 5, 1, 2, 4};
int n = sizeof(arr)/sizeof(arr[0]);
for(int i = 1; i <= n; i++){
cout<<"윈도우 크기 :"<<i<<", 최솟값의 최댓값 : ";
printMaxMinWindowK(arr, n, i);
}
return 0;
}출력
윈도우 크기 : 1, 최솟값의 최댓값 : 5 윈도우 크기 : 2, 최솟값의 최댓값 : 4 윈도우 크기 : 3, 최솟값의 최댓값 : 2 윈도우 크기 : 4, 최솟값의 최댓값 : 1 윈도우 크기 : 5, 최솟값의 최댓값 : 1 윈도우 크기 : 6, 최솟값의 최댓값 : 1 윈도우 크기 : 7, 최솟값의 최댓값 : 1 윈도우 크기 : 8, 최솟값의 최댓값 : 1
이 방법은 시간 복잡도가 O(n²) 이상으로 비효율적일 수 있습니다. 따라서 더 효율적인 대안을 살펴보겠습니다.
대체 솔루션 (효율적인 접근)
추가 메모리 공간과 보조 배열(auxiliary array)을 활용하면 더 효율적으로 문제를 해결할 수 있습니다. 현재 원소보다 왼쪽에 있는 더 작은 원소의 위치를 저장하는 배열과, 오른쪽에 있는 더 작은 원소의 위치를 저장하는 배열을 사용합니다.
이 두 배열을 이용하면 인덱스 i의 원소 arr[i]가 길이 "right[i] - left[i] + 1"짜리 윈도우의 최솟값임을 알 수 있습니다. 이 정보를 바탕으로 각 윈도우 크기별 최솟값들의 최댓값을 효율적으로 계산할 수 있으며, 전체 시간 복잡도는 O(n)입니다.
이 솔루션의 동작을 보여주는 프로그램입니다.
예제
#include <iostream>
#include<stack>
using namespace std;
void printMaxMinWindow(int arr[], int n) {
stack<int> s;
int prev[n+1];
int next[n+1];
for (int i=0; i<n; i++) {
prev[i] = -1;
next[i] = n;
}
for (int i=0; i<n; i++) {
while (!s.empty() && arr[s.top()] >= arr[i])
s.pop();
if (!s.empty())
prev[i] = s.top();
s.push(i);
}
while (!s.empty())
s.pop();
for (int i = n-1 ; i>=0 ; i-- ) {
while (!s.empty() && arr[s.top()] >= arr[i])
s.pop();
if(!s.empty())
next[i] = s.top();
s.push(i);
}
int maxOfMin[n+1];
for (int i=0; i<=n; i++)
maxOfMin[i] = 0;
for (int i=0; i<n; i++) {
int len = next[i] - prev[i] - 1;
maxOfMin[len] = max(maxOfMin[len], arr[i]);
}
for (int i=n-1; i>=1; i--)
maxOfMin[i] = max(maxOfMin[i], maxOfMin[i+1]);
for (int i=1; i<=n; i++)
cout<<"윈도우 크기: "<<i<<", 최솟값의 최댓값 : "<<maxOfMin[i]<<endl;
}
int main() {
int arr[] = {4, 1, 2, 4, 5, 1, 2, 4};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxMinWindow(arr, n);
return 0;
}출력
윈도우 크기: 1, 최솟값의 최댓값 : 5 윈도우 크기: 2, 최솟값의 최댓값 : 4 윈도우 크기: 3, 최솟값의 최댓값 : 2 윈도우 크기: 4, 최솟값의 최댓값 : 1 윈도우 크기: 5, 최솟값의 최댓값 : 1 윈도우 크기: 6, 최솟값의 최댓값 : 1 윈도우 크기: 7, 최솟값의 최댓값 : 1 윈도우 크기: 8, 최솟값의 최댓값 : 1
정리
브루트 포스 방식은 구현이 직관적이지만 입력 크기가 커지면 성능이 급격히 저하됩니다. 반면 스택을 활용한 '이전/다음 작은 원소' 기법은 선형 시간 안에 정답을 구할 수 있어 실전에서 훨씬 유용합니다. 두 접근 방식을 모두 이해해두면 다양한 슬라이딩 윈도우 문제를 해결하는 데 큰 도움이 됩니다.