본문 바로가기
카테고리 없음

🐨BOJ#6549 히스토그램에서 가장 큰 직사각형] 모노톤 스택(#1725히스토그램)

by redcubes 2024. 4. 10.

히스토그램에서 가장 큰 직사각형 

시간 제한 메모리 제한 제출 정답  맞힌 사람  정답 비율
1 초 256 MB 54258 14782 9717 26.945%

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 $n$이 가장 처음으로 주어진다. $(1 ≤ n ≤ 100,000)$ 그 다음 $n$개의 정수 $h_1, ..., h_n (0 ≤ h_i ≤ 1,000,000,000)$가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

예제 입력 1 

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

예제 출력 1 

8
4000

문제의 이해

오른쪽과 같은 여러 사각형 중 넓이가 최대인 것을 찾으라는 문제.

구간을 정하고 구간의 최소값을 구해서 곱하면 사각형의 넓이가 나온다.

$n$개의 원소를 가진 리스트에서

  • 첫 번째 원소를 시작점으로 하는 연속 구간의 개수는 $n$
  • 두 번째 원소를 시작점으로 하는 연속 구간의 개수는 $(n-1)$
  • 세 번째 원소를 시작점으로 하는 연속 구간의 개수는 $(n-2)$
  • 마지막 원소를 시작점으로 하는 연속 구간의 개수는 $(1)$

따라서, 만들 수 있는 연속 구간의 총 개수는 $1 + 2 + 3 + \cdots + (n-1) + n$
$$\frac{n(n + 1)}{2}$$

그런데, $n$개의정수$h1,...,hn(0≤hi≤1,000,000,000)$이므로 $O(n^2)$에서 1초 안에 풀 수 없다.


모노톤 스택과 모노톤 큐 알고리즘

모노톤 스택

모노톤 스택(Monotonic Stack)은 스택을 활용하는 데이터 구조 중 하나로, 스택 내의 원소들이 단조 증가 또는 단조 감소하는 순서를 유지하도록 구성된 스택이다. 특정 조건을 만족하는 원소들의 관계를 효율적으로 처리할 수 있으며, 특히 배열과 같은 선형 구조에서 연속적인 부분 구조의 최대값이나 최소값을 찾는 문제에 유용하게 사용됩니다.

모노톤 스택은 크게 두 가지 유형으로 나뉩니다:

  1. 단조 증가 스택(Monotonically Increasing Stack): 스택의 바닥부터 꼭대기까지 원소가 증가하는 순서를 유지합니다. 이 스택은 주로 ‘다음으로 큰 원소’를 찾는 문제에 사용됩니다.
  2. 단조 감소 스택(Monotonically Decreasing Stack): 스택의 바닥부터 꼭대기까지 원소가 감소하는 순서를 유지합니다. 이 스택은 주로 ‘다음으로 작은 원소’를 찾는 문제에 사용됩니다.

작동 방식

모노톤 스택의 핵심 아이디어는 배열을 순회하면서, 현재 원소가 스택의 정렬 조건(증가 혹은 감소)에 따라 스택의 최상위 원소와 비교될 때까지 스택에서 원소를 제거하는 것. 이 과정에서 각 원소에 대해 특정 조건(예: 다음으로 큰 원소 또는 다음으로 작은 원소)을 만족하는 원소를 효율적으로 찾을 수 있습니다.

장점

배열이나 리스트와 같은 선형 데이터를 한 번만 순회하면서 필요한 계산을 수행할 수 있기 때문에, 시간 복잡도 측면에서 매우 효율적(대부분의 경우 $O(n)$)

모노톤 스택을 활용함으로써 복잡한 문제를 간결하고 효율적으로 해결할 수 있는 강력한 도구입니다.

모노톤 스택 활용 예제: 다음 더 큰 원소 찾기

다음 Python 코드는 모노톤 스택을 사용하여 배열에서 각 원소 다음에 오는 더 큰 원소를 찾는 방법을 보여준다.

def next_greater_element(nums):
    ans = [-1] * len(nums)
    stack = []
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            ans[stack.pop()] = num
        stack.append(i)
    return ans

nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums))

이 코드는 각 원소에 대해, 그 원소보다 더 큰 ‘다음’ 원소를 찾아 결과 리스트에 저장한다. 원소가 스택에 들어가는 것은 그 원소가 '다음 더 큰 원소’를 찾지 못했음을 의미하며, 더 큰 원소를 만나면 스택에서 원소를 꺼내 그 위치에 해당 더 큰 원소를 기록한다.

