C# 코딩테스트 강좌, 구간 합 구하기 3

코딩 테스트를 준비하는 많은 분들께서는 알고리즘 문제 풀이에 대한 체계적인 학습이 필요합니다. 오늘은 구간 합을 구하는 문제에 대해 다뤄보겠습니다. 특히, ‘구간 합 구하기 3’ 문제는 다양한 전략을 활용할 수 있는 흥미로운 문제입니다. 이 글에서는 문제의 정의, 풀이 방법, C# 코드를 통한 구현 및 시간 복잡성 분석까지 자세히 설명하겠습니다.

문제 정의

주어진 정수 배열 arr와 여러 쿼리 query가 있을 때, 각 쿼리는 구간의 시작과 끝을 나타냅니다. 우리의 목표는 각 쿼리의 구간 합을 효율적으로 계산하여 반환하는 것입니다.

예시

배열: arr = [1, 2, 3, 4, 5]
쿼리: query = [[1, 3], [0, 2], [2, 4]]
출력: [9, 6, 12]

위의 예시에서 첫 번째 쿼리는 인덱스 1부터 3까지의 구간을 의미하므로, 2 + 3 + 4 = 9가 됩니다. 나머지 쿼리들도 동일한 방식으로 처리할 수 있습니다.

문제 접근법

문제를 해결하는 여러 방법이 있지만, 배열의 원소 개수가 많을 경우 성능이 중요한 요소로 작용할 수 있습니다. 따라서 효율적인 알고리즘은 필수적입니다.

1. 전통적인 방법

가장 기본적인 접근법은 각 쿼리에 대해 배열의 값을 직접 합산하는 것입니다. 그러나 이러한 방법은 다음과 같은 문제점을 가집니다:

시간 복잡도가 O(n)으로, 쿼리 수가 많아지면 효율적이지 못합니다.
배열의 원소 개수가 많을 경우 매우 비효율적입니다.

2. 누적 합을 이용한 방법

보다 효율적으로 문제를 해결하기 위해 노출된 방법은 누적 합을 사용하는 것입니다. 누적 합 배열은 다음과 같이 정의됩니다:

sum[i] = arr[0] + arr[1] + ... + arr[i]

이렇게 구해진 누적 합 배열을 통해 주어진 구간 합을 빠르게 계산할 수 있습니다. 구간 [left, right]의 합은 sum[right] - sum[left - 1]로 구해집니다. 이러한 방식으로 시간 복잡도를 O(1)로 줄일 수 있습니다.

3. C# 코드 구현

이제 주어진 문제를 바탕으로 C# 언어를 사용하여 누적 합을 계산하는 코드를 구현해 보겠습니다.


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 배열 및 쿼리 정의
        int[] arr = { 1, 2, 3, 4, 5 };
        int[][] queries = { new int[] { 1, 3 }, new int[] { 0, 2 }, new int[] { 2, 4 } };

        // 구간합을 저장할 리스트
        List results = new List();

        // 누적 합 배열 생성
        int[] prefixSum = new int[arr.Length];
        prefixSum[0] = arr[0];

        for (int i = 1; i < arr.Length; i++)
        {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // 각 쿼리에 대해 구간 합 계산
        foreach (var query in queries)
        {
            int left = query[0];
            int right = query[1];

            if (left == 0)
            {
                results.Add(prefixSum[right]);
            }
            else
            {
                results.Add(prefixSum[right] - prefixSum[left - 1]);
            }
        }

        // 결과 출력
        Console.WriteLine(string.Join(", ", results));
    }
}

코드 분석 및 설명

위 코드에서는 배열을 미리 누적 합으로 변환하여 각 쿼리의 구간 합을 O(1) 시간 내에 계산할 수 있도록 설계했습니다. 다음과 같은 단계로 진행됩니다:

누적 합 배열 생성: 배열의 첫 번째 원소를 초기화한 후, 반복문을 통해 각 원소의 누적 합을 계산합니다.
쿼리 수행: 각 쿼리를 순회하며 구간 합을 계산합니다. 만약 왼쪽 경계가 0이면, 바로 누적 합을 가져오고, 그렇지 않으면 두 원소의 차를 통해 구간 합을 구합니다.
결과 출력: 각각의 결과를 출력합니다.

시간 복잡성 분석

이 알고리즘의 시간 복잡성은 다음과 같습니다:

누적 합 배열을 만들기 위한 시간: O(n)
각 쿼리에 대한 구간 합 계산 시간: O(1) (쿼리 수에 비례)

따라서 전체 시간 복잡성은 O(n + m)으로 나타낼 수 있으며, 여기서 m은 쿼리의 수입니다. 이는 많은 쿼리를 처리해야 할 때 효율적인 방법입니다.

마무리

오늘은 “구간 합 구하기 3” 문제를 통해 효율적인 알고리즘을 설계하고 구현하는 방법에 대해 살펴보았습니다. 알고리즘 문제는 단순한 개념일 수 있지만, 다양한 접근 방식을 통해 해결책을 찾는 것은 코딩 테스트에 있어 매우 중요한 기술입니다. 이 강좌를 통해 여러분이 직접 코드를 작성하고, 문제를 해결하는 과정에서 많은 도움을 얻기를 바랍니다.

코드의 활용, 알고리즘의 개선을 통해 여러분의 코딩 테스트 실력을 한 단계 끌어올리길 바랍니다. 다음 강좌에서 또 만나요!