종합 문제 해결 전략

정상급 문제는 "알고리즘 고르기"가 아니다

골드~플래티넘까지는 "이건 다익스트라, 저건 DP"처럼 분류 가 통한다. 하지만 루비/마스터급 문제는 알려진 알고리즘이 그대로 들어맞지 않는다. 핵심은 관찰(observation) 로 문제를 다른 문제 로 바꾸는 것. 이 강의는 그 사고 루틴을 정리한다.

1. 작은 케이스를 손으로 풀어라

\(n = 1, 2, 3\)을 직접 계산하고 수열을 OEIS에 넣어 보라. 답의 패턴 이 보이면 절반은 풀린 것이다. 패턴 → 추측(conjecture) → 증명 또는 반례.

예: "격자에서 단조 경로 수"를 손으로 세면 \(\binom{n+m}{n}\)이 보인다. 그러면 DP가 아니라 조합 공식이 답.

2. 불변량(invariant)을 찾아라

연산이 반복될 때 변하지 않는 양 이 있는가? 불변량은 "도달 가능성"과 "불가능성 증명" 모두에 강력하다.

예: 15-퍼즐의 가환성 판정 = 순열의 패리티 불변량. 어떤 배치는 절대 도달 불가능함을 패리티로 증명.

전형 불변량: 패리티, 합 \(\bmod k\), 색칠(체스판), XOR 값(님버), 위상량(감김 수).

3. 단조성과 이분 탐색

"답이 \(X\)로 가능하면 \(X+1\)도 가능"한 단조성이 보이면, 답을 이분 탐색 하고 판정 문제로 바꾼다(parametric search). 최적화 → 판정 변환은 만능에 가깝다.

$$ \text{최대화 } \min(\cdot) \;\Rightarrow\; \text{"모든 값이 } X \text{ 이상 가능한가?" 이분.} $$

4. 쌍대성(duality)으로 뒤집어라

문제를 반대편 에서 보라.

• 최대 흐름 ↔ 최소 컷.
• 최대 매칭 ↔ 최소 정점 커버(König, 이분).
• LP 최대화 ↔ 쌍대 최소화.
• "선택" ↔ "제거"(여집합으로 세기).

직접 풀기 어려운 양을 쌍대량으로 바꾸면 구조가 단순해질 때가 많다.

5. 환원(reduction)

이 문제가 내가 아는 문제로 바뀌는가?

• 구간/순서 문제 → 그래프(위상정렬, 컴포넌트).
• 제약 만족 → 2-SAT, 차분 제약(Bellman-Ford).
• "동시에 두 제약" → 매트로이드 교집합/플로우.
• 카운팅 → 생성 함수, 포함배제.

예: "변수 쌍 (a∨b) 절들" → 함의 그래프의 SCC = 2-SAT.

6. 대칭과 정규화

답이 대칭이면 대표 하나만 세고 곱한다(번사이드/폴리아). 입력을 정렬·회전·반사로 정규형 으로 바꾸면 경우의 수가 폭발적으로 줄어든다.

사고 체크리스트

다음 강의에서 이 루틴을 구체적 미니 문제들에 적용한다.

사례 1: "최댓값을 최소화" → 이분 + 판정

문제. \(n\)개의 짐을 \(k\)개의 트럭에 순서를 지켜 나눠 싣는다. 각 트럭 적재량의 최댓값 을 최소화하라.

전략. "최댓값 \(\le X\)로 가능?"은 단조(크면 항상 가능). 그러면 \(X\)를 이분 탐색하고, 판정은 그리디(\(X\)를 넘기 전까지 한 트럭에 채우고 넘으면 새 트럭).

bool feasible(vector<int>& a, int k, long long X){
    long long cur=0; int used=1;
    for(int v : a){
        if(v > X) return false;
        if(cur + v > X){ used++; cur = v; }
        else cur += v;
    }
    return used <= k;
}
// lo=max(a), hi=sum(a) 사이 이분

직접 분할 DP(\(O(n^2\ k)\))보다 \(O(n \log \text{sum})\)로 단순·빠르다. "최적화를 판정으로" 변환의 전형.

사례 2: 불변량으로 불가능 증명

문제. \(3 \times 3\) 격자에 토글 게임: 한 칸을 누르면 자신과 상하좌우가 뒤집힌다. 모두 켜진 상태에서 시작해 모두 끄기가 가능한가?

전략. 각 칸에 가중치 \(w_{ij} \in \{0,1\}\)를 붙여, 한 번의 누름이 바꾸는 칸들의 \(\sum w\)가 항상 짝수가 되도록 \(w\)를 고른다. 그러면 "전체 패리티 \(\sum_{\text{on}} w\)"가 불변량. 시작과 목표의 불변량이 다르면 절대 불가능.

이는 \(\mathbb{F}_2\) 선형대수로 일반화된다: 누름 벡터들이 생성하는 부분공간에 (시작⊕목표)가 속하는가 = 가우스 소거.

// 각 누름 = F2 벡터, 목표차이 = b. Ax = b 해 존재? (가우스 소거)

사례 3: 여집합으로 세기 (쌍대)

문제. \(1..n\) 순열 중 고정점이 하나도 없는 것(교란순열) 수.

전략. "고정점 없음"을 직접 세기 어렵다. 포함배제로 여집합(적어도 하나 고정)을 빼라.

$$ D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n-k)! = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. $$

"적어도 \(k\)개 고정"을 더하고 빼는 것이 직접 세기보다 쉽다. 쌍대/여집합 사고의 정수.

사례 4: 그래프로 환원

문제. 부등식 제약 \(x_b - x_a \le c\)들의 집합이 동시에 만족 가능한가? 가능하면 한 해를 구하라.

전략. 각 제약 \(x_b - x_a \le c\)를 간선 \(a \to b\)(가중 \(c\))로. 차분 제약 시스템(difference constraints) = 최단경로. 음수 사이클이 있으면 모순(불가능), 없으면 Bellman-Ford의 최단거리가 한 해.

// 가상 정점 0에서 모든 노드로 0-간선, Bellman-Ford
// 음수 사이클 → 불가능, 아니면 dist[]가 해

"제약 만족 → 그래프 최단경로/2-SAT/플로우" 환원의 대표.

사례 5: 대칭으로 폭발 줄이기

문제. 회전을 같은 것으로 볼 때, \(n\)개 구슬을 \(m\)색으로 칠하는 목걸이 수.

전략. 번사이드 보조정리: 회전군 \(C_n\)의 각 원소가 고정하는 칠하기 수의 평균.

$$ \frac{1}{n}\sum_{d \mid n} \varphi(d)\, m^{n/d}. $$

대칭을 고려해 나누는 대신, 군 작용의 고정점 평균으로 정확히 센다.

메타 교훈

루비/마스터 문제 풀이 = 번역의 연쇄다. "이상한 문제 → 관찰 → 알려진 구조". 알고리즘 암기보다, 위 다섯 변환(이분/불변량/여집합/환원/대칭)을 반사적으로 시도하는 습관이 실력을 가른다. 막히면 항상: 더 작게, 다르게, 반대로 보라.