Techniques In DP (3) - DnC Optimization

DP 문제에서 $O(N)$의 시간복잡도를 $O(lgN)$으로 줄여주는 또 다른 테크닉이다. DP에 DnC는 굉장히 안어울릴 것 같다. 사실 그렇긴 하다. 사용되어질 조건이 까다롭고, 이 문제에서 DnC를 사용할 수 있는 조건을 만족하는지 알기도 굉장히 어렵다. DnC Opmization을 사용하는 문제는 대체로 굉장히 까다롭고 어렵다.

DnC Optimization이란?

Divide and Couquer Optimization의 약자로 한글로 해석하면 분할정복 최적화 기법이다. 말 그대로 분할 정복을 사용해서 최적화를 시키는 기법이다. 

When?

$DP[i]=\underset{1\leq j\leq N}{min}F(i,j)$ 에서 $DP[i]=F(i,j)$를 만족하는 $j$를$A[i]$라고 할 때,

$If$  $i_1<i_2$ $then,$ $A[i_1]\leq A[i_2]$

이런 상황에서 DnC Optimization을 사용할 수 있다. 

How?

위의 식을 다시 살펴보자. 어떤 i에 대해서 무슨 j에 대해서 최솟값이 나올지 모르기 때문에 모든 i에 대해서 j를 1~N까지 모두 해봐야하기 때문에 $O(N^2)$이 나온다. 하지만 두 번째 식과 같은 조건이 있기 때문에 i에 대해서 가능한 j의 범위를 줄일 수 있다. 

1. 처음에 N/2에 대해서 1~N까지 모두 탐색해 A[N/2]를 찾는다.
2. 1~N/2는 1~A[N/2]까지만 찾으면 되고 N/2~N은 A[N/2]~N에서만 찾으면 된다.
이는 두 개를 O(N)만에 알 수 있다는 것이다.
3. 그 두 개를 각각 N/4와 3N/4로 선택하면, 다시 그룹은 4개로 쪼개지게 된다. 
이는 4개의 DP값과 A값을 O(N)만에 찾을 수 있다는 것이다. 
4. 이렇게 계속 절반으로 쪼개나가다 보면 총 반복횟수는 O(lgN)이고, 한 번당 시간복잡도는 O(N)이기 때문에 총 시간복잡도 O(NlgN)에 해결 할 수 있다. 

그림과 함께 설명

왼쪽과 같이 위 A그룹과 밑의 B그룹이 있으면 일단 가운데인 4가 언제 최댓값이 나오는지 확인한다. O(N)으로 탐색해서 5와 연관되었을 때 최대였다고 하자. 

그렇다면 4를 기준으로 A(1~3)은 B(1~5)중에서 최댓값이 나오며 A(5~7)은 B(5~7)에서 최댓값이 나온다. 이때 그룹에서의 가운데인 각각 2와 6을 구간내에서 탐색해서 알아보고 각각 2,5일때가 최대라고 하자. 

이 다음은 1,3,5,7인 4개의 그룹으로 나누어졌다. 4개의 그룹은 각각 B에서 (1~2),(2~5),(5~5),(5~7) 구간안에서 최댓값을 가지게 되고, 이 구간을 차례로 탐색해서 결과를 얻어내면 된다. 

전체의 최댓값은 F(1,1),F(2,2),F(3,4),F(4,5),F(5,5),F(6,5),F(7,6)중에 있게 된다. 

코드

void DnCo(ll s,ll e,ll is,ll ie)
{
    ll i,j,k,l,mid=(s+e)/2;
    ll maxi=0,id=0;
    ll lo=max(mid,is);
    ll hi=min(mid,ie);
    for(i=lo;i<=hi;i++)
    {
        if( (i-mid)*t[i]+v[mid]>maxi )
        {
            maxi=(i-mid)*t[i]+v[mid];
            id=i;
        }
    }
    ans=max(ans,maxi);
    if(s!=mid) DnCo(s,mid-1,is,id);
    if(e!=mid) DnCo(mid+1,e,id,ie);
}

추천 문제

이 테크닉도 문제에서 이 테크닉을 뽑아내고 알아채는 것이 어렵기 때문에, 최대한 문제 추천을 하지 않으려고 한다,

BOJ 11001 김치 https://www.acmicpc.net/problem/11001