모노톤 큐

모노톤 큐는 큐 내의 원소가 증가하거나 감소하는 순서를 유지하는 큐이다. 이는 주로 슬라이딩 윈도우 문제와 같이, 연속적인 원소들의 집합에서 최대값이나 최소값을 효율적으로 찾는 데 사용된다.

모노톤 큐 활용 예제: 슬라이딩 윈도우 최대값 찾기

다음 Python 코드는 모노톤 큐를 사용하여 슬라이딩 윈도우 내의 최대값을 찾는 방법을 보여준다.

from collections import deque

def max_sliding_window(nums, k):
    q = deque()
    ans = []
    for i, num in enumerate(nums):
        while q and nums[q[-1]] < num:
            q.pop()
        q.append(i)
        if q[0] == i - k:
            q.popleft()
        if i >= k - 1:
            ans.append(nums[q[0]])
    return ans

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))

이 코드는 각 슬라이딩 윈도우 위치에 대해 최대값을 찾아 결과 리스트에 저장한다. 원소가 큐에 들어가는 것은 그 원소가 현재 고려 중인 윈도우에서 최대값 후보임을 의미한다. 윈도우가 이동할 때, 더 이상 윈도우에 포함되지 않는 원소는 큐에서 제거된다.


히스토그램에서 가장 큰 직사각형 찾기: 모노톤 스택 방법

히스토그램의 높이가 [2, 1, 5, 6, 2, 3]일 때, 가장 큰 직사각형을 찾는 과정(모노톤 스택 사용)

문제 해결 아이디어

  1. 순차적으로 탐색: 히스토그램의 막대를 왼쪽에서 오른쪽으로 순차적으로 탐색합니다.
  2. 스택 사용 이유: 막대 A의 오른쪽에 A보다 낮은 막대 B가 나타나면, A와 A의 왼쪽에 있는 A보다 높은 모든 막대들은 B까지만 넓은 직사각형을 만들 수 있습니다.
  3. 모노톤 스택의 역할: 현재 막대보다 높이가 낮은 막대를 스택에서 꺼내면서, 꺼낸 막대를 기준으로 직사각형의 최대 면적을 계산합니다.
  4. 계산: 스택에서 막대를 꺼낼 때, 해당 막대의 높이와 꺼내진 위치 사이의 거리를 곱하여 면적을 계산합니다.

이 과정을 통해 모든 막대에 대한 최대 직사각형의 면적을 계산하고, 가장 큰 면적을 찾아내면 문제가 해결됩니다. 이 방법은 히스토그램을 한 번만 탐색하면서 막대들 사이의 관계를 효과적으로 활용합니다.

과정

  1.  초기 상태: 스택은 비어 있으며, 막대들을 왼쪽에서 오른쪽으로 순회한다.
  2.  첫 번째 막대(높이=2): 스택이 비어 있으므로, 인덱스 0이 스택에 푸시된다.
    • 스택: [0]
  3.  두 번째 막대(높이=1): 현재 막대의 높이가 스택의 최상단 막대의 높이보다 작다.
    • 막대 0이 스택에서 팝되고, 높이 2의 직사각형의 면적이 계산된다(면적=2). 인덱스 1이 스택에 푸시된다.
    • 스택: [1]
  4.  세 번째 막대(높이=5)네 번째 막대(높이=6): 각각 스택에 푸시된다.
    • 스택: [1, 2, 3]
  5.  다섯 번째 막대(높이=2): 스택의 최상단 막대의 높이보다 작다.
    • 막대 3이 팝되고, 높이 6의 직사각형 면적이 계산된다(면적=6). 막대 2가 팝되고, 높이 5의 직사각형 면적이 계산된다(면적=10). 인덱스 4가 스택에 푸시된다.
    • 스택: [1, 4]
  6.  여섯 번째 막대(높이=3): 스택에 푸시된다.
    • 스택: [1, 4, 5]
  7.  스택 정리: 순회를 마치고 남은 막대들로 면적을 계산한다.
    • 막대 5, 4, 1이 차례대로 팝되면서 각각의 면적이 계산된다(면적=3, 6, 6).

이 과정을 통해 가장 큰 직사각형의 면적은 10이다(높이 5, 너비 2의 세 번째와 네 번째 막대). 모노톤 스택을 활용하면 히스토그램에서 가장 큰 직사각형을 효율적으로 찾을 수 있다.

 

