자바 코딩테스트 강좌, 구간 곱 구하기

안녕하세요! 이번 포스팅에서는 구간 곱 구하기 문제를 해결하는 방법에 대해 알아보겠습니다. 이 문제는 주어진 배열에서 특정 구간의 곱을 빠르게 계산하는 알고리즘을 구현하는 것을 목표로 합니다. 이 강좌에서는 문제 정의부터 시작하여, 접근 방식, 구현, 그리고 성능 분석까지 단계적으로 진행됩니다.

문제 정의

주어진 정수 배열 nums와 여러 쿼리 (i, j)가 있을 때, 배열의 인덱스 i부터 j까지의 곱을 구해야 합니다. 이를 여러 번 반복해야 하므로, 시간 복잡도를 고려하여 효율적인 방법이 필요합니다.

예제

입력:
nums = [1, 2, 3, 4, 5]
쿼리 = [(0, 1), (1, 3), (0, 4)]

출력:
쿼리 0: 1 * 2 = 2
쿼리 1: 2 * 3 * 4 = 24
쿼리 2: 1 * 2 * 3 * 4 * 5 = 120

접근 방법

직관적으로는 각 쿼리에 대해 nums 배열에서 직접 곱을 계산할 수 있습니다. 하지만 이는 최악의 경우 O(n) 시간 복잡도를 요구하므로 여러 쿼리를 수행할 때 비효율적입니다. 따라서 아래와 같은 두 가지 접근 방법을 고려해볼 수 있습니다:

1. 누적 곱 배열 (Prefix Product Array): 배열의 누적 곱을 미리 계산한 후, 각 쿼리에 대해 O(1)로 남은 곱을 빠르게 계산하는 방법입니다. 이 방법은 O(n)으로 누적 곱 배열을 준비한 후, 각 쿼리에서 O(1)에 계산하여 총 O(n + m) (여기서 m은 쿼리의 개수) 이 될 수 있습니다.
2. 세그먼트 트리 (Segment Tree): 더 일반적인 방법으로, 세그먼트 트리를 사용하여 각 구간의 곱을 효율적으로 계산할 수 있습니다. 이 경우 초기화는 O(n log n)이고 쿼리는 O(log n)입니다.

이번 강좌에서는 첫 번째 방법인 누적 곱 배열을 사용한 구현을 진행하겠습니다.

구현

먼저, 누적 곱 배열을 생성한 다음, 각 쿼리마다 해당 구간의 곱을 계산해보겠습니다.

public class RangeProduct {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int[][] queries = {{0, 1}, {1, 3}, {0, 4}};
        int[] result = rangeProduct(nums, queries);
        
        for (int res : result) {
            System.out.println(res);
        }
    }

    public static int[] rangeProduct(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] prefixProduct = new int[n + 1];
        
        // 누적 곱 배열 생성
        prefixProduct[0] = 1; // 초기값
        for (int i = 1; i <= n; i++) {
            prefixProduct[i] = prefixProduct[i - 1] * nums[i - 1];
        }
        
        int[] result = new int[queries.length];

        // 쿼리 처리
        for (int q = 0; q < queries.length; q++) {
            int i = queries[q][0];
            int j = queries[q][1];
            // 구간곱 계산
            result[q] = prefixProduct[j + 1] / prefixProduct[i]; // 0 ~ j의 곱 / 0 ~ (i-1)의 곱
        }
        
        return result;
    }
}

성능 분석

위의 풀이는 효율적으로 쿼리를 처리할 수 있는 방법을 보여줍니다. 초기 누적 곱 배열을 만드는 데 O(n)시간이 걸리며, 각 쿼리 처리 시간은 O(1)입니다. 총 시간 복잡도는 O(n + m)이 됩니다. 이 방법은 querry 수가 많아질수록 효율적인 성능을 보여줍니다.

마무리

이번 강좌에서는 구간 곱 구하기 문제를 해결하는 방법을 살펴보았습니다. 누적 곱 배열을 사용하여 효율적으로 쿼리를 처리하는 방법을 배울 수 있었습니다. 세그먼트 트리나 펜윅 트리와 같은 더욱 복잡한 자료구조를 배우고 싶다면 다음 강좌를 기대해 주세요!

더 나아가기

이 강좌 이후에는 해당 문제를 다른 방식으로 해결하는 방법에 대해 다루어보는 것도 좋습니다. 다양한 방법론을 학습함으로써 알고리즘적 사고력을 확장할 수 있을 것입니다. 질문이나 토론이 필요한 부분이 있다면 댓글로 남겨주세요!