풀이 세그먼트트리를 응요한 자료구조인 머지 소트 트리(Merge Sort Tree)를 이용하면 O((logn)^2)시간 안에 해결할 수 있는 문제입니다. 머지 소트트리는 간단하게 말해서 트리의 각 노드에 자식들의 최솟값이나 최댓값을 저장하는 것이 아니라, 머지소트(Merge Sort)시에 일어나는 각 배열들의 중간 상태를 저장하는 자료 구조입니다. [5, 2, 4, 6, 1, 3, 2, 6]의 배열을 머지소트를 이용해서 정렬할 경우, 위의 그림과 같은 과정을 거치게 됩니다. 이 때, 각 노드의 상위 노드에는 두 배열을 머지하여 생긴 새로운 배열을 저장합니다. 즉 배열(혹은 리스트)의 배열 구조를 띄게 되는 것입니다. 이렇게 머지소트트리를 생성하고 난 후에는 쿼리를 날려서, 각 구간안에 포함되는 배열들 중..

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

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

풀이 펜윅 트리로 검색해서 들어갔던 문제이기 때문에 어떻게든 펜윅 트리를 사용해서 풀어야 한다는 강박관념이 있었던 문제였습니다. 펜윅트리는 저번 포스팅에서도 간략하게 설명했지만 구간합을 빠르게 구하기 위해 사용되는 알고리즘입니다. 따라서 문제의 핵심은 특정 영화의 앞에 놓여있는 영화의 개수를 어떻게 구간합으로 표현할 것인가?입니다. 1. 영화는 한번의 시행때마다 그 위치가 움직이므로 위치의 변동을 표현할 수 있어야 한다. 2. 펜윅 트리는 구간의 합을 빠르게 구할 수 있는 자료구조이므로, 구간의 합을 영화 앞에 쌓여 있는 영화의 개수로 치환할 수 있어야 한다. 3. 영화의 위치가 변했을 때, 트리를 업데이트하기가 용이해야 한다. 위 생각을 적용해볼 때, n+m의 크기를 갖는 펜윅 트리를 구성하고, 특정 ..

풀이 구간 합을 구하기 위해서 펜윅 트리를 사용하였습니다. 펜윅 트리에 대한 자세한 내용은 펜윅트리 포스팅을 참고해주세요 소스 코드 (JAVA) import java.util.*; public class BOJ_2042 { public static void main(String args[]){ Scanner input = new Scanner(System.in); int n = input.nextInt(); int m = input.nextInt(); int k = input.nextInt(); long[] matrix = new long[n+1]; FenwickTree fenwick = new FenwickTree(n); // initialize fenwick tree for(int i=1;i

Overview 펜윅 트리 (Fenwick Tree)는 구간 합을 빠르게 구하기 위해 고안된 자료구조입니다. 결론부터 말씀을 드리면 구간트리의 진화된 형태라고도 할 수 있습니다. 기존의 배열 자체에서 구간 합을 구하기 위해서는 해당 구간을 모두 순회하면서 값을 더해야 하므로 구간 길이에 비례하는 시간이 소요됩니다. O(N)의 시간복잡도를 갖는다는 의미이죠. 이를 더 빠르게 구현하기 위해 고안된 자료구조가 바로 구간트리이며, 구간트리가 갖는 장점을 살리면서 메모리를 훨씬 더 절약할 수 있도록 고안된 자료구조가 바로 펜윅 트리입니다. (구간 트리에 관한 자세한 내용은 구간 트리를 다룬 포스팅을 참고해주세요) Definition 펜윅 트리가 갖는 중요한 아이디어는 구간 합을 구하기 위해서 부분 합만을 빠르게 ..