6549 (1) 썸네일형 리스트형 백준 6549 히스토그램에서 가장 큰 사각형(python) 문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 정글에서 Week2 주제 중 분할정복에 해당하는 문제 였다. 분할 정복 접근법 말고도 여러 방법으로 풀어 봤는데, 그 중 스택을 사용한 방식이 인상적이였다. 그래서 스택으로 푼 풀이를 소개하려 한다. 먼저 효율성을 따지지 않고 완전 탐색 형식으로 원소 마다 앞뒤로 확장 하면서 값을 갱신해 나갈 수 있는데, 이렇게 하면 O(n^2) 의 .. 이전 1 다음