226. Offline Query

이제부터는 익숙해져야 하는 $7$가지 주제를 차례로 소개하려고 한다. 이 주제들은 대회나 코딩 테스트를 가리지 않고 언제든지 등장할 수 있으며 어떤 유형의 문제와도 결합이 가능하다.

그중에서 첫 번째로 살펴볼 유형은 오프라인 쿼리이다. 그러면 먼저 쿼리가 무엇인지부터 살펴보자.

알고리즘 문제에서 쿼리(Query)는 데이터에 행해지는 반복되는 연산을 의미한다. 이때 데이터는 그래프, 집합, 선형 등 특정한 형태를 가지며 여러 값이 아닌 정수나 실수 하나의 형태로도 존재할 수 있다. 또한 연산은 종류에 따라 추가(Create), 조회(Read), 수정(Update), 삭제(Delete) 등으로 구분할 수 있다. 넓은 의미에서 SQL의 쿼리와 유사한 측면도 있으나 실제 데이터베이스를 건드리는 것이 아니기 때문에 물리 계층과 관련이 없고, 관계형 모델뿐 아니라 다양한 구조에 연산을 적용한다는 차이가 있다.

예시를 통해 알아보기로 하자.

BOJ 18917. 수열과 쿼리 38 (Silver III)

이 문제를 읽어보면 $A$라는 데이터가 주어지는데 이 데이터의 형태는 수열(배열)이고, 여기에 네 가지의 연산(쿼리)을 수행할 수 있다.

$1\ x$: $A$의 가장 뒤에 $x$를 추가한다.
$2\ x$: $A$에서 가장 먼저 나오는 $x$를 제거한다.
$3$: $A$에 포함된 모든 원소를 더한 값을 출력한다.
$4$: $A$에 포함된 모든 원소를 XOR한 값을 출력한다.

종류별로 나누면 $1$번 쿼리는 추가, $2$번 쿼리는 삭제, $3$번과 $4$번 쿼리는 조회에 해당한다고 할 수 있다. 수정에 해당하는 연산은 이 문제에는 나오지 않았다.

이제 쿼리의 온라인/오프라인에 대해서 살펴보기로 한다. 한 데이터에 여러 번의 쿼리를 수행할 경우 수행 방법은 다음과 같이 두 가지로 구분할 수 있다.

각각의 쿼리가 입력되는 대로 바로 처리한다.^[각주:1] ← 온라인 쿼리(Online Query)
입력된 쿼리를 바로 처리하지 않고 여러 쿼리를 한번에 처리하거나 순서를 바꿔서 처리한다. ← 오프라인 쿼리(Offline Query)

일반적으로 온라인 쿼리를 더 먼저 접하고 더 많이 사용한다. 오프라인 쿼리는 쿼리를 따로 저장해 놓았다가 다시 불러와야 하는 번거로움이 있기 때문이다. 하지만 다음과 같은 쿼리를 처리하는 경우를 생각해 보자.

$1\ x$: 집합에 $x$를 추가한다.
$2\ x$: 집합에서 $x$를 삭제한다.
$3\ k\ x$: $k$번째 쿼리까지 처리한 상태에서 집합에 $x$가 존재하는지 확인한다.

$3$번 쿼리는 집합의 현재 상태뿐 아니라 과거나 미래의 상태 정보를 요구하는데, 이런 쿼리는 온라인으로 처리할 수가 없다. 따라서 오프라인으로 처리하게 되는데, 어떤 식으로 하는지 요약하면 다음과 같다.

쿼리를 모두 입력받고 순서와 함께 전부 저장해 둔다. 이때 $1$번, $2$번 쿼리와 $3$번 쿼리를 따로 저장하면 편하다.
$3$번 쿼리를 $k$가 작은 순서대로 정렬한다.
$1$번, $2$번 쿼리를 차례로 수행한다. 중간중간에 $3$번 쿼리의 확인 대상이 되는 상태들이 나타나는데, 그때마다 해당하는 $3$번 쿼리를 처리해 주면 된다.

예시를 하나 살펴보자. 처음에 빈 집합이 존재하고 $10$개의 쿼리를 처리한다.

$1\ 5$
$3\ 7\ 6$
$1\ 6$
$2\ 5$
$3\ 1\ 4$
$1\ 8$
$3\ 3\ 8$
$2\ 6$
$1\ 2$
$3\ 2\ 5$

$1$번, $2$번 쿼리와 $3$번 쿼리를 구분하면 다음과 같다.

$1$번, $2$번 쿼리:
$1\ 1\ 5$
$3\ 1\ 6$
$4\ 2\ 5$
$6\ 1\ 8$
$8\ 2\ 6$
$9\ 1\ 2$

$3$번 쿼리:
$2\ 7\ 6$
$5\ 1\ 4$
$7\ 3\ 8$
$10\ 2\ 5$

쿼리를 분리해서 저장할 때는 각 쿼리가 몇 번째로 입력된 쿼리인지도 저장해야 한다. $3$번 쿼리를 저장할 때 쿼리의 종류를 생략한 것도 참고하자.

