풀이 세그먼트트리를 응요한 자료구조인 머지 소트 트리(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 네트워크를 공부하거나, 인터넷 연결등을 하다 보면 허브(HUB)라는 용어를 자주 듣게 됩니다. 그리고 비슷한 용어로 스위치(Switch), 브리지(Bridge), 라우터(Router)등의 용어들도 많이 듣게 되는데, 처음 네트워크를 접하는 입장에서 이들 용어를 정확히 이해하고 구분해 내는 것은 생각보다 쉽지 않은 것 같습니다. 4가지의 용어는 서로 다른 장비를 가리키는 말이지만, 눈으로 보기에 이들 장비는 그냥 구멍이 많이 뚫린 상자처럼 보이기 때문입니다. 이번 포스팅에서는 그중 "허브"라는 장비에 대해서 설명하려고 합니다. Definition 허브란 쉽게 말해서 컴퓨터와 컴퓨터 사이, 즉 네트워크 장비와 장비를 연결해 주는 기능을 수행하는 장비입니다. 우리가 인터넷에 접속해서 블로그의 ..

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