문제 설명
주어진 정수 배열 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) // 92. 누적 합 배열을 통한 접근 방법
단순 반복문은 경우에 따라 성능 저하를 유발할 수 있습니다. 특히 큰 크기의 배열에 대해 여러 번 구간 합을 구해야 할 경우, 매번 반복문을 수행하는 것은 비효율적입니다. 이럴 때 사용할 수 있는 방법이 바로 누적 합 배열을 사용하는 것입니다.
누적 합 배열을 사용하면, 배열의 특정 구간에 대한 합을 상수 시간 O(1)에 계산할 수 있습니다. 접근 방식은 다음과 같습니다.
- 배열의 크기만큼 누적 합 배열을 생성합니다.
- 누적 합 배열의 각 인덱스에 대해 이전 인덱스의 누적 합을 더합니다.
- 구간 합을 구할 때는
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사례 분석
이번 강좌에서는 두 가지 접근 방식을 통해 구간 합 문제를 해결해보았습니다. 단순 반복문을 이용한 방법은 직관적이고 이해하기 쉬운 장점이 있지만, 큰 배열의 경우 성능 저하를 초래할 수 있습니다. 반면 누적 합 배열을 활용한 방법은 성능적으로 우수한 방식입니다.
결론
구간 합 문제는 알고리즘과 자료구조를 활용하는 좋은 예시입니다. 효율적인 접근 방식을 통해 문제를 더욱 빠르게 해결할 수 있다는 것을 배웠습니다. 스위프트를 사용하여 이러한 문제를 해결하고 다양한 알고리즘 기술을 익혀보세요.
참고 자료
- 스위프트 공식 문서: developer.apple.com
- 자료구조와 알고리즘 책: example.com