안녕하세요! 오늘은 C#을 이용한 코딩 테스트에서 자주 출제되는 문제 중 하나인 “구간 합 구하기” 문제에 대해 다루어 보겠습니다. 이 문제를 통해 배열과 구간 합에 대한 이해도를 높이고, 이를 효율적으로 해결하기 위한 알고리즘을 배워보겠습니다.
문제 설명
구간 합 구하기 문제는 다음과 같이 정의할 수 있습니다:
정수 배열 arr와 여러 쿼리(시작 인덱스와 종료 인덱스)가 주어질 때, 각 쿼리마다 해당 구간의 합을 구하는 프로그램을 작성하시오.
입력으로는 배열의 크기 n, 배열의 원소들, 쿼리의 개수 q, 그리고 각 쿼리의 시작 인덱스 l과 종료 인덱스 r가 주어집니다.
입력 예시
5
1 2 3 4 5
3
1 3
2 4
1 5
위의 입력은 다음과 같습니다:
- 배열의 크기:
5 - 배열 원소:
[1, 2, 3, 4, 5] - 쿼리 개수:
3 - 쿼리들: (1, 3), (2, 4), (1, 5)
출력 예시
6
9
15
출력은 각 쿼리에 대한 구간 합입니다:
- (1, 3)의 구간 합:
1 + 2 + 3 = 6 - (2, 4)의 구간 합:
2 + 3 + 4 = 9 - (1, 5)의 구간 합:
1 + 2 + 3 + 4 + 5 = 15
문제 풀기
이제 이 문제를 해결하기 위한 방법을 단계별로 살펴보겠습니다. 우리는 먼저 단순한 접근법부터 시작한 후, 효율적인 방법으로 풀이를 발전시켜 보겠습니다.
1. 단순 접근법
가장 직관적인 방법은 각 쿼리의 시작 인덱스와 종료 인덱스에 맞추어 직접 합을 계산하는 것입니다. 그러나 이 방법은 비효율적일 수 있습니다. 예를 들어, 배열의 크기가 n이고 쿼리의 개수가 q일 때, 최악의 경우 O(n * q)의 시간 복잡도를 가집니다.
C#
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int q = int.Parse(Console.ReadLine());
for (int i = 0; i < q; i++)
{
var query = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int l = query[0] - 1; // 0-based index
int r = query[1] - 1; // 0-based index
int sum = 0;
for (int j = l; j <= r; j++)
{
sum += arr[j];
}
Console.WriteLine(sum);
}
}
}
이 코드에서는 사용자가 입력한 배열의 원소에 대해 쿼리마다 합을 계산하고 있습니다. 하지만 큰 데이터셋에서는 이 방법이 비효율적입니다.
2. 효율적인 접근법: 누적 합 배열
효율적인 방법으로는 누적 합 배열을 사용하는 것입니다. 누적 합은 배열의 각 인덱스까지의 합을 미리 계산해 두어 쿼리의 처리시간을 줄여줍니다.
즉,
C#
sum[i] = arr[0] + arr[1] + ... + arr[i]
를 사용하여, 구간 합을 구하고자 할 때:
C#
구간합 = sum[r] - sum[l-1]
이렇게 하면 쿼리 처리 시간이 O(1)로 줄어듭니다. 전체 시간 복잡도는 O(n + q)가 됩니다.
C#
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int q = int.Parse(Console.ReadLine());
long[] sum = new long[n + 1];
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + arr[i - 1];
}
for (int i = 0; i < q; i++)
{
var query = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int l = query[0] - 1; // 0-based index
int r = query[1] - 1; // 0-based index
long result = sum[r + 1] - sum[l];
Console.WriteLine(result);
}
}
}
이 코드에서는 먼저 누적 합 배열을 계산한 후, 각 쿼리마다 시작 인덱스와 종료 인덱스를 활용해 구간 합을 신속히 계산합니다.
결론
구간 합 구하기 문제는 코딩 테스트에서 자주 등장하는 문제로, 이를 해결하기 위해서는 누적 합 배열을 사용하는 것이 효율적임을 알 수 있습니다. 이 방법은 배열의 크기와 쿼리 개수가 클 경우 특히 유리합니다. 적절한 데이터 구조를 사용하여 알고리즘의 효율성을 높이고, 쿼리 처리 시간을 줄이는 것은 알고리즘 문제를 해결하는 데 중요한 요소입니다.
오늘 배운 내용을 바탕으로 다양한 구간 합 구하기 문제를 풀어보며 연습해 보시기 바랍니다. 감사합니다!