Aliens Trick

Aliens Trick, WQS Binary Search, Lagrange Optimization, 에일리언 트릭

정의

Aliens Trick (또는 WQS Binary Search, Lagrange Optimization) 은 “정확히 K 개 선택” 같은 까다로운 제약을 가진 DP 를, 제약을 lambda 페널티로 완화 한 자유 DP + 외부 이분탐색으로 푸는 기법.

IOI 2016 의 “Aliens” 문제에서 유명해져서 이름이 붙었다. 한국식 이름은 “외계인 트릭”. Slope Trick 과 함께 DP 의 볼록성 을 활용하는 대표적인 최적화.

문제 상황과 동기

왜 필요한가

“N 개 중 정확히 K 개를 선택해 비용 최소화” 는 직관적인 DP 상태로 dp[i][k] = i 까지 봤고 k 개 선택한 최소 비용 이다. 전이는 O(N), 상태는 O(NK), 전체 O(N² K) 또는 O(NK²).

N=10^5, K=10^5 일 때 10^10 연산, 시간 초과.

Naive 해법의 한계: K 차원을 명시적으로 들고 가면 상태 공간이 폭발한다.

Aliens Trick 의 돌파구: DP 가 K 에 대해 볼록 (convex or concave) 하면, K 제약을 제거하고 “선택할 때마다 페널티 λ 를 부과” 하는 무제약 DP 를 푼다. 이 DP 는 O(N) 또는 O(N log N). λ 를 이분탐색해 정확히 K 개를 선택하게 만든다. 전체 O(N log V) 또는 O(N log N log V).

10^5 → 10^5 * log(10^6) ≈ 2*10^6, 통과.

전형적 문제

• “N 개 선분 중 K 개를 선택해 덮는 면적 최대화”
• “K 개 그룹으로 나눠 각 그룹 비용의 합 최소화”
• “K 번의 연산으로 배열을 정렬하는 최소 비용”

시각화

핵심 아이디어

원 문제: f(K) = K 개를 선택할 때 최대 / 최소 비용.

DP 가 K 의 함수로 볼록 (concave / convex) 하면, K 제약을 제거 하고 선택할 때마다 페널티 λ 를 부여 한 자유 DP g(λ) = max (f(K) - λK) 를 정의. 이 g 는 K 가 자유롭게 정해진 무제약 DP.

g(λ) = max_K (f(K) - λK)

이는 함수 f(K) + λK 의 위쪽 봉투 (upper envelope) 의 점이다. λ 를 키울수록 g 의 argmax 인 K(λ) 는 단조 감소 (또는 증가). 따라서 λ 에 대해 이분탐색 으로 원하는 K 를 정확히 맞출 수 있다.

핵심 불변량: f(K) 가 K 에 대해 볼록하면 f(K) - λK 의 최댓값을 주는 K 는 λ 가 증가할수록 감소한다 (또는 증가, 부호에 따라). 이 단조성이 이분탐색을 가능하게 한다.

def solve(K):
    lo, hi = 0, MAX_LAMBDA
    while lo < hi:
        mid = (lo + hi) // 2
        chosen, value = solve_unconstrained(lambda=mid)
        if chosen >= K: lo = mid + 1
        else:           hi = mid - 1
    # lambda 에 따라 K 가 정확히 일치하지 않을 수 있음, 끝에서 보정
    return solve_unconstrained(lambda=lo).value + lo * K

구현

아래는 골격 코드. 실제 문제에 맞춰 solve_unconstrained 의 DP 전이를 채워 넣는다.

// O(N log V) 또는 O(N log N log V) (무제약 DP 가 O(N log N) 이면 후자)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// lambda 페널티 하에서 무제약 DP
// 반환: {비용 (페널티 포함), 선택 개수}
pair<ll, int> solve_unconstrained(ll lambda) {
    // 예: dp[i] = i 까지 봤을 때 최소 비용 (선택할 때마다 -lambda)
    // 실제 전이는 문제마다 다름
    // 여기서는 골격만
    ll cost = 0; // 페널티 포함 비용
    int count = 0; // 선택한 개수
    // ... DP 전이 ...
    return {cost, count};
}

// 정확히 K 개를 선택하는 최소 비용
ll solve_with_k(int K) {
    ll lo = -1e9, hi = 1e9; // lambda 범위는 문제마다 조정
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        auto [cost, cnt] = solve_unconstrained(mid);
        if (cnt >= K) lo = mid + 1; // 더 많이 선택, lambda 증가
        else hi = mid - 1;
    }
    auto [final_cost, final_cnt] = solve_unconstrained(lo);
    // 보정: 실제 비용 = (페널티 포함 비용) + lambda * K
    return final_cost + lo * K;
}

int main() {
    int N, K;
    cin >> N >> K;
    // ... 입력 ...
    cout << solve_with_k(K) << "\n";
}

구현 팁

1. lambda 범위: 비용의 절댓값 최댓값으로 설정. 너무 좁으면 답을 못 찾음.
2. tie-break: 같은 비용일 때 K 큰 쪽 / 작은 쪽 우선순위를 일관되게.
3. 부호 주의: 최대화는 concave, 최소화는 convex. 부등호와 페널티 부호를 맞춰야 함.

전제 조건

볼록 / 오목 (convex / concave in K) 이 핵심. f(K) 가 볼록이면 페널티 λK 를 더한 함수는 위로 볼록의 봉투 = 단조성 보장.

