제약 조건을 읽고 바로 알고리즘을 알 수 있다: 제다이 가이드

Source: Dev.to

여정이 시작된다 (“왜”)
나는 처음에 경쟁 프로그래밍 문장을 보고 뇌가 단락되는 느낌을 받은 순간을 여전히 기억합니다. 문제는 “길이 n의 배열이며 각 원소는 최대 10⁹이고, 그 중 합이 k로 나누어 떨어지는 짝을 count 해야 한다고 말했습니다. 나는 먼저 브루트 포스 루프를 적어보았고, 그다음 정렬로 바꾸었고, 해시 맵을 시도했으며… 20분 후에도 빈 에디터를 바라보며 숨은 트릭을 놓쳤는지 의문했어요.”
당신도 그런 경험을 한 적이 있나요? 당신은 혼자가 아닙니다. 실제 우리가 마주치는 진짜 용은 구문이나 언어 특성이 아니라, 제약을 소음으로 여기게 만드는 정신적 블록입니다. 최고의 코더들은 문제를 읽은 뒤 바로 코딩을 시작하지 않고, 먼저 제약을 읽고 그 안에서 알고리즘이 속삭이는 것을 듣고는 키보드를 친다.
나는 몇 시간 동안 무의미한 문제 때문에 막혀 있던 늦은 밤 연습 세션 중에 돌파구를 찾았다. 그때 나는 깨달았다: 한 차원은 매우 작고, 다른 차원은 매우 크다는 불일치가 “단축이 존재한다”는 소리를 질렀다. 드디어 그것을 보았을 때, 마치 매트릭스에서 네오가 총알을 피하는 것처럼 모든 것이 서서히 느려졌고, 해답이 자연스럽게 떠올랐다.

계시 (통찰)
이제 나는 단계별로 바로 사용할 수 있는 정확한 정신적 프레임워크를 사용하고 있다. 코드를 한 줄도 쓰기 전에 이 빠른 체크리스트를 실행해 보라.

제약 패턴
보통 의미는
전형적인 알고리즘

n ≤ 10⁵, 값 ≤ 10⁶
입력은 크지만 값이 인덱싱하기에 충분히 작다
계수 정렬 / 빈도 배열 / prefix sum

n ≤ 10⁵, 값 ≤ 10⁹
값이 직접 인덱싱하기에 너무 크지만 n은 비교적 작다
해시 맵 (unordered_map / dict)으로 빈도 관리

n ≤ 2000
O(n²) 연산이 충분함 (약 4백만 연산)
조기 종료 브루트 포스 또는 DP

n ≤ 10⁵, k ≤ 10⁵
모듈로 혹은 나머지 제약이 나타난다
남은값(r)별 버킷을 만들고 합친다

n ≤ 10⁵, 전체 테스트 케이스 n 합 ≤ 10⁶
전체 작업이 거의 선형이어야 한다
단일 패스, O(n) 혹은 O(n log n)

n ≤ 10⁵, 쿼리 ≤ 10⁵, 정적 배열
다수의 범위 쿼리, 업데이트 없음
prefix sum, Sparse Table, 혹은 세그먼트 트리

n ≤ 10⁵, 쿼리와 업데이트 동시
점Updates와 범위 쿼리가 모두 필요함
Fenwick 트리(BIT) 혹은 세그먼트 트리

그래프, m ≤ 2·10⁵, n ≤ 2·10⁵
희소 그래프
BFS/DFS, 유니온 파인드, 힙을 이용한 다익스트라

그래프, m ≈ n²
밀집 그래프
Floyd‑Warshall 또는 인접 행렬 DP

문자열 길이 ≤ 10⁵, 알파벳이 작음
작은 알파벳으로 카운팅/트라이 트릭 활용 가능
계수 정렬, 트라이, 혹은 자동기

문자열 길이 ≤ 10⁵, 알파벳이 큼
해싱 또는 접미사 구조가 필요함
롤링 해시, Suffix Array, Z-함수

정답은 64비트에 맞지만 중간값이 오버플로우할 수 있음
오버플로우를 주의하고 long long / bigint 사용
언어가 허용하면 128비트 사용, 그렇지 않으면 분할

