양수 직사각형의 최대 크기 설명 | 코드트리
양수 직사각형의 최대 크기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.
www.codetree.ai
그리드안의 직사각형의 최대 크기를 리턴하는 문제. 무식하게 풀어도 되자만 2차원이라 머리를 써서 시간을 줄여야함.
코드는 단순하지만 그리드 각행을 읽어 히스토그램을 만드는데 각행을 돌면서 계산하지만 이전 히스토그램을 지우지 않아 위쪽을 반영하게 됨 하지만 단조스택이라으로 최대 크기를 체크하는데 이를 매 행 실행해 그 행까지의 최대 크기를 찾게 됨
사실 히스토그램 데이터를 눈으로 보면 인간은 최대 크기를 알수 있지만 컴퓨터는 알수 없기 때문에 단조 스택이라는 기술을 쓰게됨
이는 히스토그램을 걸어 올라 가다가 낮아지는 곳이 나오면 낮아지는 곳을 기준으로 높은 계단을 뽑아버리면서 최대 놃이를 구하게 됨. 다 뽑아버리고 나면 하나전 스택에는 자신보다 낮은 계단의 인덱스가 들어가게 된다.
코드 개요 (동작 흐름 요약)
- 입력: n×m 정수 그리드(grid).
- 목표: 값이 **양수(>0)**인 칸만으로 이뤄진 가장 큰 직사각형 넓이.
- height 누적
- 각 행 i에서 열 j에 대해, grid[i][j] > 0이면 height[j] += 1, 아니면 0.
- 이렇게 하면 행 i 기준으로 히스토그램(height)이 됨.
- 히스토그램 최대 직사각형 (단조 증가 스택)
- 스택엔 인덱스를 저장하며, height가 오름차순이 되도록 유지.
- 현재 높이 curr가 스택 top의 높이보다 작아지는 순간 pop하며
- h = height[pop_idx] (직사각형의 높이)
- w = j (스택 비었을 때) 또는 w = j - stack[-1] - 1 (남아 있을 때)
- area = h * w로 최대값 갱신.
- 마지막에 j == m에서 curr=0(센티널)을 넣어 스택을 모두 비우며 정산.
- 전역 최대값 갱신
- 각 행에서 구한 최대 넓이로 max_area 업데이트.
- 모든 행 처리 후 max_area > 0이면 출력, 아니면 -1 출력.
- 복잡도: 각 칸은 스택에 한 번 push, 한 번 pop → 행당 O(m), 전체 O(n·m).
- 핵심: 2D 문제를 행별 히스토그램으로 바꾸고, 히스토그램 최대 직사각형을 단조 증가 스택 + 센티널로 O(m)에 처리.
# 입력 형식:
# 첫 줄에 n(행 수), m(열 수)
# 다음 n줄에 걸쳐 각 행의 정수 m개가 공백으로 구분되어 주어짐
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
def maximal_positive_rectangle(grid):
"""
2D 그리드에서 '양수(>0)'로만 이루어진 가장 큰 직사각형의 넓이를 구한다.
아이디어:
1) 각 행을 내려가며, 열별로 '양수가 연속된 높이'를 누적해 height 히스토그램을 만든다.
2) 매 행마다 만들어진 height에 대해 '히스토그램 최대 직사각형'을
단조 증가 스택(모노토닉 스택)으로 O(m)에 계산하고, 최대값을 갱신한다.
3) 모든 행을 처리한 뒤, 한 번이라도 양수 직사각형이 없으면 -1을 반환한다.
반환:
- 최대 넓이(양수 면적이 있으면)
- 없으면 -1
주의:
- 이 함수는 외부 스코프의 n, m(입력에서 읽은 값)을 그대로 사용한다.
grid의 크기와 n, m이 일치한다고 가정한다.
"""
# height[j]: "현재 행까지" 위로 연속해서 양수가 몇 칸 쌓였는지(막대 높이)
# 예: grid[i][j] > 0이면 이전 높이에 +1, 아니면 0으로 리셋
height = [0] * m
# 지금까지 찾은 최대 직사각형 넓이
max_area = 0
# 모든 행을 위에서 아래로 처리
for i in range(n):
# 1) 현재 행 i를 반영해서 히스토그램(height) 갱신
for j in range(m):
# 양수면 높이 누적(+1), 0 또는 음수면 누적 끊기(0)
height[j] = height[j] + 1 if grid[i][j] > 0 else 0
# 2) 갱신된 height를 히스토그램으로 보고,
# 단조 증가 스택으로 최대 직사각형 넓이를 계산
# 스택에는 '인덱스 j'를 저장한다.
# 스택이 유지하는 불변식: height[stack[0]] <= height[stack[1]] <= ...
stack = []
# j를 0..m-1까지 돌고, 마지막에 j==m에서 curr_height=0(센티널)로 모두 정산
for j in range(m + 1):
# 센티널: 마지막 j==m일 때 '가상의 높이 0'을 던져 스택 비우기 유도
curr_height = height[j] if j < m else 0
# 현재 막대의 높이가 스택 top보다 작아지는 순간,
# top에 있던 막대(=그 높이)로 만들 수 있는 '최대 폭'이 확정된다.
# → pop 하면서 면적을 계산하고 max 갱신.
while stack and curr_height < height[stack[-1]]:
# h: 확정할 직사각형의 '높이'
h = height[stack.pop()]
# 폭 w 계산:
# - 스택이 비었으면, 왼쪽에 자신보다 낮은 막대가 없었음 → 0..(j-1)까지 전부 확장 가능 → w = j
# - 스택이 남아있으면, 스택 top이 '바로 왼쪽의 더 낮은 막대' → (stack[-1]+1)..(j-1)까지 확장 → w = j - stack[-1] - 1
w = j if not stack else j - stack[-1] - 1
# 면적 갱신
max_area = max(max_area, h * w)
# 현재 인덱스를 스택에 push (단, height가 단조 증가/같음이 되도록 위 while에서 충분히 pop한 뒤)
stack.append(j)
# 한 번도 양수 직사각형이 없었다면 0 그대로 → -1 반환
return max_area if max_area > 0 else -1
# 결과 출력
print(maximal_positive_rectangle(grid))
좋습니다 👍
그럼 예제로 자주 쓰던 heights = [3,2,3,1,0] (세 번째 행) 케이스를 가지고,
j, curr_height, pop 동작, h, w, area, max_area, stack 상태 변화를 표로 정리해 드릴게요.
초기 상태
- height = [3,2,3,1,0]
- max_area = 0
- stack = []
단계별 추적
j curr_height 동작 (while 내부) pop된 h w area = h×w max_area stack 상태
설명
- j=1에서 curr=2가 3보다 작으므로 pop → h=3, w=1 → area=3.
- j=3에서 curr=1이 들어오자 3, 2 두 개가 pop됨.
- 3을 pop했을 때 area=3
- 2를 pop했을 때 area=2×3=6 → 최대 갱신
- j=4에서 curr=0이 들어오자 1이 pop → area=4
- j=5 센티넬에서 마지막 pop → 면적 없음.
최종
- max_area = 6
- 즉, **높이=2, 폭=3인 직사각형(열0~2 구간)**이 최대.
실행순서
좋습니다 👍 이번엔 코드가 어떻게 “순서대로” 실행되는지, 복잡한 용어보다는 흐름 따라가기 느낌으로 쉽게 풀어드릴게요.
0. 입력 받기
- 첫 줄에서 n, m을 읽음 → 행, 열 개수.
- 그다음 줄들에서 grid에 숫자를 채움.
예: 4×5라면 grid는 4행 5열 배열.
1. 준비
- height = [0]*m : 열마다 “양수가 몇 칸 연속으로 쌓였나”를 기록.
- max_area = 0 : 최대 넓이를 저장.
2. 각 행 돌기
행 i 시작
- height 누적
- 현재 행에서 양수면 해당 열 높이를 +1, 음수나 0이면 높이를 0으로 리셋.
- 이렇게 해서 height 배열은 “막대그래프”처럼 됨.
- (위에서부터 양수가 얼마나 이어졌는지를 보여줌)
- 스택 초기화
- 빈 스택을 준비 (stack = []).
- 이제 이 스택을 써서 height 히스토그램에서 가장 큰 직사각형을 찾을 거예요.
- 열 0부터 m까지 검사 (m은 가짜 0 높이)
- curr_height = height[j] (j < m일 때), 아니면 0 (j == m → 센티널).
- 스택이 비어 있거나, curr_height ≥ stack.top 높이 → push.
- curr_height < stack.top 높이라면:
- 스택에서 pop → 그 막대를 높이로 삼은 직사각형이 확정됨.
- 폭 w 계산:
- 스택이 비면 w=j
- 스택이 있으면 w = j - stack[-1] - 1
- 면적 = h × w → max_area 갱신.
- 이 과정을 curr_height ≥ stack.top 될 때까지 반복.
- 그리고 j를 스택에 push.
- 행 i의 모든 열 처리 끝나면 → 그 행에서 최대 직사각형 면적이 max_area에 반영됨.
3. 모든 행 다 돌면
- 이제 max_area에는 전체 그리드에서의 최대 넓이가 저장되어 있음.
- 하나도 없으면 -1, 있으면 그 값 반환.
4. 출력
- 최종 결과를 print로 출력.
직관적인 흐름
- 한 행씩 내려가며 → 열별로 “양수 연속 높이”를 기록 (height).
- 그 height 배열을 막대그래프로 생각 → 단조 스택으로 직사각형 최대 면적 계산.
- 각 행마다 반복 → 전역 최대 갱신.
- 결론: 전체 그리드에서 가장 큰 양수 직사각형 넓이를 얻음.