코드

이 코드는 히스토그램에서 가장 큰 직사각형의 면적을 찾는 문제를 해결하기 위해 모노톤 스택을 사용한다.

heights = [int(input()) for x in range(int(input()))]
stack = []
max_area = 0
for i, h in enumerate(heights):
    start = i
    while stack and stack[-1][1] > h:
        index, height = stack.pop()
        max_area = max(max_area, height * (i - index))
        start = index
    stack.append((start, h))
for i, h in stack:
    max_area = max(max_area, h * (len(heights) - i))
print(max_area)

코드 분석

먼저, 사용자로부터 히스토그램의 높이를 입력받아 heights 리스트에 저장합니다. 그리고 stack을 초기화하며, 최대 면적을 저장할 max_area 변수도 0으로 초기화합니다.

모노톤 스택의 역할

모노톤 스택은 히스토그램의 막대를 처리할 때, 현재까지의 처리된 막대들 중에서 아직 직사각형의 오른쪽 경계를 결정하지 못한 막대들을 저장합니다. 스택에 저장되는 각 요소는 (index, height) 형태로, 막대의 인덱스와 높이를 나타냅니다.

for i, h in enumerate(heights):
    start = i
    while stack and stack[-1][1] > h:
        index, height = stack.pop()
        max_area = max(max_area, height * (i - index))
        start = index
    stack.append((start, h))
  • for i, h in enumerate(heights):: 이 반복문은 히스토그램의 모든 막대를 순회합니다. i는 막대의 인덱스, h는 막대의 높이입니다.
  • while stack and stack[-1][1] > h:: 스택이 비어있지 않고, 스택의 마지막 원소(즉, 가장 최근에 처리된 막대)의 높이가 현재 막대의 높이보다 큰 경우, 반복문을 실행합니다. 이는 현재 막대의 높이가 이전 막대들의 직사각형의 오른쪽 경계를 결정한다는 것을 의미합니다.
  • index, height = stack.pop(): 스택에서 막대를 하나 꺼내고, 그 막대의 인덱스와 높이를 얻습니다.
  • max_area = max(max_area, height * (i - index)): 꺼낸 막대를 기준으로 할 수 있는 최대 면적의 직사각형을 계산하고, 이전까지의 최대 면적과 비교하여 더 큰 값을 max_area에 저장합니다.
  • start = index: 현재 처리 중인 막대의 시작 인덱스를 갱신합니다. 이는 스택에서 꺼낸 막대의 시작 인덱스를 이어받는 것으로, 여러 막대가 연속해서 꺼내질 때 이들을 포함하는 더 큰 직사각형을 고려하기 위함입니다.
  • stack.append((start, h)): 현재 막대를 스택에 (시작 인덱스, 높이)의 형태로 추가합니다.

마지막으로 스택에 남은 막대 처리

for i, h in stack:
    max_area = max(max_area, h * (len(heights) - i))
  • 이 부분은 입력된 모든 막대를 처리한 후, 스택에 남아 있는 막대들을 처리합니다. 스택에 남은 막대는 히스토그램의 오른쪽 끝까지 직사각형을 이룰 수 있으므로, 각 막대에 대해 len(heights) - i를 너비로 하는 직사각형의 면적을 계산합니다

. 여기서 i는 막대의 시작 인덱스입니다.

왜 모노톤 스택이 효과적인가?

모노톤 스택은 이 문제에 효과적인 이유는, 히스토그램의 각 막대를 한 번씩만 처리하면서, 각 막대가 속할 수 있는 최대 면적의 직사각형을 효율적으로 계산할 수 있기 때문입니다. 막대를 스택에 추가하고 제거하는 과정에서, 각 막대의 '왼쪽 경계’와 '오른쪽 경계’를 결정할 수 있으며, 이를 통해 최대 면적을 계산할 수 있습니다. 이 알고리즘은 시간 복잡도 $O(n)$으로, 매우 효율적입니다.

문제 링크

https://www.acmicpc.net/problem/1725

 

1725번: 히스토그램

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자

www.acmicpc.net

관련문제

https://www.acmicpc.net/problem/11003

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

 

레퍼런스

https://www.youtube.com/watch?v=Dq_ObZwTY_Q

https://youtu.be/v4OX1OTzma4

출처: 넷플릭스 오징어 게임