처음 n개의 홀수의 제곱합 구하기: 공식과 C 언어 예제

처음 n개의 홀수의 제곱합이란?

처음 n개의 홀수를 순서대로 제곱한 값들을 모두 더하는 것이 이 문제의 목표입니다.

홀수의 제곱으로 이루어진 수열은 다음과 같습니다.

1, 9, 25, 49, 81, 121 …

각 항이 홀수의 제곱이라는 점을 이용하면, 이 수열을 다음과 같이 일반화하여 나타낼 수 있습니다.

1², 3², 5², 7², 9², 11² …

제곱합을 구하는 수학 공식

이 수열의 합은 다음 공식을 사용하면 반복 계산 없이 한 번에 구할 수 있습니다.

합 = n(2n+1)(2n−1)/3 = n(4n² − 1)/3

예시

입력: N = 4
출력: 합 = 84

풀이 과정

① 직접 계산하는 방법

1² + 3² + 5² + 7² = 1 + 9 + 25 + 49 = 84

② 공식을 적용하는 방법

합 = 4 × (4 × 4² − 1) / 3 = 4 × (64 − 1) / 3 = 4 × 63 / 3 = 4 × 21 = 84

두 방법 모두 올바른 결과를 얻지만, 수학 공식을 활용하면 반복문 없이 단 한 번의 연산으로 답을 구할 수 있습니다. 반복문 기반 구현의 시간 복잡도가 O(n)인 반면, 공식 기반 구현은 O(1)이므로 n이 커질수록 성능 차이가 더욱 커집니다.

방법 1: 반복문을 이용한 구현

i번째 홀수는 (2i − 1)이므로, 이를 제곱한 값을 반복적으로 누적하면 됩니다.

#include <stdio.h>
int main() {
    int n = 8;
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += (2*i - 1) * (2*i - 1);
    printf("The sum of square of first %d odd numbers is %d", n, sum);
    return 0;
}

실행 결과

The sum of square of first 8 odd numbers is 680

방법 2: 수학 공식을 이용한 구현

공식 n(4n² − 1)/3을 그대로 코드로 옮기면 반복문 없이 즉시 결과를 얻을 수 있습니다.

#include <stdio.h>
int main() {
    int n = 18;
    int sum = ((n*((4*n*n)-1))/3);
    printf("The sum of square of first %d odd numbers is %d", n, sum);
    return 0;
}

실행 결과

The sum of square of first 18 odd numbers is 7770

정리

처음 n개의 홀수의 제곱합은 공식 n(4n² − 1)/3을 사용하면 상수 시간(O(1)) 안에 계산할 수 있습니다. 반복문을 사용하는 방법(O(n))도 직관적이고 이해하기 쉽지만, 입력 크기가 커지는 경우에는 공식 기반 구현이 훨씬 효율적이므로 실무에서는 공식 활용을 권장합니다.