미분류 – 페이지 661 – naver.HOW data lake by AI

알고리즘 경진대회나 고급 알고리즘 문제를 풀다 보면 단순한 접근법으로는 시간 초과나 메모리 초과가 발생하는 경우가 많습니다. 이런 상황에서 다양한 최적화 기법이 필요한데, 오늘은 그중에서도 특히 강력한 기법인 Convex Hull Trick(CHT)에 대해 살펴보겠습니다.

Convex Hull Trick이란?

Convex Hull Trick은 특정 형태의 동적 프로그래밍(DP) 문제를 최적화하는 기법입니다. 직선 집합에서 특정 x 좌표에 대한 최소값(또는 최대값)을 효율적으로 계산할 수 있게 해줍니다. 일반적으로 다음과 같은 형태의 DP 점화식을 최적화할 때 사용합니다:

DP[i] = min/max(A[j] * B[i] + DP[j]) for j < i

여기서 단순히 모든 j에 대해 계산하면 O(n²) 시간이 걸리지만, CHT를 사용하면 O(n log n) 또는 특수한 경우 O(n)까지 최적화할 수 있습니다.

CHT의 핵심 원리

CHT의 기본 아이디어는 다음과 같습니다:

각 상태 j에 대해 직선 f_j(x) = A[j] * x + DP[j]를 생성합니다.
이 직선들의 하위 포락선(lower envelope)만 유지합니다.
이후 어떤 x 좌표에서 최소값을 쿼리할 때, 이 포락선에서 해당 x 좌표에 해당하는 최소값을 찾습니다.

이렇게 하면 모든 j에 대해 계산하는 대신, 하위 포락선을 구성하는 직선들에 대해서만 계산하면 되므로 효율성이 크게 향상됩니다.

CHT 구현 방법

CHT를 구현하는 방법은 크게 두 가지가 있습니다:

1. 정적 CHT (Static CHT)

기울기가 단조롭게 변화하는 경우(예: 증가 또는 감소)에 사용할 수 있는 간단한 방법입니다. 이 경우 직선을 추가할 때마다 불필요한 직선을 제거할 수 있습니다.

struct Line {
    ll m, b; // y = mx + b
    
    Line(ll _m, ll _b) : m(_m), b(_b) {}
    
    ll eval(ll x) const {
        return m * x + b;
    }
};

vector<Line> hull;

// 두 직선의 교차점의 x좌표
double intersect(const Line& l1, const Line& l2) {
    return (double)(l2.b - l1.b) / (l1.m - l2.m);
}

// 새 직선 추가 (기울기는 내림차순이라고 가정)
void add_line(ll m, ll b) {
    Line newLine(m, b);
    
    while (hull.size() >= 2) {
        Line& l1 = hull[hull.size() - 2];
        Line& l2 = hull[hull.size() - 1];
        
        if (intersect(l1, newLine) <= intersect(l1, l2)) {
            hull.pop_back();
        } else {
            break;
        }
    }
    
    hull.push_back(newLine);
}

// x에서의 최소값 쿼리
ll query(ll x) {
    int lo = 0, hi = hull.size() - 1;
    
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        
        if (hull[mid].eval(x) >= hull[mid + 1].eval(x)) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    
    return hull[lo].eval(x);
}

2. 동적 CHT (Dynamic CHT)

쿼리 순서가 x좌표에 대해 정렬되어 있지 않거나, 직선 추가 순서가 기울기에 대해 정렬되어 있지 않은 경우에는 동적 CHT를 사용해야 합니다. 이를 구현하는 대표적인 방법은 Li-Chao 트리나 std::set을 활용한 방법이 있습니다.

다음은 std::set을 활용한 동적 CHT 구현입니다:

struct Line {
    ll m, b;
    mutable ll left; // 이 직선이 최소값을 가지는 왼쪽 끝점
    
    Line(ll _m = 0, ll _b = LLONG_MAX, ll _left = LLONG_MIN) 
        : m(_m), b(_b), left(_left) {}
    
    bool operator<(const Line& other) const {
        return left < other.left;
    }
};

struct DynamicHull {
    multiset<Line> hull;
    
    // 교차점 계산을 위한 정수 나눗셈
    static ll div(ll a, ll b) {
        if (b == 0) return LLONG_MAX;
        return a / b - ((a ^ b) < 0 && a % b);
    }
    
