백준 1725 히스토그램, 2104 부분배열 고르기

www.acmicpc.net/problem/1725

1725번: 히스토그램

www.acmicpc.net/problem/2104

2104번: 부분배열 고르기

대단히 유명하고 필수적인 문제들이다. 두 문제는 매우 유사하여 함께 풀이하겠다.

분할 정복과 스택을 활용한 풀이가 있다고 알려져 있는데 스택을 활용한 풀이만 설명하겠다. 이 문제의 풀이를 통해 스택의 순기능을 깨닫고 어떻게 스택을 제대로 활용하는지 알 수 있다.

분할 정복 코드도 아래에서 찾을 수 있다. (분할 정복을 이용해서 푸는 게 오히려 더 어려웠다.) 두 문제가 정말로 비슷한데 2104 (부분배열 고르기)를 기준으로 먼저 풀이를 소개하고 이를 1725에 똑같이 적용하겠다. 

 

아래의 그림을 보자.

3, 5 ,2 라는 값이 입력으로 주어졌을 때, 최대의 점수를 갖기 위해서는 면적이 가장 넓은 직사각형을 찾아야 한다. 이제 바로 느낌이 올 것이다. 이 문제는 히스토그램과 매우 유사하다는 것을. 조금 더 덧붙이면 히스토그램은 각 박스의 밑변이 모두 1인 직사각형이고, 이 문제는 항상 정사각형이다. 

위의 그림을 잘 관찰한다면, 높이를 3으로 하는 직사각형은 최대 5까지 뻗을 수 있고, 높이가 5인 직사각형은 자기 자신 하나만 부분 배열에 포함 가능하다. 높이가 2인 직사각형은 전 범위를 모두 아우를 수 있다. 효율성을 따지지 않고 모든 경우의 수를 전부 따진다면, 입력값을 [3, 5, 2]로 배열 저장하고, 이 중에 원소를 하나씩 취하면서 앞뒤로 확장할 수 있는 만큼 최대한 확장하며, 매번 최대 점수를 갱신하는 것일 것이다. 당연히 O(n^2)의 시간복잡도를 갖게 되고, 시간 내에 문제를 해결할 수 없다. 단순히 문제를 시간 내에 풀기 위해서 이런 방법을 피하는 것이 아니다. 이 안에는 너무나 많은 연산과 불필요한 연산들이 모두 포함되어 있기 때문이다. 

 

그렇다면 어떻게 해야 할까? 높이가 낮을 수록 넓은 범위로 직사각형 확장이 가능하다는 점에 착안해야 한다. 그렇다면 그 박스(높이가 낮은)는 어디까지 확장해야 하는 걸까? 매번 확장하며 최댓값을 갱신할 수는 없다. 대신에 자료구조 스택을 활용하여, 박스를 오름차순으로 쌓아두는 것이다. 즉, 직사각형의 넓이 계산을 나중으로 미루는 것이다. 스택의 최상단보다 새로 들어오는 박스의 높이가 높다면, 스택 위에 쌓고, 높이가 낮다면 자신보다 작은 박스가 나올 때까지 pop 하는 것이다. 이렇게 하면 스택은 항상 오름차순의 형태를 갖게 된다. 참고로 이를 모노톤 스택(monotone stack)이라고 하며, 오름차순 또는 내림차순의 한가지 방향을 갖는 자료구조이다. 이는 매우 중요하기에 다른 포스팅에서 따로 모아 다루도록 하겠다. (모노톤 스택, 큐, 덱 등 다양하다)

위의 그림과 같이 3이 오면 스택에 아무것도 없으니 쌓고, 5가 들어오면 3보다 크니 또 쌓는다. 나중에 pop 하면서 밑변 값을 중첩하여(3+5) 직사각형의 넓이를 계산할 기회가 온다. (계산을 나중으로 미루는 것이다! 어차피 모노톤이므로 나중에 한꺼번에 계산가능한 것이다) 이제 마지막으로 2가 들어오면, 2는 5보다 작으므로 5를 pop해야 한다. 이제 5에서 2로 확장이 불가하므로, 5 하나만 선택되었을 때의 직사각형 넓이를 계산한다. 5 곱하기 5는 25가 되어 최대 점수를 갱신한다. 스택은 모노톤이므로, 현재 스택상에서 가장 큰 박스는 5이다. 그래서 사실상 3 곱하기 3으로 3 박스의 넓이 계산은 할 필요가 없는 것이다. 5를 pop 하면서 밑변 값에 5를 넣어둔다. 

이제 아래의 그림을 보자.

5가 빠지고 3이 남았는데 3도 2보다 작아서 pop해야 하는 상황이다. 이전 단계에서 밑변에 5가 저장되어있었으므로 자신의 값을 중첩하여 밑변이 3+5=8이 되고 거기에 자신의 높이를 곱하여 8x3=24 가 된다. 그리고 최대 점수와 비교하여 갱신한다. (여기서는 최대 점수가 현재 25이므로 갱신되진 않는다). 이제 2를 스택에 담을 때, 밑변을 모두 중첩하여 2+3+5=10을 기록해두는 것이다. 이렇게 해야 이번 예시에서는 3,5,2 뿐이지만 2 뒤에 2보다 더 큰 값이 들어오더라도 2를 높이로 갖는 직사각형이 전 범위를 포함했을 때의 최대 점수를 따질 수 있게 된다.

