[자료구조 및 알고리즘] 오프라인 쿼리와 Mo's Algorithm

오프라인 쿼리와 Mo's Algorithm

오프라인 쿼리는 쿼리를 즉시 처맇지 않고, 미리 저장해 두었다가 특정 ㅈ건에 따라 일괄적으로 처리하는 알고리즘 설계기법을 말한다. 이 방법은 데이터가 많고 쿼리가 많은 상황에서 효율적인 처리를 가능하게 한다.

 

1. 오프라인 쿼리의 특징

• 즉시 응답하지 않음 - 쿼리를 입력받을 때 바로 처리하지 않고, 나중에 한 번에 처리한다.
• 정렬 기반 최적화 가능 - 쿼리를 정렬하거나 특정 조건에 따라 순서를 조정하여 효율성을 높일수 있다.
• 시간 복잡도 최적화 - 적절한 데이터 구조와 알고리즘을 사용하면 쿼리의 총 실행시간을 줄일 수 있다.

2 . 오프라인 쿼리의 장점

• 배치 처리 - 쿼리를 정렬하거나 재구성한 뒤 효율적으로 처리하므로 전체 실행 시간이 줄어든다.
• 특정 패턴 최적화 - 예를 들어 구간 쿼리나 특정 조건에 따라 순서가 중요한 경우, 쿼리를 미리 정렬하여 처리 시간을 최소화 한다.

3. 대표적인 오프라인 쿼리 알고리즘 - Mo's Algorithm

Mo's Algorithm은 구간 퀄를 효율적으로 처리하는 오프라인 알고리즘이다. 구간 합, 구간 최대값 / 최소값, 특정 범위에서의 빈도 계산 등의 문제에서 사용된다.

 

알고리즘 동작 방식

 

1. 쿼리를 블록 단위로 정렬한다.

• 배열을 √N 크기의 블록으로 나누고, 쿼리를 다음 기준으로 정렬한다.
  • 블록 번호(왼쪽 인덱스 // 블록 크기)
  • 같은 블록 내에서는 오른쪽 인덱스의 크기

2. 정렬된 순서대로 쿼리를 처리하며 필요한 값을 갱신한다.

• 이전 쿼리의 결과를 재활용하여 계산 시간을 줄인다.
• 구간 [L1, R1]에서 [L2, R2]로 이동 시, 기존 결과를 활용하여 추가/제거 작업만 수행

시간 복잡도

• 각 쿼리의 처리는 평균적으로 O( √N ​)이며, 전체 시간 복잡도는 O((N+Q) √N ​)이다.

4. 오프라인 쿼리 코드 및 설명

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;

// 쿼리 구조체
struct Query {
    int L, R, idx; // 왼쪽 인덱스, 오른쪽 인덱스, 쿼리 번호
};

// 결과 저장용 배열
vector<int> results;

// 고유 값 계산을 위한 변수
unordered_map<int, int> freq; // 각 값의 빈도
int unique_count = 0;         // 현재 구간에서의 고유 값 개수

// 현재 값 추가
void add(int x) {
    freq[x]++;
    if (freq[x] == 1) // 빈도가 1이 되면 고유 값 증가
        unique_count++;
}

// 현재 값 제거
void remove(int x) {
    if (freq[x] == 1) // 빈도가 1에서 0으로 줄어들면 고유 값 감소
        unique_count--;
    freq[x]--;
}

int main() {
    // 입력 배열과 쿼리
    int n; // 배열의 크기
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    int q; // 쿼리의 개수
    cin >> q;
    vector<Query> queries(q);

    for (int i = 0; i < q; i++) {
        cin >> queries[i].L >> queries[i].R;
        queries[i].L--; // 0-based indexing
        queries[i].R--;
        queries[i].idx = i; // 쿼리의 순서를 저장
    }

    // 결과 저장 배열 초기화
    results.resize(q);

    // 블록 크기 계산
    int block_size = sqrt(n);

    // 쿼리를 Mo's Algorithm에 따라 정렬
    sort(queries.begin(), queries.end(), [block_size](Query a, Query b) {
        if (a.L / block_size != b.L / block_size) // 블록 번호 기준 정렬
            return a.L / block_size < b.L / block_size;
        return a.R < b.R; // 블록 내부에서는 오른쪽 인덱스 기준 정렬
    });

    // Mo's Algorithm 실행
    int currentL = 0, currentR = -1;
    for (const auto& q : queries) {
        int L = q.L, R = q.R;

        // 현재 구간을 [L, R]로 확장
        while (currentR < R) add(arr[++currentR]);
        while (currentR > R) remove(arr[currentR--]);
        while (currentL < L) remove(arr[currentL++]);
        while (currentL > L) add(arr[--currentL]);

        // 결과 저장
        results[q.idx] = unique_count;
    }

    // 결과 출력
    for (int i = 0; i < q; i++)
        cout << results[i] << endl;

    return 0;
}

 

• 구조체 정의:
  • Query 구조체를 정의하여 쿼리의 범위 [L,R][L, R][L,R]와 쿼리의 순서를 저장
• Mo's Algorithm 정렬:
  • 배열을 정렬할 때 블록 번호와 오른쪽 끝점을 기준으로 정렬
  • 블록 크기는 √N ​로 설정
• add와 remove 함수:
  • add: 현재 값을 구간에 포함시켜 고유 값 개수를 갱신
  • remove: 현재 값을 구간에서 제거하며 고유 값 개수를 갱신
• Mo's Algorithm 처리:
  • 현재 구간 [currentL,currentR]을 쿼리 [L,R]로 설정
  • while 루프를 사용해 구간을 동적으로 확장하거나 축소
• 결과 저장:
  • 각 쿼리의 결과를 results 배열에 저장하고, 쿼리 순서대로 출력

5. 블록이 필요한 이유

• 블록은 Mo's 알고리즘에서 배열 전체를 처리하는 대신 쿼리를 효율적으로 정렬하고 처리하기 위해 작은 덩어리로 나누는 단위이다. 이를 통해 배열의 특정 구간을 효율적으로 처리할 수 있다.
• 블록을 사용하면 L과 R에 따라 구간 이동 비용을 줄이고 쿼리 저렬과 계산을 최적화할 수 있다.
• 일반적으로 배열의 크기 N에 대해 블록 크기는 √N 로 설정