[C/C++] 백준 #1725 히스토그램(분할 정복)
히스토그램 문제는, 히스토그램 그래프에서 x축의 빈도의 너비와, y축의 값의 높이 단위 크기가 같을때, 히스토그램 그래프 안에 직사각형의 넓이가 최대가 되는 것을 구하는 문제입니다. 분할정복 문제의 전형적인 경우입니다. 예를 들어서 히스토그램의 값이 [ 3, 2, 3, 4, 2, 3, 4, 1 ]의 값을 가진다고 하면, 이를 히스토그램으로 표현하면 아래와 같습니다. 사람이 본다면 인지적으로 높이 2인 직사각형이 가장 넓을 것이라 할 수 있습니다. 하지만, 히스토그램의 x축 개수가 매우 많다면 사람이 인지적으로 판단하는 것도 힘듭니다. 컴퓨터가 푼다면, 높이 1인 것부터 차례로 찾아볼 수도 있습니다. 히스토그램의 1보다 큰 수가 얼마나 연속되었는지 찾으면 됩니다. 이것이 \(O(N)\) 알고리즘이니, 높이..
2022. 10. 5.
