알고리즘 대회에서 자주 등장하는 난수 배열 생성 방식과 std::nth_element를 활용한 효율적인 문제 해결 기법을 살펴본다. 특히 대용량 데이터에서 순위 기반 쿼리를 처리하는 방법이 핵심이다.

Xorshift RNG 구현

다음은 경량 의사난수 생성기(Pseudo-Random Number Generator)의 한 종류인 xorshift 계열 구현이다. 세 개의 상태 변수를 이용하며, 비트 연산으로 빠르게 난수를 생성한다.

static unsigned state_x, state_y, state_z;

unsigned xorshift_rng() {
    unsigned temp;
    state_x ^= state_x << 16;
    state_x ^= state_x >> 5;
    state_x ^= state_x << 1;
    temp = state_x;
    state_x = state_y;
    state_y = state_z;
    state_z = temp ^ state_x ^ state_y;
    return state_z;
}

이 생성기는 선형 피드백 시프트 레지스터(LFSR)의 변형으로, 하드웨어 친화적인 구조 덕분에 시 효율이 뛰어나다.

std::nth_element의 동작 원리

C++ 표준 라이브러리의 std::nth_element는 퀵셀렉트(Quickselect) 알고리즘을 기반으로 하며, 평균 O(n) 시간에 k번째 원소를 정확히 찾아 해당 위치에 배치한다. 중요한 점은 전체 정렬이 아닌 부분적 순서만 보장한다는 것이다.

// 구문: nth_element(first, nth, last)
// [first, nth)의 모든 원소 <= *nth <= [nth, last)의 모든 원소

int dataset[] = {7, 1, 9, 3, 5, 8};
std::nth_element(dataset, dataset + 3, dataset + 6);
// 결과 예시: {1, 3, 5, 7, 9, 8} 또는 {3, 1, 5, 7, 9, 8}
// dataset[3] == 7은 확정, 좌우 구간은 미정렬

적용 예제 1: 최대 LCM 쌍 탐색

문제 개요: 길이 n ≤ 2×10⁶의 난수 배열에서 두 수의 최소공배수(LCM)가 최대가 되는 값을 구한다.

관찰: 서로소인 두 수의 LCM은 그 곱과 같다. 큰 수들끼리 서로소일 가능성이 높으므로, 상위 값들에 집중하면 된다. 수학적 직관에 따라 상위 100개만 추출하여 검증한다.

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const int MAX_SIZE = 1e7 + 10;

unsigned sx, sy, sz;
ull values[MAX_SIZE];

unsigned generate_random() {
    unsigned t;
    sx ^= sx << 16;
    sx ^= sx >> 5;
    sx ^= sx << 1;
    t = sx;
    sx = sy;
    sy = sz;
    sz = t ^ sx ^ sy;
    return sz;
}

ull compute_lcm(ull p, ull q) {
    if (p < q) swap(p, q);
    ull a = p, b = q;
    while (b != 0) {
        ull r = a % b;
        a = b;
        b = r;
    }
    // a는 최대공약수, LCM = p / GCD * q로 오버플로우 방지
    return p / a * q;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    for (int tc = 1; tc <= test_cases; ++tc) {
        int n;
        cin >> n >> sx >> sy >> sz;
        
        for (int i = 0; i < n; ++i) {
            values[i] = generate_random();
        }
        
        ull best = 0;
        const int SAMPLE = 100;
        
        if (n > SAMPLE) {
            int cutoff = n - SAMPLE;
            nth_element(values, values + cutoff, values + n);
            
            for (int i = cutoff; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    ull cand = compute_lcm(values[i], values[j]);
                    if (cand > best) best = cand;
                }
            }
        } else {
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    ull cand = compute_lcm(values[i], values[j]);
                    if (cand > best) best = cand;
                }
            }
        }
        
        cout << "Case #" << tc << ": " << best << "\n";
    }
    return 0;
}

적용 예제 2: 다중 순위 쿼리 최적화

문제 개요: 길이 n ≤ 10⁷의 배열에서 여러 개의 순위 위치에 해당하는 원소들을 동시에 구한다.

핵심 최적화: 단순히 m번의 nth_element를 호출하면 O(m×n)로 시간 초과가 발생한다. 쿼리를 내림차순으로 정렬한 뒤, 구간을 점진적으로 축소하는 방식으로 중복 연산을 제거한다.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e7 + 10;
const int MAX_Q = 110;

struct RankQuery {
    int position;
    int original_idx;
    bool operator<(const RankQuery& o) const {
        return position > o.position; // 내림차순
    }
};

unsigned ax, ay, az;
unsigned raw_data[MAX_N];
unsigned answer[MAX_Q];
RankQuery queries[MAX_Q];

unsigned rng_generator() {
    unsigned tmp;
    ax ^= ax << 16;
    ax ^= ax >> 5;
    ax ^= ax << 1;
    tmp = ax;
    ax = ay;
    ay = az;
    az = tmp ^ ax ^ ay;
    return az;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int dataset_count = 0;
    int n, q;
    
    while (cin >> n) {
        cin >> q >> ax >> ay >> az;
        
        for (int i = 0; i < q; ++i) {
            cin >> queries[i].position;
            queries[i].original_idx = i;
        }
        sort(queries, queries + q); // position 큰 순서
        
        for (int i = 0; i < n; ++i) {
            raw_data[i] = rng_generator();
        }
        
        // 경계 확장: 마지막 쿼리 이후는 전체 범위
        int right_bound = n;
        
        cout << "Case #" << ++dataset_count << ":";
        
        for (int i = 0; i < q; ++i) {
            int target = queries[i].position;
            // 구간 [target, right_bound)에서 target 위치 확정
            nth_element(raw_data, raw_data + target, raw_data + right_bound);
            answer[queries[i].original_idx] = raw_data[target];
            right_bound = target; // 다음 반복의 검색 범위 축소
        }
        
        for (int i = 0; i < q; ++i) {
            cout << " " << answer[i];
        }
        cout << "\n";
    }
    return 0;
}

성능 비교 및 주의사항

방식	시간 복잡도	적용 상황
완전 정렬	O(n log n)	전체 순위가 필요할 때
단일 nth_element	O(n)	하나의 순위만 필요할 때
구간 축소 nth_element	O(n) 평균	다중 순위, 범위가 겹칠 때
우선순위 큐	O(n log k)	상위 k개가 필요할 때

std::nth_element는 인트로셀렉트(Introselect) 변형을 사용하는 구현체가 많아, 최악의 경우에도 O(n log n)을 보장한다. 다만 이터레이터 무효화 규칙을 주의해야 하며, nth_element 호출 후 해당 범위의 이터레이터는 재검증이 필요하다.