안녕하세요! 오늘은 자바스크립트를 사용하여 구간 합을 구하는 문제를 다뤄보겠습니다. 구간 합 문제는 데이터 처리 및 배열 조작을 효율적으로 수행하는 방법을 배우는 데 큰 도움이 됩니다. 이 주제는 코딩 테스트와 알고리즘 문제풀이에서 빈번하게 등장하므로, 이 기회를 통해 철저히 이해해 보시길 바랍니다.
문제 설명
주어진 배열에서 특정 구간의 합을 효율적으로 구하는 함수 rangeSum(array, start, end)를 구현하세요. 여기서 array는 정수로 이루어진 배열이고, start와 end는 배열의 인덱스를 나타냅니다. 구간의 합은 array[start] + array[start + 1] + ... + array[end]로 정의됩니다.
입력
- 1 ≤
array.length≤ 105 - -109 ≤
array[i]≤ 109 - 0 ≤
start≤end<array.length
출력
구간의 합을 나타내는 정수를 반환합니다.
예제
입력: rangeSum([1, 2, 3, 4, 5], 1, 3)
출력: 9 // 2 + 3 + 4 = 9문제 풀이
구간 합을 구하기 위해서는 먼저 배열과 구간의 시작과 끝 인덱스를 이해해야 합니다. 우리가 해결해야 할 문제는 주어진 배열에서 특정 인덱스 범위 내의 모든 숫자를 더하는 것입니다. 하지만 배열의 크기가 커질 수 있기 때문에 효율적인 방법을 사용하는 것이 중요합니다.
단순한 반복문을 이용한 접근
가장 간단하고 직관적인 방법은 주어진 인덱스 범위에서 반복문을 사용하여 바로 구간의 합을 계산하는 것입니다. 이 방법의 시간 복잡도는 O(n)입니다.
function rangeSum(array, start, end) {
let sum = 0;
for (let i = start; i <= end; i++) {
sum += array[i];
}
return sum;
}위의 코드는 주어진 배열과 시작 및 끝 인덱스를 이용하여 범위 내의 모든 값을 더해주는 방식입니다. 단, 이 방법은 구간이 바뀔 때마다 처음부터 다시 계산해야 하므로 비효율적입니다.
더 효율적인 방법: 누적 합 배열
우선 배열을 한 번 스캔하여 누적 합을 저장하는 방법이 있습니다. 이 방법은 다음과 같은 절차로 이루어집니다.
- 누적 합 배열을 생성한다.
- 원본 배열을 바탕으로 누적 합을 계산한다.
- 구간 합을 구할 때는
sum[end] - sum[start - 1]로 간단히 계산한다.
구현하는 코드는 다음과 같습니다:
function rangeSum(array, start, end) {
const prefixSum = new Array(array.length).fill(0);
prefixSum[0] = array[0];
for (let i = 1; i < array.length; i++) {
prefixSum[i] = prefixSum[i - 1] + array[i];
}
return start > 0 ? prefixSum[end] - prefixSum[start - 1] : prefixSum[end];
}위의 방법은 시간 복잡도가 O(n)인 초기화 과정을 거친 뒤, 구간 합을 O(1)로 계산할 수 있습니다. 이렇게 한 번의 배열 스캔으로 누적 합을 구하게 되면, 이후에 계산해야 할 구간의 개수에 따라 매우 효율적으로 작동합니다.
시간 복잡도
첫 번째 방법인 단순 반복문 방법의 경우, 구간의 크기와 관계없이 O(n)의 시간 복잡도를 가집니다. 그러나 누적 합을 사용하는 방법은 초기 O(n)의 시간 복잡도 이후에 각 구간 합을 O(1)로 계산할 수 있기 때문에, 많은 쿼리가 발생할수록 이점이 많아집니다.
결론
오늘은 자바스크립트로 구간 합을 구하는 방법에 대해 알아보았습니다. 효율적으로 문제를 해결하는 방법을 배움으로써, 코딩 테스트에서 자주 직면하는 문제들을 극복할 수 있는 능력을 기르시길 바랍니다. 이제는 직접 다양한 배열을 가지고 테스트해보며 연습해 보세요!