인터랙티브와 구성 문제

두 가지 비표준 문제 유형

대부분의 문제는 "입력 → 출력"이다. 그러나 정상급 셋에는 두 가지 변종이 자주 나온다.

• 인터랙티브(interactive): 정적 입력이 없고, 판정기와 대화 하며 질의를 던지고 답을 받는다. 질의 횟수에 상한이 있다.
• 구성(constructive): "조건을 만족하는 어떤 것을 직접 만들어라". 존재 증명이 곧 알고리즘이 된다.

이 강의는 인터랙티브에, 다음 강의는 구성에 집중한다.

인터랙티브의 기본 규약

• 질의를 출력하고 즉시 flush(버퍼 비우기). 안 하면 데드락.
• 판정기의 응답을 읽고 다음 질의를 정한다.
• 질의 횟수/형식 위반은 즉시 오답(WA/IE).

cout << "? " << x << endl;       // endl이 flush를 포함
// 또는: cout << "? " << x << "\n"; cout.flush();
int res; cin >> res;             // 판정기 응답

정보 이론 하한

인터랙티브의 질의 횟수 제한은 보통 정보량 으로 정해진다. 답의 후보가 \(N\)개고 한 질의가 \(b\)비트(예: yes/no는 1비트)를 주면, 최소

$$ \lceil \log_b N \rceil $$

번의 질의가 필요하다. 예: 1..N에서 숨은 수 맞히기, yes/no 질의 → \(\lceil \log_2 N \rceil\). 이 하한을 달성 하는 전략(이분 탐색)을 설계한다.

적응적 판정기(adaptive adversary)

가장 까다로운 점: 많은 인터랙티브 판정기는 적응적이다. 즉 답을 미리 고정하지 않고, 너의 질의에 가장 불리하게 답을 나중에 정한다. 단, 이미 한 답과 모순되지 않는 한도 내에서.

비유: 숨은 수 맞히기에서 판정기가 수를 안 정해 두고, 매번 "아직 가능한 후보 집합"이 가장 크게 남도록 yes/no를 고른다.

따라서 "운 좋게 빨리 맞히기"는 통하지 않는다. 최악의 후보 집합을 매 질의마다 최대로 줄이는 전략(이분/삼분 탐색, 결정 트리 균형화)이 정답이다.

적대적 분석으로 전략 설계

전략의 옳음은 "적이 어떻게 답하든 \(Q\)번 내 확정"을 보이는 것. 보통 잠재 함수(potential) = 남은 후보 수 또는 불확실성. 각 질의가 잠재 함수를 일정 비율 이상 줄이도록 설계한다.

흔한 패턴

• 이분 탐색형: 숨은 값/경계 찾기.
• 그래프 탐색형: 미지의 그래프를 질의로 복원(차수/연결성 질의).
• 비교 기반: 정렬류, "둘 중 큰 것?" 질의 횟수 최소화.
• 이진 인코딩: 한 질의에 여러 비트 묶어 정보량 극대화.

구현 체크리스트

• 매 출력 후 flush(endl 또는 명시적 flush). 미스 시 TLE/데드락.
• 질의 횟수를 카운트하고 상한 직전에 안전하게 종료.
• 판정기의 "끝/오답 신호"(예: -1 응답)를 받으면 즉시 exit.
• 로컬 테스트용 가짜 판정기(특히 적응적 버전)를 만들어 검증.

다음 강의에서 구성 문제와 "증명을 알고리즘으로 바꾸기"를 본다.

구성 문제의 본질

"조건 \(C\)를 만족하는 객체를 출력하라(없으면 -1)." 채점은 네가 만든 것 이 \(C\)를 만족하는지로 한다(정답이 유일하지 않음). 핵심 사고: 존재 증명을 그대로 구성 절차로 바꾼다. 수학에서 "존재한다"의 구성적 증명이 곧 코드다.

사례 1: 합이 같은 두 그룹으로 분할

문제. \(1, 2, \dots, n\)을 합이 같은 두 집합으로 나눠라(가능하면).

관찰. 총합 \(\frac{n(n+1)}{2}\)가 홀수면 불가능(패리티 불변량). 짝수면 가능 — 그리고 구성 도 쉽다: 큰 수부터 부족한 쪽에 넣는 그리디, 또는 연속 4개씩 \(\{a, a+3\}/\{a+1, a+2\}\)로 짝지어 균형.

// 총합/2 = target. 큰 수부터 target 채우는 그리디로 한 집합 구성
long long total = 1LL*n*(n+1)/2;
if(total % 2) { puts("-1"); return; }
long long need = total/2;
for(int v=n; v>=1; v--) if(need >= v){ groupA.push_back(v); need -= v; }

증명("짝수면 항상 가능")이 그리디의 정당성을 보장한다.

사례 2: 인접 차이가 모두 다른 순열

문제. \(1..n\)의 순열 \(p\)로 \(|p_{i+1}-p_i|\)가 전부 서로 다르게 만들어라.

구성. \(1, n, 2, n-1, 3, \dots\) 지그재그. 차이는 \(n-1, n-2, n-3, \dots, 1\)로 모두 다름. 패턴을 발견하고 왜 차이가 단조 감소 하는지 증명하면 끝.

int lo=1, hi=n;
for(int i=0;i<n;i++) cout << (i%2==0 ? lo++ : hi--) << " ";

작은 케이스로 패턴 추측 → 일반 증명 → 출력. 전형적 흐름.

사례 3: 그래프 구성 (차수열 실현)

문제. 주어진 차수열 \(d_1 \ge \dots \ge d_n\)을 갖는 단순 그래프를 만들어라(가능하면).

도구. 에르되시–갈라이 정리 / 하벨–하키미 알고리즘. 후자는 구성적:

가장 큰 차수 \(d_1\)인 정점을, 그 다음으로 큰 \(d_1\)개 정점에 연결하고 각 차수를 1씩 줄인 뒤 재귀.

// 매 단계 차수 내림차순 정렬 → 최대 정점을 상위 d개에 연결
while(true){
    sort(deg.rbegin(), deg.rend());
    if(deg[0]==0) break;            // 모두 0 → 완성
    int d = deg[0]; deg[0]=0;
    for(int i=1;i<=d;i++){
        if(i>=(int)deg.size() || deg[i]==0){ puts("-1"); return; } // 불가능
        deg[i]--; addEdge(...);
    }
}

정리의 증명(가장 큰 차수를 상위 정점에 연결해도 실현 가능성이 보존됨, exchange argument)이 알고리즘의 정당성이다.

사례 4: 적대적 인터랙티브 + 구성

일부 문제는 인터랙티브 이면서 구성이다: 질의로 정보를 모아 답을 짓는다. 예: 미지의 트리를 거리 질의로 복원. 적응적 판정기를 가정하고, 각 질의가 가능한 트리 후보를 충분히 줄이는지 분석한다. 구성 절차 자체가 "어떤 응답이 와도 모순 없는 트리를 만들 수 있다"는 불변량 을 유지해야 한다.

구성 문제 공략 루틴

핵심 교훈

• 구성 문제는 "유일 정답 맞히기"가 아니라 "하나라도 짓기". 가장 단순한 구성을 노려라(지그재그, 그리디, 재귀 분할).
• 불가능 판정은 거의 항상 불변량/패리티/세는 논증 으로.
• 인터랙티브는 적응적 적 을 가정하고 최악 후보 절감을 보장하라. flush를 잊지 말 것.
• 항상 자문: "이 증명 을 코드로 옮길 수 있는가?" 옮길 수 있으면 그게 답이다.