풀이 최소 스패닝 트리를 구하는 데에는 크게 2가지 알고리즘 (크루스칼 알고리즘, 프림 알고리즘)이 알려져 있습니다. 위 문제는 최소 스패닝 트리의 가중치 값을 묻는 기본적인 문제이기 때문에, 개인적으로 구현하기 편했던 크루스칼 알고리즘을 사용하였습니다. 크루스칼 알고리즘을 사용하기 위해서는 먼저 상호 배타적 집합 (Disjoint Set)을 먼저 구현해야 합니다. 크루스칼 알고리즘은 프림 알고리즘 과는 다르게, 간선을 가중치 순으로 먼저 정렬한 후에, 가중치가 작은 간선부터 이어 나가면서, 해당하는 간선의 두 정점이 이미 같은 트리에 속해 있는지를 판단해야 합니다. 예를 들어, 1과 2를 잇는 가중치 1인 간선을 추가하려고 할 때, 1과 2를 이어주는 경로가 이미 존재한다면 해당 간선을 추가해서는 안된..

풀이 세그먼트 트리를 이용해 O(nlogn) 시간 안에 해결할 수 있는 문제입니다. 모든 세그먼트 트리 문제가 그렇듯, 각 구간에 저장할 정보가 무엇인지를 정하는 것이 문제 해결의 주 요소입니다. 입력받은 숫자들이 담겨 있는 배열의 전체 크기에 함수를 한번 호출하면, 그 함수들의 분할 정복을 통해 최대 직사각형의 넓이를 구하는 방식을 생각해 볼 수 있습니다. 예를 들어서 전체 8만큼의 크기를 갖는 배열이 있다고 할 때 (2 1 4 5 1 3 3 1) 전체 구간을 모두 포함하는 직사각형의 넓이와, 최소 높이를 갖는 인덱스를 기준으로 왼쪽 구간을 모두 포함하는 직사각형의 넓이와, 오른쪽 구간을 모두 포함하는 직사각형의 넓이를 비교하여 가장 큰 넓이를 갖는 사각형을 출력하면 되는 것입니다. 왼쪽 구간을 포함하..