문제 설명
주어진 정수 배열 nums와 쿼리 배열 queries가 있습니다. 각 쿼리는 두 정수 (l, r)로 이루어져 있으며, 이는 nums[l] * nums[l + 1] * ... * nums[r]의 값을 구하라는 요청입니다. 단, nums 배열의 크기는 최대 10^5, queries의 길이는 최대 10^4입니다. 이때, 곱셈의 결과가 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 출력해야 합니다.
입력 형식
첫 번째 줄에 배열의 크기 n과 쿼리의 수 q가 주어집니다. 두 번째 줄에 n개의 정수로 이루어진 배열 nums가 주어지고, q개의 줄에 걸쳐 각 쿼리 l과 r가 주어집니다.
출력 형식
각 쿼리에 대해 계산한 결과를 한 줄에 하나씩 출력합니다.
예시
5 3
2 3 4 5 6
0 2
1 3
2 4
출력
24
60
120
문제 풀이
이 문제를 해결하기 위해서는 구간 곱을 빠르게 계산할 수 있는 방법이 필요합니다. 단순히 각 쿼리에 대해 구간을 순회하면서 곱을 계산하면 시간 복잡도 O(q * n)에 이르게 되어, 최악의 경우 10^9의 연산을 수행할 수 있습니다. 이는 실용적이지 않기 때문에, Prefix Product를 사용하여 시간 복잡도를 줄이는 전략을 사용합니다.
Prefix Product 방법
우선, nums 배열의 원소들에 대한 누적 곱을 저장하여 쿼리의 결과를 빠르게 계산할 수 있도록 합니다.
C#
int mod = 1000000007;
int[] prefixProduct = new int[n + 1];
prefixProduct[0] = 1;
for (int i = 1; i <= n; i++) {
prefixProduct[i] = (int)((1L * prefixProduct[i - 1] * nums[i - 1]) % mod);
}
여기서 prefixProduct[i]는 nums[0] * nums[1] * ... * nums[i - 1]의 값을 저장합니다. 이 구조를 통해 우리는 구간 곱을 쉽고 빠르게 계산할 수 있습니다.
구간 곱 계산하기
이제 각 쿼리 (l, r)에 대해, 구간 곱 nums[l] * nums[l + 1] * ... * nums[r]는 다음과 같이 구할 수 있습니다:
C#
int result = (int)((1L * prefixProduct[r + 1] * modInverse(prefixProduct[l]) % mod) % mod);
여기서 modInverse 함수는 모듈로 연산에 대한 역원을 구하는 함수입니다. 역원은 다음과 같이 구현할 수 있습니다:
C#
int modInverse(int a) {
return power(a, mod - 2);
}
int power(int x, int y) {
int res = 1;
while (y > 0) {
if ((y & 1) == 1) {
res = (int)((1L * res * x) % mod);
}
y >>= 1;
x = (int)((1L * x * x) % mod);
}
return res;
}
최종 코드
위의 설명을 토대로 전체 코드를 작성하면 다음과 같습니다:
C#
using System;
class Program {
static int mod = 1000000007;
static void Main() {
string[] firstLine = Console.ReadLine().Split();
int n = int.Parse(firstLine[0]);
int q = int.Parse(firstLine[1]);
int[] nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int[] prefixProduct = new int[n + 1];
prefixProduct[0] = 1;
for (int i = 1; i <= n; i++) {
prefixProduct[i] = (int)((1L * prefixProduct[i - 1] * nums[i - 1]) % mod);
}
for (int i = 0; i < q; i++) {
string[] query = Console.ReadLine().Split();
int l = int.Parse(query[0]);
int r = int.Parse(query[1]);
int result = (int)((1L * prefixProduct[r + 1] * modInverse(prefixProduct[l]) % mod) % mod);
Console.WriteLine(result);
}
}
static int modInverse(int a) {
return power(a, mod - 2);
}
static int power(int x, int y) {
int res = 1;
while (y > 0) {
if ((y & 1) == 1) {
res = (int)((1L * res * x) % mod);
}
y >>= 1;
x = (int)((1L * x * x) % mod);
}
return res;
}
}
결론
이번 강좌에서는 배열의 구간 곱을 효과적으로 계산하기 위해 Prefix Product 방법과 모듈로 연산의 역원의 개념을 활용하는 방법을 학습했습니다. 이 방법을 응용하면 더욱 복잡한 쿼리 처리에도 유용하게 활용할 수 있을 것입니다. C# 언어의 특징을 살려 효율적인 코드를 작성하고, 알고리즘 문제 해결 능력을 한층 더 향상시킬 수 있습니다.
추가적으로, 이 문제에서 사용한 Prefix Product 기법은 다양한 형태의 쿼리 문제에서 유용하게 적용될 수 있으므로, 다양한 문제에 적용해보는 것도 좋습니다. 감사합니다!