이번 글에서는 주어진 범위 안의 숫자들이 짝수인지 홀수인지, 즉 숫자의 홀짝성(parity)에 대한 확률을 구하는 문제를 다룹니다. 각 쿼리마다 결과를 분수 형태인 p / q로 출력해야 하며, 이때 p와 q는 서로소(최대공약수가 1)여야 합니다.
문제 예시
입력 : N = 5, arr[] = { 6, 5, 2, 1, 7 }
query 1: 0 2 2
query 2: 1 2 5
query 3: 0 1 4
출력 : 0
3 4
1 2해결 접근 방법
핵심 아이디어는 접두사 합(prefix sum) 기법을 활용하는 것입니다. 배열을 한 번만 순회하면서 인덱스 i까지 등장한 짝수의 개수와 홀수의 개수를 각각 별도의 배열에 누적 저장합니다. 이렇게 해두면 어떤 쿼리가 들어와도 해당 범위의 끝 지점 값에서 시작 지점 값을 빼기만 하면 되므로, 매번 배열을 처음부터 다시 탐색할 필요 없이 O(1) 만에 답을 구할 수 있습니다.
구체적인 처리 순서는 다음과 같습니다.
- 짝수 개수 배열(even)과 홀수 개수 배열(odd)을 준비하고, 1-based 인덱싱을 위해 0번 인덱스를 0으로 초기화합니다.
- 원본 배열을 순회하며 각 원소가 홀수면 odd 배열을, 짝수면 even 배열을 증가시킵니다.
- 각 쿼리에 대해 k 값으로 쿼리 종류를 판별하고, 범위 [l, r] 내의 대상 개수 p와 전체 원소 개수 q = r - l + 1을 구합니다.
- p가 0이면 0을, p와 q가 같으면 1을 출력하고, 그 외에는 최대공약수(gcd)로 나누어 기약분수 형태로 출력합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
void solve(int arr[], int n, int Q, int query[][3]){
int even[n + 1]; // i번째 인덱스까지 발견된 짝수의 개수를 저장하는 배열
int odd[n + 1]; // i번째 인덱스까지 발견된 홀수의 개수를 저장하는 배열
even[0] = 0; odd[0] = 0; // 1-based 인덱싱을 사용하므로 두 배열의 0번 인덱스를 0으로 설정
for (int i = 0; i < n; i++) {
if (arr[i] & 1) { // 홀수를 발견하면 odd 증가
odd[i + 1] = odd[i] + 1;
even[i + 1] = even[i];
}
else { // 그렇지 않으면 even 증가
even[i + 1] = even[i] + 1;
odd[i + 1] = odd[i];
}
}
for (int i = 0; i < Q; i++) { // 쿼리 순회
int r = query[i][2]; // 범위의 오른쪽 끝
int l = query[i][1]; // 범위의 왼쪽 끝
int k = query[i][0]; // 쿼리 종류
int q = r - l + 1; // 주어진 범위에 포함된 원소의 개수
int p;
if (k) // k가 쿼리 종류를 나타내며,
// 주어진 범위에서 같은 홀짝성을 가지는 원소의 개수를 구함
p = odd[r] - odd[l - 1];
else
p = even[r] - even[l - 1];
if (!p) // p가 0이면 단순히 0 출력
cout << "0\n";
else if (p == q) // p == q이면 1 출력
cout << "1\n";
else {
int g = __gcd(p, q);
cout << p / g << " " << q / g << "\n"; // p와 q가 공약수를 가지지 않도록 gcd로 나눔
}
}
}
int main(){
int arr[] = { 6, 5, 2, 1, 7 }; // 주어진 배열
int n = sizeof(arr) / sizeof(int); // 배열의 크기
int Q = 2; // 쿼리의 개수
int query[Q][3] = {{ 0, 2, 2 },{ 1, 2, 5 }}; // 주어진 쿼리들
solve(arr, n, Q, query);
return 0;
}실행 결과
0 3 4
코드 설명
위 코드에서는 두 개의 배열을 유지하면서 i번째 인덱스까지 발견된 짝수와 홀수의 개수를 미리 누적해 둡니다. 이후 각 쿼리가 들어오면 해당 범위 [l, r] 안에 있는 짝수 또는 홀수의 개수를 구하고, 범위 내 전체 원소 개수와 함께 분수 형태로 출력합니다. 마지막으로 __gcd 함수를 사용해 분자와 분모를 약분하여 기약분수로 만드는 것이 중요한 포인트입니다.
성능 및 시간 복잡도
전처리 과정에서 배열을 한 번 순회하므로 O(N)의 비용이 들고, 이후 각 쿼리는 단순한 뺄셈 연산만 필요하기 때문에 쿼리당 O(1)입니다. 따라서 총 시간 복잡도는 O(N + Q)가 되며, 쿼리 수가 많은 상황에서도 매우 효율적으로 동작합니다. 반복 탐색 방식(O(N × Q))에 비해 월등히 빠른 성능을 보입니다.
마무리
이 튜토리얼에서는 주어진 범위에서 짝수 또는 홀수의 확률을 구하는 쿼리 문제를 해결해 보았습니다. 접두사 합 방식을 활용한 완전한 C++ 프로그램과 함께 문제 풀이 과정을 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있으니, 여러 언어로 직접 구현해 보면서 개념을 익혀 보시길 바랍니다.