배열의 각 요소를 이전 요소로 나눈 후 합계 구하기

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 배열을 하나 입력받은 뒤, 각 요소를 바로 앞에 있는 요소로 나눈 값을 모두 더해 최종 합계를 구하는 것입니다.

예를 들어 배열이 {5, 6, 7, 2, 1, 4}라고 가정해 보겠습니다. 이때 계산 과정은 다음과 같습니다.

5 + (6 / 5) + (7 / 6) + (2 / 7) + (1 / 2) + (4 / 1) = 12.15238

첫 번째 요소인 5는 나눌 이전 요소가 없기 때문에 그대로 더해집니다. 그럼 개념을 확실히 이해할 수 있도록 알고리즘부터 살펴보겠습니다.

알고리즘

divSum(arr, n)

begin
    sum := arr[0]
    for i := 1 to n-1, do
       sum := sum + arr[i] / arr[i-1]
    done
    return sum
end

알고리즘의 동작 방식은 매우 간단합니다. 먼저 첫 번째 요소를 초기 합계로 설정한 후, 두 번째 요소부터 마지막 요소까지 순회하면서 현재 요소를 이전 요소로 나눈 값을 합계에 계속 누적하면 됩니다. 전체 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다.

예제 코드 (C++)

#include <iostream>
using namespace std;
float divSum(int arr[], int n){
    float sum = arr[0];
    for(int i = 1; i<n; i++){
        sum += arr[i] / float(arr[i - 1]);
    }
    return sum;
}
int main() {
    int arr[6] = {5, 6, 7, 2, 1, 4};
    int n = 6;
    cout << "Sum : " << divSum(arr, n);
}

코드에서 주목할 부분은 arr[i] / float(arr[i - 1])입니다. 정수형 배열을 그대로 나누면 정수 나눗셈이 수행되어 소수점 이하가 잘려나가기 때문에, 이전 요소를 명시적으로 float 타입으로 변환하여 실수 나눗셈이 이루어지도록 처리했습니다.

출력 결과

Sum : 12.1524

출력 결과를 보면 예상했던 값인 12.15238이 소수 넷째 자리에서 반올림된 12.1524로 표시되는 것을 확인할 수 있습니다. 이처럼 간단한 반복문 하나만으로 배열 요소들을 이전 요소로 나눈 값의 합계를 손쉽게 구할 수 있습니다.