6549번 - 히스토그램에서 가장 큰 직사각형
풀이 방법은 이렇습니다.
1. 최솟값 세그먼트 트리를 통해 [최솟값,[최솟값의 인덱스들]]로 정리
2. 분할 정복을 통해 해당 구간의 최솟값*구간의 넓이로 최대 넓이를 계속 갱신, 최솟값의 인덱스를 기준으로 분할
다만 인덱스들을 저장하는 과정에서 list로 저장하니 메모리가 터져가지고.. 결국 tuple에 인덱스를 문자열로 저장 후 분할 정복 시에 list 형태로 만들어서 분할하는 꼼수 아닌 꼼수를 사용했습니다.
인덱스를 메모리를 덜 사용하면서 저장할 수 있을까요?
댓글을 작성하려면 로그인해야 합니다.
mastershim 3년 전
풀이 방법은 이렇습니다.
1. 최솟값 세그먼트 트리를 통해 [최솟값,[최솟값의 인덱스들]]로 정리
2. 분할 정복을 통해 해당 구간의 최솟값*구간의 넓이로 최대 넓이를 계속 갱신, 최솟값의 인덱스를 기준으로 분할
다만 인덱스들을 저장하는 과정에서 list로 저장하니 메모리가 터져가지고.. 결국 tuple에 인덱스를 문자열로 저장 후 분할 정복 시에 list 형태로 만들어서 분할하는 꼼수 아닌 꼼수를 사용했습니다.
인덱스를 메모리를 덜 사용하면서 저장할 수 있을까요?