위의 그림에서 보다시피 3,5,2를 사용해 만들 수 있는 직사각형은 총 6개가 있는데, X표시로 되어있는 경우는 계산조차 되지 않았다. 불필요한 계산들은 아예 하지 않은 것이다. 3,5가 5,2보다 더 큰 점수를 갖기에 3,5가 계산되었고 3이 pop 되었다. 그리고 5가 가장 크기에 2만 선택된 경우, 3만 선택된 경우도 아예 고려하지 않는다. 

 

결국 문제 해결을 위한 절차는 다음과 같이 정리할 수 있다.

• 높이의 오름차순으로 스택에 담기
• 작은 값이 나오면 pop하면서 계산을 하고, 밑변은 스택에 남은 값에 물려주기
• 마지막까지 스택에 남은 값을 모두 pop 하여 계산

최대한 자세하게 설명을 남기려고 하였지만 부족함은 있다. 하지만 핵심 아이디어는 담았다고 생각한다.

1725 히스토그램도 똑같은 방식으로 해결한다. 위에서 언급하였듯이, 밑변의 길이가 1인 직사각형이라고 생각하면 된다. 

 

<주요 내용>

모노톤 스택 (monotone stack), 스택 (stack), 레이지 개념 (계산을 미뤄두는), 부분 배열의 시각화 (직사각형의 넓이)

 

<코드>

 

2104 부분배열 고르기 (스택 활용 풀이)

#include <iostream>
#include <stack>
#define endl '\n'
using namespace std;
typedef long long ll;

ll s,temp,v;
int n;
// first: length of a cell, second: stacked length
stack<pair<int,ll>>st;

int main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>v;
        temp=0;
        while(!st.empty() && v<st.top().first){
            temp+=st.top().second;
            s=max(s,temp*st.top().first);
            st.pop();
        }
        temp+=v;
        st.emplace(v,temp);
    }
    temp=0;
    while(!st.empty()){
        temp+=st.top().second;
        s=max(s,temp*st.top().first);
        st.pop();
    }
    cout<<s<<endl;
    return 0;
}

 

2104 부분배열 고르기 (분할 정복 풀이)

#include <iostream>
using namespace std;
#define ll long long

const int nMax = 100000;
int n, arr[nMax];
ll DnC(int s, int e)
{
    int l, r, height;
    ll base;
    if (s == e)
        return (ll)arr[s] * arr[s];
    int mid = (s + e) / 2;
    ll m = max(DnC(s, mid), DnC(mid + 1, e));

    l = mid;
    r = mid + 1;
    base = arr[l] + arr[r];
    height = min(arr[l], arr[r]);
    m = max(m, base * height);

    while (!(l == s && r == e))
    {
        if (r < e && (l == s || arr[l - 1] < arr[r + 1]))
        {
            base += arr[++r];
            height = min(height, arr[r]);
        }
        else
        {
            base += arr[--l];
            height = min(height, arr[l]);
        }
        m = max(m, base * height);
    }
    return m;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cout << DnC(0, n - 1) << '\n';
    return 0;
}

 

1725 히스토그램 (스택 활용 풀이)

#include <iostream>
#include <stack>
#define endl '\n'
using namespace std;
stack<pair<int,int>>st;
int s,n,a,temp;

int main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);
    
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a;
        temp=0;
        while(!st.empty() && a<st.top().first){
            temp+=st.top().second;
            s=max(s,temp*st.top().first);
            st.pop();
        }
        temp++;
        st.emplace(a,temp);
    }
    temp=0;
    while(!st.empty()){
        temp+=st.top().second;
        s=max(s,temp*st.top().first);
        st.pop();
    }
    cout<<s<<endl;
    return 0;
}

 

1725 히스토그램 (분할 정복 풀이)

#include <iostream>
using namespace std;
#define ll long long

const int nMax = 100000;
ll m, n, arr[nMax];
ll DnC(ll s, ll e)
{
    ll l, r, m, mid, b, h;
    if (s == e)
        return arr[s];
    mid = (s + e) / 2;
    m = max(DnC(s, mid), DnC(mid + 1, e));

    l = mid;
    r = mid + 1;
    b = 2;
    h = min(arr[l], arr[r]);
    m = max(m, b * h);

    while (!(l == s && r == e))
    {
        if (r < e && (l == s || arr[l - 1] < arr[r + 1]))
        {
            b++;
            h = min(h, arr[++r]);
        }
        else
        {
            b++;
            h = min(h, arr[--l]);
        }
        m = max(m, b * h);
    }
    return m;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    m = DnC(0, n - 1);
    cout << m << '\n';
    return 0;
}