볼록 다각형 접선 최적화

Convex Tangent Optimization, 볼록 다각형 접선 최적화

정의

볼록 다각형의 접선을 이용한 최적화 는 두 종류 비용의 곱 / 합 형태의 trade-off 를 최소화 / 최대화할 때, 모든 가능 해 (x, y) 들이 만드는 평면 점집합의 볼록 헐 (convex hull) 위 접선 을 잡아 답을 찾는 기법.

전형적 문제: minimize A·B where A, B 는 같은 객체 집합에서 정해지는 두 가중치 합. 일반적으로 NP-hard 같지만 볼록 헐 + 접선 분할 로 polynomial.

문제 상황과 동기

곱 최소화는 일반적으로 NP

“N 개 간선 각각에 시간 t_i, 비용 c_i 가 있고, 그 중 N-1 개를 골라 spanning tree 를 만들 때 (sum t_i) · (sum c_i) 최소화” 같은 문제는 일반적으로 NP-hard 다. 두 목적함수의 곱 이기 때문.

Naive 접근: 모든 spanning tree 를 enumerate 해 A·B 계산 → O(N^N) 불가능. 단일 가중치 w_i = alpha·t_i + beta·c_i 의 MST 는 O(M log M) 이지만, alpha, beta 를 어떻게 정할지 모른다.

볼록 다각형 접선 최적화의 돌파구: 모든 가능한 spanning tree 들을 (A, B) 평면에 점으로 찍으면, 그 점집합의 convex hull 위에서만 답을 찾으면 된다. hull 위 점들은 접선 방향 (즉 alpha·A + beta·B 의 최솟값) 을 바꿔가며 MST 를 풀면 얻어진다. 분할정복으로 O(N · M log M) (N = hull 크기, 보통 O(M) 이하).

전형적 문제

• timeismoney (BOJ 5257): spanning tree 의 시간·비용 곱 최소화
• 아티스트 (BOJ 15310): 두 가중치의 곱 최소화
• range-to-range 매칭: 두 집합 간 매칭에서 두 비용의 곱

공통점: 가능한 해들이 2차원 평면에 점으로 표현되고, 그 convex hull 위 접선을 분할정복으로 탐색.

시각화

핵심 아이디어

가능한 해를 (A, B) 좌표로 보면 평면의 점집합. 최소화 A·B 는 원점에서 곡선 xy = k 가 가장 작은 k 에서 접하는 점. 이 점은 항상 점집합의 convex hull 위.

핵심 불변량: convex hull 위의 두 점 P_lo = (A_lo, B_lo), P_hi = (A_hi, B_hi) 사이의 선분 위 또는 아래에 더 좋은 점이 있을 수 있다. 접선 방향 (alpha, beta) = (B_hi - B_lo, A_lo - A_hi) 로 가중치 w = alpha·A + beta·B 의 단일 최적화 (MST 등) 를 풀면 새 점 P_mid 를 얻는다. P_mid 가 선분 아래에 있으면 재귀적으로 [P_lo, P_mid], [P_mid, P_hi] 구간을 분할.

모든 해 (A, B) 의 convex hull H 만 보면 충분
H 의 어떤 두 점을 잇는 *접선* 의 양 끝점 사이에 답이 있다
분할정복: 두 끝점 사이에 답이 있는지 재귀

분할정복 깊이 O(log) 또는 O(N) 단계, 각 단계에서 접선 방향에 따른 MST / 매칭 등 보조 최적화 1 회.

예제 추적

N=3 간선 그래프, 2 개 골라 spanning tree. 각 간선 (t, c): (1, 10), (2, 5), (3, 3).

초기 두 끝점 찾기:
  alpha=1, beta=0 (시간만) → MST = {0, 1}, A=3, B=15, P_lo=(3, 15)
  alpha=0, beta=1 (비용만) → MST = {1, 2}, A=5, B=8, P_hi=(5, 8)

solve(P_lo=(3,15), P_hi=(5,8)):
  접선 방향: (B_hi-B_lo, A_lo-A_hi) = (8-15, 3-5) = (-7, -2)
  가중치: w = -7·A + (-2)·B 최소화 → 7·A + 2·B 최소화
  MST with w = 7·t + 2·c:
    간선 0: 7·1 + 2·10 = 27
    간선 1: 7·2 + 2·5 = 24
    간선 2: 7·3 + 2·3 = 27
  선택: {1, 2}, A=5, B=8, P_mid=(5, 8)
  
  P_mid == P_hi 이므로 새 점 없음 → [P_lo, P_hi] 사이에서 종료

다시 alpha=-1, beta=0:
  ... (반복하면 hull 의 모든 점 발견)

