C# 코딩테스트 강좌, 구간 곱 구하기

문제 설명

주어진 정수 배열 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가 주어집니다.

출력 형식

각 쿼리에 대해 계산한 결과를 한 줄에 하나씩 출력합니다.

예시

문제 풀이

이 문제를 해결하기 위해서는 구간 곱을 빠르게 계산할 수 있는 방법이 필요합니다. 단순히 각 쿼리에 대해 구간을 순회하면서 곱을 계산하면 시간 복잡도 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 기법은 다양한 형태의 쿼리 문제에서 유용하게 적용될 수 있으므로, 다양한 문제에 적용해보는 것도 좋습니다. 감사합니다!