다음으로 $3$번 쿼리를 정렬한다. 여기서는 두 번째 수가 $k$이므로 정렬하면 다음과 같이 된다.

$1$번, $2$번 쿼리:
$1\ 1\ 5$
$3\ 1\ 6$
$4\ 2\ 5$
$6\ 1\ 8$
$8\ 2\ 6$
$9\ 1\ 2$

$3$번 쿼리:
$5\ 1\ 4$
$10\ 2\ 5$
$7\ 3\ 8$
$2\ 7\ 6$

이제 쿼리를 처리한다. $1$번, $2$번 쿼리를 처리하다가 중간중간에 $3$번 쿼리를 처리해 주면 된다. 먼저 $1$번째 쿼리('$1$번 쿼리'와 '$1$번째 쿼리'의 차이에 주의하자)를 처리하면 집합은 다음과 같이 변한다.

$$S = \{5\}$$

이때 $3$번 쿼리를 보면 $k = 1$인 쿼리가 존재한다. 따라서 이 쿼리를 처리한다. $4$는 집합에 없으므로 $5$번째 쿼리의 결과는 False이다.

이제 다음 $1$번, $2$번 쿼리로 넘어간다. 다음 쿼리는 $3$번째 쿼리인데 이때 $3$번 쿼리 중 $k = 2$인 쿼리가 있으므로 이걸 먼저 처리해야 한다. $5$는 집합에 있으므로 $10$번째 쿼리의 결과는 True이다. 이어서 $3$번째 쿼리를 처리하면 집합은 다음과 같이 변한다.

$$S = \{5, 6\}$$

다시 $3$번 쿼리를 보면 $k = 3$인 쿼리가 있으므로 이걸 처리한다. $8$은 집합에 없으므로 $7$번째 쿼리의 결과는 False이다.

이어서 $4$번째 쿼리와 $6$번째 쿼리를 차례로 처리한다. 그러면 집합은 다음과 같이 변한다.

$$S = \{6, 8\}$$

$3$번 쿼리에 $k = 7$인 쿼리가 있으므로 이걸 처리한다. $6$은 집합에 있으므로 $2$번째 쿼리의 결과는 True이다.

마지막으로 $8$번째 쿼리와 $9$번째 쿼리를 차례로 처리한다. 그러면 집합의 마지막 상태는 다음과 같다.

$$S = \{2, 8\}$$

이제 $3$번 쿼리를 입력된 순서로 정렬한다. 쿼리의 순서와 결과값만 표시하면 다음과 같다.

$2$ True
$5$ False
$7$ False
$10$ True

이렇게 해서 쿼리 처리가 완료되었다.

위에서 살펴본 것과 같이 오프라인 쿼리는 온라인으로 처리하기 어려운 쿼리를 처리할 때 유용하지만, 반대로 온라인 쿼리만 쓸 수 있는 경우가 있다. 머지 소트 트리 연습문제로 나왔던 수열과 쿼리 3 문제를 보면 이전 쿼리의 결과를 통해 다음 쿼리를 생성한다. 이런 식으로 이전 쿼리의 결과가 다음 쿼리의 내용에 영향을 주는 경우 쿼리의 순서를 바꾸면 쿼리의 내용을 알 수가 없으므로 오프라인 쿼리를 쓸 수 없다. 참고로 수열과 쿼리 3 문제에서 쿼리가 서로 영향을 주지 않을 때 오프라인 쿼리로 푸는 방법은 연습문제의 수열과 쿼리 1 해설에 언급되어 있다.

[연습문제]

BOJ 16978. 수열과 쿼리 22 (Platinum IV)

세그먼트 트리로 구간 합을 구하는 기본적인 형태의 문제이다. 쿼리가 여러 시점을 참조하므로 오프라인 쿼리로 처리하면 된다.

BOJ 13306. 트리 (Platinum IV)

트리에서 오프라인 쿼리를 사용하는 흔하지 않은 문제이다. 풀이 자체는 알면 간단한데, 간선을 제거하는 쿼리가 $N - 1$개 주어지므로 모든 쿼리의 처리가 끝났을 때는 모든 간선이 제거된 상태이고, 여기서 시작에서 역방향으로 문제를 풀면 $1$번 쿼리는 간선을 추가하는 쿼리, $2$번 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 확인하는 쿼리가 되므로 분리 집합을 사용하면 쉽게 구할 수 있다.

BOJ 13537. 수열과 쿼리 1 (Platinum III)

쿼리를 $k$ 기준 내림차순으로 정렬한 다음 빈 수열에 큰 원소부터 하나씩 추가하는 식으로 접근하면 오프라인 쿼리로 처리할 수 있는 형태가 된다. 쿼리를 처리할 때는 구간에서 현재까지 추가된 원소의 개수를 세그먼트 트리로 구하면 된다.

→ solved.ac tag: offline_queries