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

문제 정의

주어진 정수 배열 nums와 두 정수 left, right가 있습니다. 우리는 nums 내에서 인덱스 left에서 right까지의 구간 합을 계산하는 문제를 해결해야 합니다. 구간 sum을 다음의 수식으로 정의합니다:

sum = nums[left] + nums[left + 1] + ... + nums[right]

배열의 길이는 1 이상 10^5 이하이며, left와 right는 각각 0과 nums.Length - 1 사이의 값입니다.

예제

입력

nums = [1, 2, 3, 4, 5]
left = 1
right = 3

출력

sum = 9

여기서 구간 합은 2 + 3 + 4 = 9입니다.

문제 접근 방법

이 문제를 해결하기 위해서는 두 가지 접근 방법을 고려할 수 있습니다:

• 직접적인 반복문을 사용한 방법
• 더 효율적인 방법으로 접두사 배열을 사용하는 방법

1. 직접적인 반복문 사용

먼저, 가장 간단한 방법은 해당 구간을 반복문을 통해 순회하며 합을 구하는 것입니다. 하지만 이 방법은 구간의 크기가 클 경우 시간 복잡도가 O(n)이 되어 비효율적입니다.

2. 접두사 배열 사용

이 문제를 더 효율적으로 해결하기 위해 접두사 배열을 사용할 수 있습니다. 접두사 배열(Prefix Sum)은 주어진 배열의 각 인덱스에서의 누적 합을 저장하여 반복문을 줄여줍니다.

접두사 배열을 구성하는 과정은 다음과 같습니다:

prefix[0] = nums[0]
prefix[i] = prefix[i - 1] + nums[i] (1 ≤ i < nums.Length)

이렇게 구성된 접두사 배열을 활용하면, 구간 합을 O(1)의 시간 복잡도로 계산할 수 있습니다. 구간 합은 다음과 같이 계산됩니다:

sum = prefix[right] - prefix[left - 1] (left > 0)
sum = prefix[right] (left == 0)

C# 코드 구현

이제 위에서 설명한 방법으로 C# 코드를 작성해 보겠습니다. 아래의 코드는 입력으로 주어진 배열 및 구간을 바탕으로 구간 합을 계산합니다.

코드

using System;

class Program {
    static void Main(string[] args) {
        int[] nums = { 1, 2, 3, 4, 5 };
        int left = 1;
        int right = 3;

        int result = GetRangeSum(nums, left, right);
        Console.WriteLine(result);
    }

    static int GetRangeSum(int[] nums, int left, int right) {
        int n = nums.Length;
        int[] prefix = new int[n];
        prefix[0] = nums[0];

        // 접두사 배열 초기화
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        // 구간 합 계산
        if (left == 0) {
            return prefix[right];
        }
        return prefix[right] - prefix[left - 1];
    }
}

이 코드는 주어진 배열 nums와 구간 left와 right를 인자로 받아서 구간 합을 반환합니다. 접두사 배열을 사용하여 구간 합을 효율적으로 계산할 수 있습니다.

복잡도 분석

이제 우리가 작성한 코드의 시간 및 공간 복잡도를 분석해 보겠습니다.

시간 복잡도

접두사 배열을 초기화하는 과정은 O(n)의 시간 복잡도를 가지며, 구간 합을 계산하는 과정은 O(1)의 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도는 O(n)입니다.

공간 복잡도

접두사 배열을 저장하기 위해 O(n)의 추가 공간이 필요하므로, 공간 복잡도 또한 O(n)입니다.

결론

이번 포스트에서는 구간 합 구하기 문제를 다루었습니다. 접두사 배열을 활용한 효율적인 접근 방법을 통해 구간 합을 O(1)의 시간 복잡도로 계산할 수 있게 되었습니다. 이 기법은 다양한 알고리즘 문제에 유용하게 적용될 수 있으므로, 꼭 기억해 두시기 바랍니다.

다음 포스트에서는 또 다른 알고리즘 문제를 다루겠습니다. 감사합니다!