안녕하세요, 여러분! 오늘은 C#을 이용한 코딩 테스트의 중요한 주제 중 하나인 ‘구간 합’에 대해 다뤄보겠습니다. 구간 합 문제는 배열의 특정 구간에 대한 합을 효율적으로 구하는 문제입니다. 이 문제는 많은 알고리즘 문제 및 실무에서도 자주 나오는 매우 유용한 주제입니다.
문제 정의
문제를 시작하기에 앞서, 구간 합이 무엇인지 간단히 설명드리겠습니다. 구간 합이란 주어진 배열의 특정 구간(예: 배열[i] 부터 배열[j]까지)의 합을 구하는 것을 의미합니다. 이러한 문제는 다양한 방식으로 출제될 수 있습니다.
문제 예시
다음과 같은 배열이 있다고 가정해 보겠습니다.
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};이제 우리는 주어진 배열의 구간 합을 요청하는 문제를 풀어 보겠습니다. 예를 들어, i와 j가 각각 2와 5라면, 우리는 arr[2]부터 arr[5]까지의 합, 즉 3 + 4 + 5 + 6 = 18을 구해야 합니다.
문제 해결 접근법
구간 합을 구하기 위한 첫 번째 방법은 단순 반복문을 사용하는 것입니다. 배열의 요소를 순회하여 i와 j의 값에 해당하는 구간의 합을 계산할 수 있습니다. 하지만 시간 복잡도가 O(N)으로 비효율적이라는 단점이 있습니다. 그렇다면 어떻게 하면 더 효율적으로 구간 합을 계산할 수 있을까요?
전처리 방식
구간 합 문제를 효율적으로 해결하기 위해, ‘누적 합 배열’이라는 개념을 사용합니다. 누적 합 배열은 각 인덱스까지의 합을 저장하는 배열로, 구간 합을 쉽게 계산할 수 있게 해줍니다. 누적 합 배열을 이용하면 구간 합을 O(1)의 시간 복잡도로 구할 수 있습니다.
누적 합 배열 예시
누적 합 배열을 만드는 방법을 살펴보겠습니다.
int[] prefixSum = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++)
{
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
위 코드에서는 prefixSum 배열의 i+1 번째 인덱스에 arr 배열의 i번째 인덱스까지의 합을 저장합니다. 이제 특정 구간 [i, j]의 합은 prefixSum[j + 1] – prefixSum[i]로 쉽게 구할 수 있습니다.
구현
이제 누적 합 배열을 이용한 구간 합 알고리즘을 C#으로 구현해 보겠습니다.
using System;
public class Program
{
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int[][] queries = { new int[] { 2, 5 }, new int[] { 0, 9 }, new int[] { 4, 7 } };
int[] result = RangeSum(arr, queries);
foreach (var sum in result)
{
Console.WriteLine(sum);
}
}
public static int[] RangeSum(int[] arr, int[][] queries)
{
int[] prefixSum = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++)
{
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
int[] results = new int[queries.Length];
for (int i = 0; i < queries.Length; i++)
{
int l = queries[i][0];
int r = queries[i][1];
results[i] = prefixSum[r + 1] - prefixSum[l];
}
return results;
}
}
위 코드를 실행하면 각각의 쿼리에 대해 구간 합을 계산할 수 있습니다. 주의할 점은 인덱스의 범위를 항상 유효하게 유지해야 한다는 것입니다.
시간 복잡도 분석
위에서 설명한 알고리즘의 시간 복잡도는 다음과 같습니다.
- 누적 합 배열 생성: O(N)
- 쿼리 처리: O(1) (각 쿼리에 대해 상태 정보 접근)
결과적으로 이 알고리즘은 O(N + Q)의 시간 복잡도를 가지며, 여기서 Q는 쿼리의 개수입니다. 이처럼 구간 합 문제는 누적 합 배열을 통해 매우 효율적으로 해결할 수 있습니다.
실전 연습
이제 여러분이 구간 합 문제를 얼마나 잘 이해하고 있는지 테스트해 보세요. 아래와 같은 문제를 스스로 만들어 풀어보기를 권장합니다.
문제: 특정 구간에서의 최대값 구하기
주어진 배열의 특정 범위 내에서 최대값을 구하는 문제를 풀어보세요. 해당 문제를 누적 합을 활용해서 해결해보세요.
결론
구간 합 문제는 배열의 구간 내 합을 구하는 기본적인 알고리즘 문제입니다. 배열을 효율적으로 다루기 위해 누적 합 배열을 사용하는 방법을 배웠습니다. 이와 같은 기법은 더 복잡한 문제에서도 유용하게 활용될 수 있으므로 충분히 연습하시기 바랍니다.
이 글이 여러분의 C# 코딩 테스트 준비에 도움이 되었기를 바랍니다. 더 많은 알고리즘 문제를 풀어보며 실력을 키워보세요!