C++로 급수의 합 구하기: 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+...+(2n-1))

이 문제에서는 숫자 n이 주어지며, 우리의 목표는 다음 급수의 합을 구하는 프로그램을 작성하는 것입니다.

1 + (1+3) + (1+3+5) + (1+3+5+7) + …… + (1+3+5+7+…+(2n-1))

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력: n = 5
출력: 55

사용자가 숫자 'n'을 입력하면, 위 급수를 모두 더한 값을 출력해야 합니다. 먼저 이 급수가 어떤 의미를 갖는지 자세히 알아보겠습니다.

n=1일 때, 급수는 단순히 1입니다.

n=2일 때, 마지막 항인 2n-1은 2×2-1 = 3이 되므로, 급수는 1 + (1+3)이 됩니다.

즉, 각 괄호 안의 항은 홀수(1, 3, 5, 7...)를 차례대로 더한 값입니다. 표로 정리하면 다음과 같습니다.

n 값	2n-1	급수 형태
1	1	1
2	3	1 + (1+3)
3	5	1 + (1+3) + (1+3+5)
4	7	1 + (1+3) + (1+3+5) + (1+3+5+7)

풀이 방법

이 문제는 두 가지 방법으로 해결할 수 있습니다.

반복문을 사용한 직접 접근: 중첩 반복문(nested loop)을 이용해 각 항을 직접 계산하는 방식
수학적 접근: 전체 합에 대한 일반화된 공식을 유도하여 반복문 없이 한 번에 계산하는 방식

방법 1: 중첩 반복문을 이용한 직접 접근

급수의 각 항 자체가 또 하나의 급수이기 때문에 중첩 반복문을 사용합니다. 바깥쪽 반복문은 몇 번째 항까지 더할지를 결정하고, 안쪽 반복문은 해당 항(홀수들의 합)을 실제로 계산합니다.

코드 예제

#include<stdio.h>

int calcSum(int n){
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        // 각 항의 첫 번째 값은 항상 1
        int value = 1;
        for (int j = 1; j <= i; j++) {
            sum += value;
            // 다음 홀수로 이동
            value += 2;
        }
    }
    return sum;
}

int main(){
    int n = 35;
    printf("The sum of the series upto %d is %d ", n , calcSum(n));
}

출력 결과

The sum of the series upto 35 is 14910

프로그램 동작 원리

n = 2를 입력했다고 가정하고 프로그램의 실행 과정을 단계별로 살펴보겠습니다.

합계를 저장할 변수 sum을 선언하고 초기값을 0으로 설정합니다.
i = 1일 때, 조건 i <= n이 참이므로 바깥쪽 반복문이 실행됩니다.
- 변수 value의 값은 1입니다.
- j = 1일 때, j와 i의 값이 같으므로 조건이 참이고 안쪽 반복문이 실행됩니다.
- value 값을 sum에 더하면 sum은 0 + 1 = 1이 됩니다.
- value가 2 증가하여 새 값은 1 + 2 = 3이 됩니다.
- j가 1 증가하여 2가 되지만, 이제 j > i이므로 안쪽 반복문의 조건이 거짓이 되어 반복문을 빠져나옵니다.
i가 1 증가하여 i = 2가 되고, 조건 i <= n이 여전히 참이므로 반복문에 다시 진입합니다.
- 변수 value가 다시 1로 초기화됩니다.
- j = 1일 때, j < i (1 < 2)이므로 반복문이 실행됩니다.
- value를 sum에 더합니다. sum의 현재 값은 1이므로 새 값은 1 + 1 = 2가 됩니다.
- value가 2 증가하여 3이 됩니다.
- j가 1 증가하여 2가 됩니다. j == i이므로 조건이 참입니다.
- value를 sum에 더합니다. sum의 현재 값은 2이므로 새 값은 2 + 3 = 5가 됩니다.
- value가 2 증가하여 5가 됩니다.
- j가 다시 증가하면 조건이 거짓이 되어 반복문을 종료합니다.
i가 1 증가하여 i = 3이 되지만, n = 2이므로 조건 i <= n이 거짓이 되어 바깥쪽 반복문도 종료됩니다.
최종적으로 메시지와 함께 sum의 값이 화면에 출력됩니다.

방법 2: 수학적 공식을 이용한 접근

문제를 수학적으로 분석한 후 코드를 작성하면 코드를 크게 단순화할 수 있습니다.

먼저 알아두어야 할 핵심 사실은 다음과 같습니다.

처음 n개의 홀수의 합, 즉 1+3+5+7+9…+(2n-1)의 합은 n²입니다.
따라서 주어진 급수의 총합은 1² + 2² + 3² + 4² + … + n²이 되며, 이는 제곱수의 합 공식 n(n+1)(2n+1)/6으로 계산할 수 있습니다.

즉, 각 항 T_k = k²이고, 전체 합은 Σk² (k=1부터 n까지)이므로 반복문 없이 O(1) 시간 복잡도로 답을 구할 수 있습니다.

코드 예제

#include<stdio.h>

int calcSum(int n){
    // 요구되는 합: n(n+1)(2n+1)/6
    return (( (n) * (n + 1) * (2*n + 1 ) )/6 ) ;
}

int main(){
    int n = 35;
    printf("The sum of the series upto %d is %d ", n , calcSum(n));
}

출력 결과

The sum of the series upto 35 is 14910

프로그램 동작 원리

사용자가 n = 2를 입력했다고 가정해 보겠습니다. 그러면 2n-1의 값은 3이 되고, 급수는 1 + (1+3)이 됩니다. 코드를 통해 합을 구하는 과정은 다음과 같습니다.

calcSum() 함수가 인자 값 2로 호출됩니다.
함수 내부에서 공식 n(n+1)(2n+1)/6에 따라 2×3×5/6 = 5를 계산하고, 이 값을 main 함수로 반환합니다.
main 함수는 결과 메시지와 함께 답을 화면에 출력합니다.

마무리

중첩 반복문을 사용한 방법은 시간 복잡도가 O(n²)인 반면, 수학 공식을 활용한 방법은 O(1)로 훨씬 효율적입니다. 입력 크기가 클수록 수학적 접근 방식이 성능 면에서 확실한 이점을 제공하므로, 알고리즘 설계 시 패턴을 찾아 공식으로 일반화하는 습관을 들이는 것이 좋습니다.