스위프트 코딩테스트 강좌, 구간 합

문제 설명

주어진 정수 배열 nums와 두 개의 정수 start, end가 주어질 때, nums[start] + nums[start + 1] + ... + nums[end]의 값을 구하는 문제입니다. 구간 합을 효율적으로 계산하기 위한 방법과 스위프트 언어로 이 문제를 어떻게 해결할 수 있는지를 살펴보겠습니다.

입력 예시

[1, 2, 3, 4, 5], start = 1, end = 3

출력 예시

9

문제 접근 방법

이 문제를 해결하기 위해서는 구간 덧셈을 어떻게 효율적으로 수행할 수 있을지를 고려해야 합니다. 단순한 방법으로는 for 루프를 사용하여 주어진 인덱스 범위의 합을 구하는 것입니다. 그러나 이 방법은 개선의 여지가 많습니다.

1. 단순 반복문을 통한 합 계산

먼저 가장 기본적인 방법을 살펴보겠습니다. 주어진 범위에 대해 반복문을 사용하여 합을 구하는 방법입니다. 다음은 이 방법을 구현한 스위프트 코드입니다.

func rangeSum(nums: [Int], start: Int, end: Int) -> Int {
        var sum = 0
        for i in start...end {
            sum += nums[i]
        }
        return sum
    }

사용 예시

let nums = [1, 2, 3, 4, 5]
let result = rangeSum(nums: nums, start: 1, end: 3)
print(result) // 9

2. 누적 합 배열을 통한 접근 방법

단순 반복문은 경우에 따라 성능 저하를 유발할 수 있습니다. 특히 큰 크기의 배열에 대해 여러 번 구간 합을 구해야 할 경우, 매번 반복문을 수행하는 것은 비효율적입니다. 이럴 때 사용할 수 있는 방법이 바로 누적 합 배열을 사용하는 것입니다.

누적 합 배열을 사용하면, 배열의 특정 구간에 대한 합을 상수 시간 O(1)에 계산할 수 있습니다. 접근 방식은 다음과 같습니다.

  1. 배열의 크기만큼 누적 합 배열을 생성합니다.
  2. 누적 합 배열의 각 인덱스에 대해 이전 인덱스의 누적 합을 더합니다.
  3. 구간 합을 구할 때는 prefixSum[end + 1] - prefixSum[start]을 통해 쉽게 구간 합을 계산합니다.

누적 합 배열 구현 코드

func rangeSumUsingPrefix(nums: [Int], start: Int, end: Int) -> Int {
        var prefixSum = [0]    // 누적 합 배열 초기화
        prefixSum.append(0)    // 첫 번째 인덱스는 0으로 초기화
        
        // 누적 합 배열 생성
        for num in nums {
            prefixSum.append(prefixSum.last! + num)
        }
        
        // 구간 합 계산
        return prefixSum[end + 1] - prefixSum[start]
    }

사용 예시

let nums = [1, 2, 3, 4, 5]
let result = rangeSumUsingPrefix(nums: nums, start: 1, end: 3)
print(result) // 9

사례 분석

이번 강좌에서는 두 가지 접근 방식을 통해 구간 합 문제를 해결해보았습니다. 단순 반복문을 이용한 방법은 직관적이고 이해하기 쉬운 장점이 있지만, 큰 배열의 경우 성능 저하를 초래할 수 있습니다. 반면 누적 합 배열을 활용한 방법은 성능적으로 우수한 방식입니다.

결론

구간 합 문제는 알고리즘과 자료구조를 활용하는 좋은 예시입니다. 효율적인 접근 방식을 통해 문제를 더욱 빠르게 해결할 수 있다는 것을 배웠습니다. 스위프트를 사용하여 이러한 문제를 해결하고 다양한 알고리즘 기술을 익혀보세요.

참고 자료