안녕하세요! 오늘은 ‘구간 합 구하기 3’라는 주제로 자바 코딩테스트 문제를 함께 풀어보겠습니다. 이 문제는 주어진 배열에서 특정 구간의 합을 효율적으로 구하는 알고리즘을 구성하는 것을 목표로 합니다. 그러면 문제를 살펴보도록 하겠습니다.
문제 설명
주어진 정수 배열 A와 m개의 쿼리가 주어질 때, 각 쿼리는 두 개의 정수 X와 Y로 나타내며, A[X] + A[X+1] + ... + A[Y]의 값을 출력하는 문제입니다. 단, 쿼리는 1-indexed입니다.
입력 형식
- 첫 번째 줄에 두 개의 정수
N(배열 원소의 개수)과M(쿼리의 개수)가 주어진다. - 둘째 줄에
N개의 정수로 이루어진 배열A가 주어진다. - 셋째 줄부터
M개의 줄에 각각의 쿼리를 나타내는 두 개의 정수X와Y가 주어진다.
출력 형식
각 쿼리의 결과를 한 줄에 하나씩 출력한다.
예제
입력 예제: 5 3 1 2 3 4 5 1 3 2 4 1 5 출력 예제: 6 9 15
문제 접근 방법
1-indexed 배열에서 특정 구간의 합을 구하기 위해서는 다음과 같은 방법을 사용할 수 있습니다:
- 우선 합 배열을 만든다: 원 배열의 합을 미리 계산하여 각 인덱스에서의 합을 저장하는 배열을 생성합니다. 이 합 배열을 사용하면 O(1) 시간 복잡도로 구간 합을 구할 수 있습니다.
- 구간 합 계산: 구간의 총 합은
sum[Y] - sum[X-1]로 계산할 수 있습니다. 여기서sum[i]는 입력 배열의 1부터i까지의 합입니다.
알고리즘 구현
자바로 알고리즘을 구현해 보겠습니다. 아래는 실제 코드입니다:
import java.util.Scanner;
public class IntervalSum {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 배열 크기 N과 쿼리 개수 M 입력 받기
int N = scanner.nextInt();
int M = scanner.nextInt();
// 배열 A 선언 및 값 입력
long[] A = new long[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = scanner.nextLong();
}
// 합 배열 선언
long[] sum = new long[N + 1];
// 합 배열 생성
for (int i = 1; i <= N; i++) {
sum[i] = sum[i - 1] + A[i];
}
// 쿼리 처리
for (int j = 0; j < M; j++) {
int X = scanner.nextInt();
int Y = scanner.nextInt();
// 구간 합 계산 및 출력
System.out.println(sum[Y] - sum[X - 1]);
}
// Scanner 닫기
scanner.close();
}
}코드 설명
위 코드는 다음과 같은 구조로 되어 있습니다:
Scanner를 사용하여 입력을 받습니다. 배열의 크기(N)와 쿼리의 개수(M)를 읽습니다.- 배열
A를 만들고 1-indexed로 값을 할당합니다. - 합 배열
sum을 생성합니다. 이 배열은sum[i]가 배열A의 1부터i까지의 합을 저장합니다. - 각 쿼리의
X와Y를 읽고 구간 합을 계산한 후 결과를 출력합니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 다음과 같습니다:
- 합 배열을 만드는 데 O(N) 시간이 소요됩니다.
- 각 쿼리를 처리하는 데 O(1)의 시간이 소요됩니다. 따라서 쿼리
M에 대해 O(M)의 시간이 소요됩니다.
결론적으로, 전체 알고리즘의 시간 복잡도는 O(N + M)입니다. 이는 문제를 효율적으로 해결할 수 있는 방법입니다.
마무리
오늘은 ‘구간 합 구하기 3’ 문제를 통해 Java 언어로 알고리즘 문제를 해결하는 방법을 배워보았습니다. 합 배열을 활용하여 쿼리의 효율성을 높이는 방법에 대해 이해하셨기를 바랍니다. 추가적인 문제를 통해 더 많은 연습을 해보세요. 다음 강좌에서는 다른 주제로 찾아뵙겠습니다. 감사합니다!