랄뚜기의 코딩일기

Max(Min) Heap Definition 정의 1 : max(min) heap은 internal node(child node가 존재하는 node)가 그들의 children보다 작지(크지) 않은 완전이진트리를 말한다. 정의 2 : root node가 각각의 child 보다 작고(크고) 각각의 child를 root node로 갖는 subtree들은 max(min) heap 의 특징을 가지고 있다. max(min) heap은 max(min)heap 특징을 지닌 완전이진트리이다. Priority Queue는 insert와 delete가 모두 O(log n)으로 insert와 delete가 모두 빈번하게 나오는 경우 훨씬 효율적이다. Heap Sort 방법 1. 배열 n의 정렬되지 않은 요소들을 max hea..

MSS는 위에 그림에서 L,R,LR 중 하나의 경우로 존재할 것이다. Divide-and Conquer로 Recursive하게 풀면 O(NlogN)에 풀 수 있다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위 문제를 풀 때 사용했던 방법이다. 이해 할 때 참고하면 좋다. 2차원 배열의 MSS를 구하는 문제이다. 크기가 n*n의 2차원 배열에는 약 1/4*n^4개의 subrectangles가 있다. 단순하게 모든 경우의 수를 더하는 것은 가로 세로 ..

일반적으로 Time-complexity가 polynomial이면 efficient하다고 하고, Exponential이면 inefficient하다고 정의한다. 하지만 실제로는 cubic만 되도 Time-complexity가 엄청 늘어나므로 실질적으로는 거리가 멀다. Worst-Case versus Average-Case Time Complexity Worst-case complexity란 말 그대로 모든 경우가 다 일어나고 끝나는 경우이다. Average-case complexity는 평균적으로 걸리는 시간 복잡도이다. Quick sort를 예로 들자면, Worst-case complexity는 O(n^2)이고 Average-case complexity는 O(nlogn)이다 g(n)은 이해하였으니 넘어가도..

Order of Algorithms