자바 코딩테스트 강좌, 구간 합

안녕하세요! 이번 포스팅에서는 자바를 활용한 코딩테스트 준비를 위한 구간 합 문제를 다루어 보겠습니다. 구간 합 문제는 주어진 배열의 특정 구간에 있는 원소들의 합을 효율적으로 구하는 문제로, 알고리즘 문제에서 자주 출제되는 유형입니다.

문제 설명

배열 A가 주어졌을 때, Q개의 쿼리가 있습니다. 각 쿼리는 두 정수 L과 R로 이루어져 있으며, 이들은 배열 A의 인덱스를 나타냅니다. 각 쿼리에 대해 L번째부터 R번째까지의 구간 합을 구하시오.

입력

    첫 번째 줄에는 배열의 크기 N과 쿼리의 수 Q가 주어진다.
    두 번째 줄에는 N개의 정수 A[1], A[2], ..., A[N]이 주어진다.
    이후 Q개의 줄에 L과 R가 공백으로 구분되어 주어진다.

출력

    각 쿼리에 대한 구간 합을 한 줄에 하나씩 출력한다.

예제 입력

예제 출력

    6
    9
    15

문제 해결 전략

구간 합 문제를 처리하기 위한 코딩 방법은 여러 가지가 있지만, 비효율적인 방법으로는 각 쿼리에 대해 직접 루프를 돌며 구간 합을 계산하는 것입니다. 이 경우, 최악의 경우 O(N * Q)의 시간이 소요될 수 있습니다. 따라서 우리는 구간 합을 빠르게 계산하기 위한 방법을 찾아야 합니다.

전처리 통한 접근

효율적인 방법 중 하나는 전처리 과정을 통해 구간 합을 누적 배열 형태로 저장하는 것입니다. 이렇게 하면 각 쿼리의 구간 합을 O(1)에 구할 수 있습니다.

먼저, 누적합 배열 sum을 생성합니다. 이때 sum[0] = 0으로 초기화하고, sum[i] = sum[i - 1] + A[i - 1]로 설정합니다.
각 쿼리는 구간 [L, R]에서의 합을 구하기 위해 sum[R] - sum[L - 1] 공식을 사용합니다.

자바 코드 구현

    import java.util.Scanner;

    public class RangeSum {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            // 배열의 크기와 쿼리 수 입력
            int N = sc.nextInt();
            int Q = sc.nextInt();
            
            // 배열 입력
            int[] A = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = sc.nextInt();
            }
            
            // 누적합 배열 생성
            long[] sum = new long[N + 1];
            for (int i = 1; i <= N; i++) {
                sum[i] = sum[i - 1] + A[i - 1];
            }
            
            // 각 쿼리를 처리
            for (int i = 0; i < Q; i++) {
                int L = sc.nextInt();
                int R = sc.nextInt();
                long rangeSum = sum[R] - sum[L - 1];
                System.out.println(rangeSum);
            }
            
            sc.close();
        }
    }

코드 설명

위의 코드는 다음과 같은 흐름으로 동작합니다:

먼저, 사용자로부터 배열의 크기 N과 쿼리 수 Q를 입력받습니다.
그 다음, 배열 A의 원소를 입력받아 초기화합니다.
각 원소의 누적합을 저장하는 sum 배열을 생성합니다. 이때, 인덱스 0은 0으로 초기화 통합하여, sum[i]에 대한 접근이 용이합니다.
쿼리마다 주어진 L과 R을 이용해 구간 합을 계산 후 출력합니다.

테스트 및 검증

코드를 작성한 후, 다양한 입력을 통해 각 쿼리가 올바른 결과를 출력하는지 확인해야 합니다. 예제 입력과 함께 추가적인 경우들도 실험해보며 결과를 검토합니다. 아래는 몇 가지 예시입니다.

입력: 1 1 → 출력: 1
입력: 2 5 → 출력: 14
입력: 3 3 → 출력: 3

결론

이번 포스팅에서는 구간 합 문제를 해결하는 과정을 살펴보았습니다. 전처리를 통해 구간 합을 효율적으로 계산하는 방법을 익히는 것이 중요하며, 자바의 배열과 반복문을 활용하는 방법을 연습하는 것도 좋은 코딩 실력을 기르는 데 도움이 될 것입니다. 앞으로 더 많은 알고리즘 문제를 다루며 기술적인 역량을 다져나가길 바랍니다.

감사합니다!