The key is 패턴 매칭: 각 제약이 복잡성을 적절한 수준으로 유지하도록 해줄 데이터 구조를 알려준다. 작은 값 범위가 보이면 “빈도 배열”, 큰 값 범위이지만 n이 작다면 “해시 맵”, 모듈로 혹은 나눗셈이 보이면 “남은ders별 버킷”을 떠올려라.
이 표를 내면에 새기면서 나는 추측을 그만두었다.Bullet points를 스캔하고 맞는 행에 체크하면서 알고리즘은 거의 스스로 쓰여졌다.

힘을 휘두르다 (코드와 예시)
이제 이 프레임워크가 있을 때, 내가 이전에 막혔던 실제 문제를 살펴보자.

문제 명세 (요약)
주어진 배열 a의 길이 n(1 ≤ n ≤ 2·10⁵)과 정수 k(1 ≤ k ≤·10⁵)가 있을 때, (i, j) 쌍의 개수를 구한다.

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if(!(cin >> n >> k)) return 0;
    vector a(n);
    for (int &x : a) cin >> x;

    vector cnt(k, 0);
    for (int x : a) cnt[x % k]++;

    long long ans = 0;
    // pairs where both remainders are 0
    ans += cnt[0] * (cnt[0] - 1) / 2;

    // if k is even, handle the middle remainder separately
    if (k % 2 == 0) {
        ans += cnt[k/2] * (cnt[k/2] - 1) / 2;
    }

    // pair r with k-r for 1 <= r < k/2 (or < (k+1)/2 when k odd)
    int limit = (k % 2 == 0) ? k/2 : (k/2)+1;
    for (int r = 1; r < limit; ++r) {
        ans += cnt[r] * cnt[k - r];
    }

    cout << ans << '\n';
    return 0;
}

왜 이것이 작동하는가:  
문제를 O(n²)에서 O(n + k) 로 줄였으며, 여기서 k보다 작은 범위의 remainders만 고려했음.  
`k ≤ 10⁵`이라 빈도 배열을 할당하는 것이 매우 쉽다.  

- 특수 caso 처리가 더블 카운팅을 방지하고 “자신 짝” 함정을 피한다.  

피해야 할 흔한 함정  

**Forgetting the `r == 0` case** – you’ll miss pairs where both numbers are individually divisible by `k`. → "`r == 0`을 잊으면 k로 나누어 떨어지는 두 숫자 짝을 놓친다."  
**Double‑counting when `k` is even** – the remainder `k/2` pairs with itself, not with a distinct counterpart. → "k가 짝수일 때 더블 카운팅이 발생한다. `k/2`는 자체와 짝을 이루고, 다른 값과 짝하지 않는다."  
**Using `int` for the answer** – the number of pairs can be up to ~2·10¹⁰, which overflows a 32‑bit int. Use `long long` (or `int64_t`). → "`int`를 사용하면 답이 최대 약 2·10¹⁰이 되어 32비트 정수형으로 오버플로우가 발생한다. `long long`(또는 `int64_t`)을 사용한다."

왜 이 새로운 힘이 중요한가  
이 제약 우선 마인드셋을 갖추면 문제 설명을 볼 때마다 미로에 빠지는 느낌을 받지 않는다. 대신,  

**몇 초 안에 최적 데이터 구조를 파악한다 — ‘맵을 쓰자, 트리를 쓰자, 브루트 포스라 하자’와 같은 고민을 할 필요 없이.**  
**버그를 적게 만든다 — 제약이 직접 알고리즘을 결정하므로 엣지 케이스를 놓칠 확률이 낮아진다.**  
**코딩을 즐긴다 — 제약이 속삭이는 순간, 마치 게임의 비밀 레벨을 해금하는 느낌이다.**

대회에 들어가서 문제 앞 두 줄만 보고 페닝윅 트리, 트라이, 혹은 간단한 빈도 배열 중 무엇을 쓰면 될지 이미 알 수 있다. 그것이 좋은 프로그래머를 훌륭한 프로그래머로 바꾸는 자신감이다.  

**당신의 차례 – 작은 모험**  
새로운 직관을 시험해볼 작은 과제를 제시한다: `n` (≤ 10⁵) 개의 정수, 각각 ≤ 10⁶이며, `q` (≤ 10⁵) 개의 쿼리를 받아 `[l, r]` 구간에 있는 소수 개수를 답한다.  
제약을 읽고 적절한 기법을 선택해 솔루션을 작성하라. 작성이 끝나면 주석에 네 접근 방식을 댓글로 올려라 — 내가 어떻게 프레임워크를 사용하는지 보고 싶다!  
행운스러운 코딩을, 제약이 언제나 твоём 가이드가 되길. 🚀