C++로 처음 n개 자연수의 제곱합 구하기

이 글에서는 처음 n개의 자연수(1부터 n까지)의 제곱합을 구하는 C++ 프로그램 작성 방법을 살펴보겠습니다.

반복문을 이용한 기본 접근 방식

가장 직관적인 방법은 1부터 n까지 반복하는 for 루프를 사용하는 것입니다. 각 반복 단계에서 현재 항의 제곱을 계산한 뒤 합계 변수에 더해주면 됩니다. 이 방식은 n번 반복하기 때문에 시간 복잡도가 O(n)입니다.

알고리즘: squareNNatural(n)

begin
    sum := 0
    for i in range 1 to n, do
        sum := sum + i^2
    done
    return sum
end

O(1) 상수 시간 해법: 수열 공식 활용

n이 매우 큰 경우 반복문 방식은 비효율적일 수 있습니다. 다행히 처음 n개 자연수의 제곱합은 잘 알려진 닫힌 형태(closed-form) 공식으로 한 번의 계산으로 구할 수 있으며, 이 경우 시간 복잡도는 O(1), 즉 상수 시간입니다.

Σi² = n(n+1)(2n+1) / 6

C++ 구현 예제

#include<iostream>
using namespace std;
long square_sum_n_natural(int n) {
    long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i * i; // i를 제곱하여 합계에 더함
    }
    return sum;
}
main() {
    int n;
    cout << "Enter N: ";
    cin >> n;
    cout << "Result is: " << square_sum_n_natural(n);
}

실행 결과

Enter N: 4
Result is: 30

위 실행 결과를 공식으로 검증해 보면, n = 4일 때 4 × 5 × 9 / 6 = 180 / 6 = 30으로 동일한 값이 나옵니다. 따라서 입력 크기가 클수록 반복문 대신 공식을 사용하는 것이 훨씬 효율적입니다.