13. 분할 정복

13.md

0.00MB

0. 복습
1. 분할 정복 Divide and Conquer(DNC)

merge sort를 할 때 생각해보면, 한 그룹을 둘로 나누는 과정을 반복해 모두 쪼갠다음, 다시 합쳐나가는 방식이다. 이런 문제 풀이 방식을 분할정복이라고 한다. 하나의 거대한 문제를 작은 여러개의 문제로 나누는 것.

1725번을 보자.

만약 가운데 두개를 고정하는 문제였다면, 그 두개를 기준으로 양 옆에 높이가 더 높은 막대를 포함시키면서 탐색한다. 이를 그리디 방법이라고 부르겠다.

이를 이용해서 dnc(L, R)을 정의하겠다.

dnc(L, R) = L ~ R 구간에서의 직사각형 최대 넓이

dns(L, R) = max( dns(L, mid), dns(mid+1, R), 그리디방법 )

즉, 가운데를 잘랐을 때 우리가 구할 답은 가운데 기준 왼쪽에 있을 수 있고, 오른쪽에 있을 수 있고, 왼쪽 오른쪽에 걸쳐있을 수 있다.

여기서 왼쪽 오른쪽에 걸쳐있다는 것은 가운데 두 개의 직사각형(mid, mid+1)을 모두 포함한다.

시간복잡도는 O(nlogn) 이다.

참고 : 6549, 1725, 14727, 12846, 2104

2. 연속 합 Maximum Subarray

1912번을 보자. 우선 이건 dp로 해결할 수 있다.

dp[i] 가 i를 포함한 가장 큰 연속 합이라고 정의할 때, 모든 dp값들 중에서 가장 큰 값을 출력하면 된다.

dp[i] = max(dp[i-1], 0) + arr[i]가 dp 식이다.

#include <iostream>
using namespace std;
int dp[100001];
int arr[100001];
int n;
int main(){
    cin >> n;
    for(int i=1; i<=n; ++i){
        cin >> arr[i];
        dp[i]=max(dp[i-1], 0) + arr[i];
    }
    int maxx=arr[1];
    for(int i=1; i<=n; ++i){
        maxx=max(maxx, dp[i]);
    }
    cout << maxx << '\n';
    //dp[i] : i까지 봤을 때 가장 큰 합
}

이를 분할정복으로 풀 수 있다.

우선 Node를 정의해야 한다. 이 Node를 어떠한 연속된 구간이라고 정의한다.

이 Node에는 sum, lm, rm, tm이 있는데
sum은 그 구간의 전체 합을,
lm은 left_max로, 그 구간의 왼쪽 끝 원소를 무조건 포함한 최대 연속 합을,
rm은 right_max로, 그 구간의 오른쪽 끝 원소를 무조건 포함한 최대 연속 합을,
tm은 total_max로, 해당 구간의 최대 연속 합을 저장한다.

이 Node를 반씩 쪼개고, 그 쪼갠걸 다시 합쳐가면서 문제를 해결 할 것이다.

최초의 Node는 전체 구간, 즉 [1,N]을 의미한다. 이를 반으로 쪼갠 후 왼쪽을 Lnode, 오른쪽을 Rnode라고 하겠다.

이 Node에서의 lm은 (Lnode의 lm), (Lnode의 전체 + Rnode의 lm) 둘 중 큰 값이다.
각각 (중간을 포함하지 않는 lm), (중간을 포함하는 lm)으로 볼 수 있다.

rm은 (Rnode의 rm), (Rnode의 전체 + Lnode의 rm) 둘 중 큰값이다.
각각 (중간을 포함하지 않는 rm), (중간을 포함하는 rm)으로 볼 수 있다.

tm은 (Lnode의 tm), (Rnode의 tm), (Lnode) 셋 중 가장 큰값이다.
각각 (중간을 포함하지 않고 왼쪽에 있는 최대 구간합), (중간을 포함하지 않고 오른쪽에 있는 최대 구간합), (중간을 포함하는 최대 구간 합)으로 볼 수 있다.

이렇게 분할정복을 마치고 최초 Node의 전체구간, 즉 [1,N]에서의 tm이 답이 되는것이다.

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int A[100001];
struct Node {
    int sum, lm, rm, tm; // left_max, right_max, total_max
};

Node dnc(int L, int R) {
    Node ret;
    if(L==R) {
        ret.sum = ret.lm = ret.rm = ret.tm = A[L];
        return ret;
    }
    int mid = (L+R)/2;
    Node Lnode = dnc(L, mid);
    Node Rnode = dnc(mid+1, R);
    ret.sum = Lnode.sum + Rnode.sum;
    ret.lm = max(Lnode.lm, Lnode.sum + Rnode.lm);
    ret.rm = max(Rnode.rm, Rnode.sum + Lnode.rm);
    ret.tm = max({Lnode.tm, Rnode.tm, Lnode.rm + Rnode.lm});
    return ret;
}
int main(){
    cin >> N;
    for(int i=1; i<=N; ++i){
        cin >> A[i];
    }
    cout << dnc(1, N).tm << '\n';
}

참고 : 1912, 10211