[Algorithm] C++/Python 백준 6549번 : 히스토그램에서 가장 큰 직사각형
히스토그램은 여러 개의 직사각형이 연속적으로 나열된 도형으로, 각 직사각형은 너비가 1이고 높이는 다양한 값을 가질 수 있다. 이 문제에서는 주어진 히스토그램에서 가장 큰 넓이를 갖는 직사각형을 찾는 것이 목표이다. 예를 들어, 히스토그램의 막대 높이가 [2, 1, 5, 6, 2, 3]일 때, 가장 큰 직사각형의 넓이는 10이다.
입력은 여러 개의 테스트 케이스로 구성되며, 각 테스트 케이스는 첫 번째 수로 막대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 각 막대의 높이 h_i(0 ≤ h_i ≤ 1,000,000,000)가 주어진다. 마지막 입력은 0으로 표시되며, 이는 입력의 끝을 나타낸다. 각 테스트 케이스마다 히스토그램에서 가장 큰 직사각형의 넓이를 출력해야 한다.
이 문제는 매우 큰 데이터셋을 효율적으로 처리해야 하므로, 시간 복잡도가 낮은 알고리즘을 사용해야 한다.
문제 : https://www.acmicpc.net/problem/6549
 |
|---|
접근 방식
이 문제를 해결하기 위해 스택(Stack)을 이용한 선형 시간 알고리즘(O(N))을 사용한다. 일반적인 아이디어는 히스토그램을 왼쪽에서 오른쪽으로 순회하면서 각 막대에 대해 가능한 최대 직사각형의 넓이를 계산하는 것이다. 스택에는 막대의 인덱스를 저장하며, 현재 막대의 높이가 스택의 최상단 막대보다 작을 경우 스택에서 막대를 꺼내면서 최대 넓이를 갱신한다.
이 알고리즘의 핵심은 다음과 같다:
- 스택에는 높이가 증가하는 순서로 막대의 인덱스를 저장한다.
- 현재 막대의 높이가 스택의 최상단 막대보다 작으면, 스택에서 막대를 꺼내고 해당 막대를 높이로 하는 최대 직사각형의 넓이를 계산한다.
- 이 과정을 히스토그램의 끝까지 진행하며, 스택에 남은 막대들도 동일하게 처리한다.
이 방법을 통해 시간 복잡도 O(N)에 문제를 해결할 수 있다.
C++ 코드와 설명
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
while (true) {
int n;
cin >> n; // 히스토그램의 막대 수 입력
if (n == 0) break; // 입력의 끝이면 종료
vector<long long> heights(n); // 막대의 높이를 저장할 벡터
for (int i = 0; i < n; ++i) {
cin >> heights[i]; // 각 막대의 높이 입력
}
stack<int> s; // 인덱스를 저장할 스택
long long max_area = 0; // 최대 넓이 초기화
for (int i = 0; i < n; ++i) {
// 현재 막대의 높이가 스택 최상단 막대보다 작을 때까지 반복
while (!s.empty() && heights[s.top()] > heights[i]) {
int tp = s.top(); // 스택 최상단 막대의 인덱스
s.pop(); // 스택에서 제거
long long h = heights[tp]; // 스택 최상단 막대의 높이
long long width = s.empty() ? i : i - s.top() - 1; // 너비 계산
max_area = max(max_area, h * width); // 최대 넓이 갱신
}
s.push(i); // 현재 막대의 인덱스를 스택에 추가
}
// 스택에 남은 막대 처리
while (!s.empty()) {
int tp = s.top();
s.pop();
long long h = heights[tp];
long long width = s.empty() ? n : n - s.top() - 1;
max_area = max(max_area, h * width);
}
cout << max_area << '\n'; // 최대 넓이 출력
}
return 0;
}
코드의 동작 단계별 설명:
- 입력 처리:
- 히스토그램의 막대 수
n을 입력받는다.n이0이면 루프를 종료한다. n개의 막대 높이를heights벡터에 저장한다.
- 히스토그램의 막대 수
- 스택 초기화 및 최대 넓이 변수 설정:
- 인덱스를 저장할 스택
s를 초기화한다. - 최대 넓이를 저장할 변수
max_area를0으로 초기화한다.
- 인덱스를 저장할 스택
- 히스토그램 순회:
- 막대를 하나씩 순회하면서 현재 막대의 높이가 스택 최상단 막대의 높이보다 작을 경우, 스택에서 막대를 꺼내며 최대 넓이를 계산한다.
- 너비
width는 스택이 비어 있으면 현재 인덱스i, 그렇지 않으면i - s.top() - 1이 된다. - 최대 넓이는
max_area와 계산된 넓이 중 큰 값으로 갱신한다. - 현재 막대의 인덱스를 스택에 추가한다.
- 남은 스택 처리:
- 히스토그램 순회를 마친 후에도 스택에 남아 있는 막대들을 처리하여 최대 넓이를 갱신한다.
- 이때 너비는 스택이 비어 있으면
n, 그렇지 않으면n - s.top() - 1이 된다.
- 결과 출력:
- 각 테스트 케이스마다 계산된
max_area를 출력한다.
- 각 테스트 케이스마다 계산된
변경 사항 설명:
h와width변수를int에서long long으로 변경하였다. 이는 막대의 높이와 넓이의 곱이int범위를 초과할 수 있기 때문이다.- 스택에서 막대의 높이를 가져올 때 임시로 인덱스
tp를 사용하여 코드의 가독성을 높였다.
C++ without library 코드와 설명
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <malloc.h>
int main() {
while (1) {
int n;
scanf("%d", &n); // 히스토그램의 막대 수 입력
if (n == 0) break; // 입력의 끝이면 종료
long long* heights = (long long*)malloc(n * sizeof(long long)); // 막대 높이 배열 동적 할당
int* stack = (int*)malloc(n * sizeof(int)); // 스택 배열 동적 할당
int top = -1; // 스택의 최상단 인덱스
for (int i = 0; i < n; ++i) {
scanf("%lld", &heights[i]); // 각 막대의 높이 입력
}
long long max_area = 0; // 최대 넓이 초기화
int i = 0;
while (i < n) {
// 스택이 비어 있거나 현재 막대의 높이가 스택 최상단 막대보다 크거나 같으면
if (top == -1 || heights[stack[top]] <= heights[i]) {
stack[++top] = i++; // 현재 막대의 인덱스를 스택에 추가
} else {
int tp = stack[top--]; // 스택에서 최상단 막대 인덱스 꺼내기
long long h = heights[tp]; // 높이
long long width = top == -1 ? i : i - stack[top] - 1; // 너비 계산
long long area = h * width; // 넓이 계산
if (area > max_area) max_area = area; // 최대 넓이 갱신
}
}
// 남은 스택 처리
while (top != -1) {
int tp = stack[top--];
long long h = heights[tp];
long long width = top == -1 ? i : i - stack[top] - 1;
long long area = h * width;
if (area > max_area) max_area = area;
}
printf("%lld\n", max_area); // 최대 넓이 출력
free(heights); // 동적 할당 메모리 해제
free(stack);
}
return 0;
}
코드의 동작 단계별 설명:
- 입력 처리 및 메모리 할당:
- 히스토그램의 막대 수
n을scanf로 입력받는다.n이0이면 루프를 종료한다. n크기의heights배열과stack배열을 동적 할당한다.- 각 막대의 높이를
heights배열에 저장한다.
- 히스토그램의 막대 수
- 스택 및 변수 초기화:
- 스택의 최상단 인덱스를 나타내는
top을-1로 초기화한다. - 최대 넓이를 저장할
max_area를0으로 초기화한다.
- 스택의 최상단 인덱스를 나타내는
- 히스토그램 순회:
- 인덱스
i를0부터 시작하여n까지 순회한다. - 현재 막대의 높이가 스택 최상단 막대의 높이보다 크거나 같으면 스택에 인덱스를 추가하고
i를 증가시킨다. - 그렇지 않으면 스택에서 막대 인덱스를 꺼내며 최대 넓이를 계산한다.
- 너비는 스택이 비어 있으면
i, 그렇지 않으면i - stack[top] - 1이 된다.
- 인덱스
- 남은 스택 처리:
- 히스토그램 순회를 마친 후에도 스택에 남아 있는 막대들을 처리하여 최대 넓이를 갱신한다.
- 결과 출력 및 메모리 해제:
- 계산된
max_area를 출력한다. - 동적 할당한 메모리를 해제한다.
- 계산된
변경 사항 설명:
h,width,area변수를long long으로 선언하여 오버플로우를 방지하였다.scanf와printf에서long long자료형을 처리하기 위해%lld포맷 지정자를 사용하였다.
Python 코드와 설명
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
input = sys.stdin.readline
while True:
inputs = sys.stdin.readline().split()
n = int(inputs[0]) # 히스토그램의 막대 수
if n == 0:
break # 입력의 끝이면 종료
heights = list(map(int, inputs[1:])) # 막대 높이 리스트
stack = [] # 인덱스를 저장할 스택
max_area = 0 # 최대 넓이 초기화
i = 0
while i < n:
# 스택이 비어 있거나 현재 막대의 높이가 스택 최상단 막대보다 크거나 같으면
if not stack or heights[stack[-1]] <= heights[i]:
stack.append(i) # 현재 막대의 인덱스를 스택에 추가
i += 1
else:
tp = stack.pop() # 스택에서 최상단 막대 인덱스 꺼내기
h = heights[tp] # 높이
width = i if not stack else i - stack[-1] - 1 # 너비 계산
area = h * width # 넓이 계산
if area > max_area:
max_area = area # 최대 넓이 갱신
# 남은 스택 처리
while stack:
tp = stack.pop()
h = heights[tp]
width = i if not stack else i - stack[-1] - 1
area = h * width
if area > max_area:
max_area = area
print(max_area) # 최대 넓이 출력
코드의 동작 단계별 설명:
- 입력 처리:
sys.stdin.readline()을 사용하여 입력을 빠르게 처리한다.- 한 줄의 입력을 받아 공백으로 분리하여
inputs리스트에 저장한다. - 첫 번째 요소를 막대 수
n으로 변환한다.n이0이면 루프를 종료한다. - 나머지 요소들을 막대 높이로 변환하여
heights리스트에 저장한다.
- 스택 및 변수 초기화:
- 인덱스를 저장할 스택
stack을 빈 리스트로 초기화한다. - 최대 넓이를 저장할
max_area를0으로 초기화한다.
- 인덱스를 저장할 스택
- 히스토그램 순회:
- 인덱스
i를0부터 시작하여n까지 순회한다. - 현재 막대의 높이가 스택 최상단 막대의 높이보다 크거나 같으면 스택에 인덱스를 추가하고
i를 증가시킨다. - 그렇지 않으면 스택에서 막대 인덱스를 꺼내며 최대 넓이를 계산한다.
- 너비는 스택이 비어 있으면
i, 그렇지 않으면i - stack[-1] - 1이 된다.
- 인덱스
- 남은 스택 처리:
- 히스토그램 순회를 마친 후에도 스택에 남아 있는 막대들을 처리하여 최대 넓이를 갱신한다.
- 결과 출력:
- 계산된
max_area를 출력한다.
- 계산된
변경 사항 설명:
- 입력 속도를 향상시키기 위해
sys.stdin.readline을 사용하였다. - 최대 넓이를 계산할 때 조건문을 추가하여
max_area를 갱신하도록 수정하였다.
결론
이 문제를 통해 스택을 활용한 효율적인 알고리즘의 중요성을 다시 한 번 느낄 수 있었다. 특히 큰 입력 데이터를 처리할 때 자료형에 대한 정확한 이해와 활용이 얼마나 중요한지 깨달았다. C++ 코드에서 int와 long long의 차이가 결과에 큰 영향을 미칠 수 있으므로, 항상 변수의 범위를 고려하여 자료형을 선택해야 한다.
추가적인 최적화 방안으로는 입력 속도를 향상시키기 위해 C++에서는 scanf와 printf를 사용하거나, Python에서는 sys.stdin.readline을 사용할 수 있다. 앞으로도 다양한 알고리즘 문제를 통해 알고리즘적 사고와 최적화 기법을 연습해야겠다.
Comments