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가 있다.
단순하게 모든 경우의 수를 더하는 것은 가로 세로 각각 탐색이 O(n^2), 합을 구하는 것이 O(n)이므로 총 O(n^2*n*n^2*n) = O(n^6)이 된다.
위 방식은 O(n^4)이 걸리는 알고리즘이다. 오른쪽 모서리까지의 합을 저장해 놓아서 계산할 때 사용한다. 따라서 합을 구하는 시간복잡도는 O(1)이므로 가로세로 탐색만 하면 되기 때문에 시간 복잡도는 O(n^4)이 된다.
위 방식은 시간복잡도 O(n^3)에 풀 수 있는 문제이다. 탐색은 세로 방향만 탐색하고 가로로 내려가면서 Kadane 알고리즘을 써서 최댓값을 구하는 방식이다.
'3-2 > 알고리즘설계와분석' 카테고리의 다른 글
| chap3-2 Quick Sort (0) | 2021.10.05 |
|---|---|
| chap3-1 Merge Sort (0) | 2021.09.30 |
| chater2 Max(Min) Heap (0) | 2021.09.28 |
| chapter1-2 (0) | 2021.09.15 |
| chap1 (0) | 2021.09.10 |