최종 hull: {(3,15), (5,8)} 등
곱 최소: 3·15=45 vs 5·8=40 → 답 40

응용

1. timeismoney 류

각 간선에 시간 t, 비용 c. 둘의 곱 (또는 합·곱 조합) 최소화 spanning tree. 접선 방향 에 따라 가중치 = α·t + β·c 의 MST 풀이.

2. 아티스트

가중치 두 개가 있는 객체 집합에서 비용·시간 곱 최소화.

3. 뚫기 / 도로 건설

비슷한 trade-off 문제.

구현

다음은 분할정복으로 convex hull 위 점들을 찾아 A·B 최소화를 푸는 골격. solve_single(alpha, beta) 는 문제에 맞는 MST / 매칭 등을 호출.

// O(N · M log M), O(M) 공간. 가능 해들의 convex hull 위 접선 분할정복
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Point { ll A, B; };

// alpha·A + beta·B 최소화하는 MST (또는 매칭 등) 의 (A, B) 반환
// 문제마다 구현 다름. 여기서는 skeleton
Point solve_single(ll alpha, ll beta) {
    // 예: Kruskal 로 간선 가중치 = alpha·t + beta·c 의 MST
    // ...
    return {total_A, total_B};
}

ll best_product = LLONG_MAX;
Point best_point;

void solve(Point lo, Point hi) {
    if (lo.A == hi.A && lo.B == hi.B) return; // 같은 점
    
    // 접선 방향: (B_hi - B_lo, A_lo - A_hi)
    ll alpha = hi.B - lo.B;
    ll beta = lo.A - hi.A;
    
    Point mid = solve_single(alpha, beta);
    
    // mid 가 lo-hi 선분 아래에 있는지 체크 (cross product)
    // (mid - lo) x (hi - lo) > 0 이면 아래쪽
    ll cross = (mid.A - lo.A) * (hi.B - lo.B) - (mid.B - lo.B) * (hi.A - lo.A);
    
    if (cross > 0) {
        // 새 점 발견, 재귀
        solve(lo, mid);
        solve(mid, hi);
    }
    
    // 현재 mid 의 곱 갱신
    ll prod = mid.A * mid.B;
    if (prod < best_product) {
        best_product = prod;
        best_point = mid;
    }
}

int main() {
    int N, M; cin >> N >> M;
    // 간선 입력 등 ...
    
    // 초기 두 끝점 찾기
    Point p_lo = solve_single(1, 0); // A 최소
    Point p_hi = solve_single(0, 1); // B 최소
    
    best_product = min(p_lo.A * p_lo.B, p_hi.A * p_hi.B);
    best_point = (p_lo.A * p_lo.B < p_hi.A * p_hi.B) ? p_lo : p_hi;
    
    solve(p_lo, p_hi);
    
    cout << best_product << "\n";
}

구현 팁

1. 초기 끝점: alpha=1, beta=0 과 alpha=0, beta=1 로 각각 A 최소, B 최소 해를 구해 두 끝점으로 삼는다.
2. cross product 체크: 새 점이 선분 아래 있는지 외적으로 판정. 오차 없이 정수 연산.
3. 종료 조건: 두 점이 같거나, cross product ≤ 0 이면 더 이상 분할 불가.
4. 문제별 solve_single: MST 는 Kruskal, 매칭은 Hungarian 등 문제에 맞게 구현.

복잡도

단계	비용
한 번의 단일 가중치 최적화	O(M log M) (MST 의 경우)
분할정복 깊이	O(N) (hull 크기)
전체	O(N · M log M)

Aliens Trick 과의 비교

항목	Aliens	볼록 다각형 접선
trade-off 형태	”정확히 K 개”	A·B 곱 / 합
차원	1D (K)	2D (A, B)
핵심	lambda 이분탐색	접선 normal
구현	단순	분할정복

둘 다 볼록성 + 단일 가중치 변환 이라는 공통 정신.

함정

1. 정수 접선 정렬

α, β 가 정수여야 정확한 비교. 실수면 오차.

2. 두 점 거리 0

분할정복 종료 조건. 두 점이 같으면 더 분할 불가.

3. 점집합이 비볼록일 때

평면 점집합의 contour (Pareto frontier) 만 hull 로. 내부 점들은 답이 될 수 없음.

4. MST / 매칭 의존

각 분할 단계에서 부른 최적화 (MST, 매칭, …) 가 정확해야 전체 정확.

BOJ 연습 문제

번호	제목	링크
BOJ 15310	아티스트	kokoa-lab
BOJ 5257	timeismoney	kokoa-lab
BOJ 25009	뚫기	kokoa-lab

참고

• Aliens Trick
• Slope Trick
• 민코프스키 합 DP
• Bulldozer Trick