    // 불필요한 직선 제거 로직
    bool isect(multiset<Line>::iterator it) {
        // 구현 생략...
    }
    
    // 새 직선 추가
    void add_line(ll m, ll b) {
        // 구현 생략...
    }
    
    // x에서의 최소값 쿼리
    ll query(ll x) {
        if (hull.empty()) return LLONG_MAX;
        
        auto it = hull.lower_bound(Line(0, 0, x));
        if (it == hull.begin()) return it->m * x + it->b;
        
        --it;
        return it->m * x + it->b;
    }
};

실전 응용: 트리 기반 DP 문제

CHT는 특히 트리 기반의 DP 문제에서 강력한 성능을 발휘합니다. 이런 문제에서는 종종 각 노드의 서브트리에 대한 최적해를 계산해야 하는데, 이때 Small-to-Large 최적화와 함께 CHT를 사용하면 매우 효율적인 해결책을 얻을 수 있습니다.

다음은 트리 DP와 CHT를 결합한 예시 코드입니다:

// 각 노드의 서브트리에 대한 CHT
vector<DynamicHull> cht(n + 1);

// 서브트리 크기 계산
vector<int> subtree_size(n + 1, 0);
function<int(int)> calc_size = [&](int node) {
    subtree_size[node] = 1;
    for (int child : children[node]) {
        subtree_size[node] += calc_size(child);
    }
    return subtree_size[node];
};
calc_size(1);

// 리프 노드부터 루트까지 DP 계산
function<void(int)> solve = [&](int node) {
    // 자식 노드들 먼저 처리
    for (int child : children[node]) {
        solve(child);
    }
    
    // 리프 노드 처리
    if (children[node].empty()) {
        cht[node].add_line(values[node], 0);
        return;
    }
    
    // Small-to-Large 최적화를 위한 자식 정렬
    vector<int> sorted_children = children[node];
    sort(sorted_children.begin(), sorted_children.end(), [&](int a, int b) {
        return subtree_size[a] < subtree_size[b];
    });
    
    // 가장 큰 자식의 CHT를 현재 노드로 복사
    int largest_child = sorted_children.back();
    sorted_children.pop_back();
    cht[node] = move(cht[largest_child]);
    
    // 나머지 자식들의 CHT 병합
    for (int child : sorted_children) {
        // 각 자식에 대한 계산 및 병합
        cht[node].merge(cht[child]);
    }
    
    // 현재 노드에 대한 새 직선 추가
    cht[node].add_line(values[node], calculated_value);
};
solve(1);

CHT 활용 시 주의사항

CHT를 효과적으로 활용하기 위해서는 몇 가지 주의해야 할 점이 있습니다:

오버플로우 주의: 직선의 기울기와 절편, 그리고 교차점 계산에서 정수 오버플로우가 발생할 수 있으므로 적절한 자료형(long long)을 사용해야 합니다.
분모가 0인 경우 처리: 교차점 계산 시 두 직선의 기울기가 같으면 분모가 0이 되므로 이 경우를 적절히 처리해야 합니다.
정밀도 문제: 정수 나눗셈에서 내림/올림을 정확히 처리해야 교차점을 정확하게 계산할 수 있습니다.
Small-to-Large 최적화: 여러 CHT를 병합할 때는 항상 작은 것을 큰 것에 병합하는 방식으로 구현해야 시간 복잡도를 보장할 수 있습니다.

결론

Convex Hull Trick은 특정 형태의 DP 문제를 큰 폭으로 최적화할 수 있는 강력한 기법입니다. 특히 직선 집합에서 최소/최대값을 효율적으로 쿼리해야 하는 상황에서 매우 유용합니다. 트리 DP와 결합하면 더욱 복잡한 문제도 효율적으로 해결할 수 있습니다.

알고리즘 경진대회나 고난도 알고리즘 문제에서 CHT를 마스터하면 한 단계 높은 수준의 문제 해결 능력을 갖출 수 있을 것입니다. 물론 구현이 복잡하고 세부 사항에 주의해야 하지만, 그만큼 강력한 도구이므로 꼭 학습해보시길 권장합니다.

[카테고리:] 미분류

복잡한 알고리즘 문제 해결을 위한 Convex Hull Trick(CHT) 활용하기