알고리즘
2020. 5. 13.
히스토그램에서 가장 큰 직사각형
백준 온라인 저지 6549 빗물 채우기 문제로 모 회사 면접에 나왔다 당시 분명 풀어본건데 긴장한 탓인지 못풀어서 몹시 원통했던 기억에 있다. 출근하다가 급 생각나서 기록해보겠다 다양한 풀이방식이 있겠지만 내가 아는 방식은 2가지이다. 1. 스택 활용 O(n) 단순히 값을 넣어가며 앞뒤로 2번 Sweep해서 구하는 방식 2. 세그먼트 트리 + 분할 정복 O(nlogn)세그먼트 트리로 구간 내 최대값을 구하고 분할정복으로 반복하는 방식 추후 정리