문제 개요
이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어집니다. 우리의 목표는 C++에서 주어진 배열의 모든 요소의 합을 계산하는 프로그램을 작성하는 것입니다.
프로그램 설명 — 주어진 배열의 모든 요소를 순서대로 더한 뒤, 그 결과값(합계)을 반환합니다.
예시로 문제 이해하기
입력
arr[] = {3, 1, 7, 2, 9, 10}출력
32
설명
합 = 3 + 1 + 7 + 2 + 9 + 10 = 32
해결 접근 방법
배열 요소의 합을 구하려면 배열을 처음부터 끝까지 순회하면서 각 요소를 하나씩 꺼내 sumVal 변수에 누적하면 됩니다. 마지막에 sumVal에 저장된 값이 곧 배열의 총합입니다.
이를 구현하는 방법은 크게 두 가지가 있습니다.
- 재귀(Recursion)를 이용한 방법
- 반복문(Iteration)을 이용한 방법
방법 1: 재귀 접근 방식
재귀 방식은 배열의 마지막 요소부터 시작해, 현재 요소와 나머지 부분 배열의 합을 재귀적으로 더해 나가는 방법입니다. 기저 조건(base case)은 배열의 크기가 1일 때 해당 요소를 그대로 반환하는 것입니다.
예제 코드
#include <iostream>
using namespace std;
int calcArraySum(int arr[], int n){
if(n == 1){
return arr[n-1];
}
return arr[n-1] + calcArraySum(arr, n-1);
}
int main(){
int arr[] = {1, 4, 5, 7, 6};
int n = sizeof(arr)/ sizeof(arr[0]);
cout<<"The sum of elements in a given array is"<<calcArraySum(arr, n);
return 0;
}실행 결과
The sum of elements in a given array is 23
재귀 방식은 코드가 간결하고 직관적이라는 장점이 있지만, 호출될 때마다 스택 메모리를 사용하므로 배열의 크기가 매우 클 경우 스택 오버플로우가 발생할 수 있다는 점에 유의해야 합니다.
방법 2: 반복문 접근 방식
반복문 방식은 for 루프를 사용해 배열의 첫 번째 요소부터 마지막 요소까지 차례대로 순회하며 합계를 누적합니다. 실무에서는 메모리 효율성과 안정성 때문에 이 방식이 가장 널리 사용됩니다.
예제 코드
#include <iostream>
using namespace std;
int calcArraySum(int arr[], int n){
int sumVal = 0;
for(int i = 0; i < n; i++){
sumVal += arr[i];
}
return sumVal;
}
int main(){
int arr[] = {1, 4, 5, 7, 6};
int n = sizeof(arr)/ sizeof(arr[0]);
cout<<"The sum of elements in a given array is"<<calcArraySum(arr, n);
return 0;
}실행 결과
The sum of elements in a given array is 23
시간 복잡도 분석
두 방식 모두 배열의 모든 요소를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 다만 공간 복잡도 측면에서 반복문 방식은 추가 메모리가 필요 없는 O(1)인 반면, 재귀 방식은 함수 호출 스택 때문에 O(n)의 공간이 필요합니다. 따라서 일반적인 상황에서는 반복문 방식이 더 효율적인 선택입니다.