볼록 조건: f(K+1) - f(K) 가 K 에 대해 단조 (감소/증가)

볼록이 아니라면 Aliens Trick 적용 불가, 다른 방법 (Knuth Optimization, DnC, Slope Trick 등) 을 고려.

복잡도

항목	값
Unconstrained DP 1 회	O(N) 또는 O(N log N)
λ 이분탐색	O(log V) (V = 페널티 값 범위)
전체	O(N log V) 또는 O(N log N log V)

원래 O(N²), O(NK²) 였던 DP 를 한 단계 낮춰 준다.

함정

1. K 가 정확히 안 맞는 경우

f 의 그래프 위에 정확히 (K, f(K)) 점이 평면에 끼이지 않으면 (collinear 한 점들이 있는 경우) 이분탐색 결과 K(λ) 가 목표 K 를 건너뛴다. 답 보정식: g(λ) + λK.

2. 정수 λ 일 때 동률 처리

여러 K 가 같은 f(K) - λK 값을 줄 수 있다. unconstrained DP 에서 최대 K 를 선호 하도록 tie-break 를 일관되게 둬야 한다.

3. 역추적 (선택한 원소 복원)

마지막 λ 로 unconstrained DP 를 한 번 더 돌리며 backtrack. 단순 값 계산보다 코드가 길다.

4. concave 인지 convex 인지 헷갈림

최대화 문제는 concave (위로 볼록) 이어야 함. 최소화는 convex (아래로 볼록). 부호와 부등호 방향을 끝까지 일관되게.

λ 이분탐색 흐름

flowchart TD
    Start["lo=0, hi=MAX_LAMBDA"] --> Mid["mid = lo + hi / 2"]
    Mid --> UC["solve_unconstrained(mid)"]
    UC --> |"cnt >= K"| IncLo["lo = mid + 1"]
    UC --> |"cnt < K"| DecHi["hi = mid - 1"]
    IncLo --> Check[반복 여부 확인]
    DecHi --> Check
    Check --> |계속| Mid
    Check --> |종료| Ans["정답 = g + lo * K"]

이분탐색 종료 후 g(λ) + λK 보정이 핵심. f(K) 가 collinear (여러 K 가 같은 λ 에 대응) 인 경우에도 이 공식으로 정확한 답을 얻는다.

볼록성 확인 방법

Aliens Trick 적용 전 f(K) 의 볼록성을 확인하는 방법:

1. 수학적 증명: 문제의 구조에서 볼록 / 오목 성질을 분석. 구간 합, 그리디 교환 논증 등.
2. 소규모 브루트 포스: N 이 작을 때 f(K) 값 직접 계산, 2차 차분 확인.

# f(K) 볼록성 검증 (소규모 테스트)
for K in 1..n:
    f[K] = brute_force(K)
for K in 1..n-1:
    delta[K] = f[K+1] - f[K]   # 1차 차분

# delta 가 단조 감소 -> concave (최대화 Aliens)
# delta 가 단조 증가 -> convex (최소화 Aliens)

볼록성이 확인되면 실제 풀이에서 unconstrained DP 를 들고 이분탐색으로 빠르게.

구현 변형: 정수 λ vs 실수 λ

정수 λ: λ 가 정수이면 lo, hi 를 정수로 운영. 대부분의 Codeforces / BOJ 문제.

실수 λ: 비용이 실수이면 lo, hi 를 실수로, 고정 횟수로 수렴 판단.

// 실수 λ 이분탐색 골격
double lo = 0, hi = 1e9;
for (int iter = 0; iter < 200; iter++) {   // 200회면 충분
    double mid = (lo + hi) / 2;
    auto [cost, cnt] = solve_unconstrained(mid);
    if (cnt >= K) lo = mid;
    else hi = mid;
}
// 종료 후: solve_unconstrained(lo).cost + lo * K

eps 대신 고정 횟수를 쓰면 무한 루프 위험 없음.

연관 기법 비교

기법	목적	핵심 아이디어
Aliens Trick	K 제약 DP 가속	λ 페널티 + 이분탐색
Knuth Optimization	구간 DP O(N^3) → O(N^2)	opt 단조성
Divide and Conquer DP	1D1D DP O(N^2) → O(N log N)	opt 단조성
SMAWK	완전 볼록 행렬 최소	row-min 탐색

Slope Trick 과의 차이

항목	Aliens Trick	Slope Trick
다루는 것	f(K) 의 한 점	f(x) 함수 전체
핵심 도구	외부 이분탐색 + 일반 DP	두 개 priority queue
제약 종류	”정확히 K 개”	piecewise-linear 페널티
결과	단일 값	전체 함수

둘 다 볼록성을 활용하지만 다루는 방향이 직교적. 같은 문제를 두 방법 다 풀 수 있는 경우도 있고, 한 쪽만 풀리는 경우도 많다.

BOJ 연습 문제

최적값 구하기

번호	제목	링크
BOJ 19672	Feast	kokoa-lab
BOJ 20090	Aliens (IOI 2016)	kokoa-lab
BOJ 14510	Blazing New Trails	kokoa-lab
BOJ 17439	꽃집	kokoa-lab

역추적

번호	제목	링크
BOJ 18456	Jealous Split	kokoa-lab

다른 출처 연습 문제

출처	제목	링크
Codeforces	Edu Round 79 F	https://codeforces.com/contest/1279/problem/F

참고

• Slope Trick
• 볼록 다각형 접선 최적화