C 언어에서 각 요소를 이전 요소로 나눈 후 배열 합계 구하기

배열(Array)은 동일한 데이터 타입의 요소들이 순서대로 나열된 자료구조입니다. 이번 글에서는 정수 배열을 대상으로, 각 요소를 바로 앞의 요소(선행 요소)로 나눈 몫들을 모두 더한 합계를 구하는 방법을 알아보겠습니다.

먼저 예제를 통해 문제를 좀 더 구체적으로 이해해 보겠습니다.

예제 1

Array : 3, 5, 98, 345
Sum : 26

설명 — 3 + 5/3 + 98/5 + 345/98 = 3 + 1 + 19 + 3 = 26

각 요소를 바로 앞의 요소로 나눈 뒤, 나눗셈 결과에서 정수 부분(몫)만 취하여 합계를 계산했습니다. C 언어에서 정수형끼리 나누면 소수점 이하가 버려지므로, 별도의 변환 없이 정수 나눗셈 결과가 그대로 사용됩니다.

예제 2

Array : 2, 5, 8, 11, 43, 78, 234
Sum : 13

설명 — 2 + 2 + 1 + 1 + 3 + 1 + 3 = 13

알고리즘

이 알고리즘은 배열의 각 요소를 한 번씩 순회하면서, 현재 요소를 바로 앞의 요소로 나눈 몫을 sum 변수에 누적하여 더합니다.

Input : Array - int arr[]
Output : int sum

알고리즘의 동작 단계는 다음과 같습니다.

Step 1: sum = arr[0] 으로 초기화
Step 2: for(i = 1부터 배열 크기까지) Step 3 수행
Step 3: sum = sum + (arr[i] / arr[i-1])
Step 4: sum 출력

단 네 단계로 이전 숫자로 나눈 후의 배열 합계를 구할 수 있는 아주 간단한 알고리즘입니다. sum을 배열의 첫 번째 요소로 초기화하는 이유는, 첫 번째 요소는 그 앞에 나눌 대상이 되는 요소가 존재하지 않기 때문입니다. 만약 반복문을 인덱스 0부터 시작하면 arr[-1]에 접근하게 되어 잘못된 메모리 참조 오류가 발생할 수 있으므로, 반복은 반드시 인덱스 1부터 시작해야 합니다.

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않는 효율적인 방식입니다.

C 코드 예제

#include<stdio.h>
int main() {
    int arr[] = { 2, 5, 8, 11, 43, 78, 234 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = arr[0];
    for (int i = 1; i < n; i++) {
        sum += arr[i] / arr[i - 1];
    }
    printf("이전 숫자로 나눈 후 배열의 합계는 %d 입니다 \n", sum);
    return 0;
}

출력 결과

이전 숫자로 나눈 후 배열의 합계는 13입니다.

코드를 살펴보면 sizeof 연산자를 활용해 배열의 크기를 자동으로 계산하고, 첫 번째 요소로 sum을 초기화한 뒤 인덱스 1부터 마지막 요소까지 순회하며 정수 나눗셈의 몫을 누적합니다. 이처럼 C 언어의 정수 나눗셈 특성을 활용하면 복잡한 처리 없이도 손쉽게 원하는 합계를 구할 수 있습니다.