Overview & Definition 머지 소트 트리는 백준 알고리즘 문제 13544 수열과 쿼리3 문제를 해결하기 위해서 사용하였던 자료구조입니다. 세그먼트 트리를 변형하여 만든 구조이기 때문에 초기화 하는 방법과, 쿼리 날리는 방법 등이 세그먼트 트리와 상당히 유사합니다. 세그먼트 트리는 리프 노드(Leaf Node)에 각 배열의 원소를 집어넣고, 부모노드에 자식 노드들의 최댓값이나 최솟값, 혹은 부분합을 저장해서 특정 구간에 대한 질의(Query)를 빠르게 처리하는데 특화된 자료구조입니다. 머지 소트 트리는 부모 노드에 각 자식 노드를 머지한 결과값을 저장한 배열을 저장합니다. 예를 들어서 왼쪽 자식 노드가 [1, 3, 5], 오른쪽 자식 노드가 [2, 4, 6]인 상태라면, 부모 노드는 [1, ..

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

Overview 트리 자료구조는 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행할 수 있도록 도와줍니다. 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다. 구간 트리는 특히 일차원 배열의 특정 구간에 대한 질문들(최대, 최소값 등)을 빠르게 대답하는 데에 주로 사용합니다. 예를 들어, 일차원 배열의 특정 구간에서 최대인 값을 찾기 위해서는 특정 구간을 일일이 순회하면서 최소값을 찾아야 했습니다. 하지만, 구간 트리를 이용하면 특정 구간의 최대값을 미리 전처리해서 부모 노드에 저장하는 방식을 취하기 때문에 (일종의 다이나믹 프로그래밍 방법이라고도 할 수 있습니다.) 훨씬 더 빠른 시간에 ..