1725
-
백준 1725번 히스토그램 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 2. 20:42
이번 글은 백준 알고리즘 문제 1725번 "히스토그램"을 다뤄본다.6549번 "히스토그램에서 가장 큰 직사각형" 또한 거의 동일한 문제가 된다. 문제의 접근은 스택을 활용한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 처음에는 도저히 생각이 나지 않아, 순수하게 접근했다.시간초과가 발생할 것을 알았지만, 일단 풀어보았다.단순히, 하나의 막대를 기준으로, 왼쪽 오른쪽에 대..