처음 n개 자연수의 제곱합의 합 구하기 (C 언어 예제)

처음 n개 자연수의 제곱합(square-sum)의 합이란, 1부터 n까지 각 숫자에 대해 그 숫자까지의 제곱합을 구하고, 이 값들을 모두 더한 것을 의미합니다.

예를 들어, 처음 4개 자연수에 대한 제곱합의 합은 다음과 같습니다.

sum = (1²) + (1² + 2²) + (1² + 2² + 3²) + (1² + 2² + 3² + 4²) = 1 + 5 + 14 + 30 = 50

처음 n개 자연수의 제곱합의 합을 구하는 두 가지 방법

1) for 반복문 사용하기

이 방법은 1부터 N까지 모든 숫자를 반복하면서 각 숫자까지의 제곱합을 계산하고, 그 결과를 sum 변수에 누적하여 더하는 방식입니다. n개의 숫자마다 반복 연산이 필요하기 때문에, 숫자가 커질수록 실행 시간이 오래 걸린다는 단점이 있습니다.

예제 코드

#include <stdio.h>
int main() {
    int n = 6;
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += ((i * (i + 1) * (2 * i + 1)) / 6);
    printf("처음 %d개 자연수의 제곱합의 합은 %d입니다", n, sum);
    return 0;
}

실행 결과

처음 6개 자연수의 제곱합의 합은 196입니다

2) 수학 공식 사용하기

수열의 일반항과 일반식을 분석하여 유도된 수학 공식을 활용하면 반복문 없이 한 번의 계산으로 결과를 구할 수 있습니다. 처음 n개 자연수의 제곱합의 합을 구하는 공식은 다음과 같습니다.

sum = n × (n+1) × (n+1) × (n+2) / 12

이 공식을 활용하면 시간 복잡도 O(1)로 매우 큰 n에 대해서도 빠르게 결과를 얻을 수 있습니다.

예제 코드

#include <stdio.h>
int main() {
    int n = 6;
    int sum = (n * (n + 1) * (n + 1) * (n + 2)) / 12;
    printf("처음 %d개 자연수의 제곱합의 합은 %d입니다", n, sum);
    return 0;
}

실행 결과

처음 6개 자연수의 제곱합의 합은 196입니다

두 방법 모두 동일한 결과를 출력하지만, 입력값이 클 경우에는 반복 연산이 필요 없는 수학 공식 기반 방법이 훨씬 효율적입니다.