Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 수열 1 + 2 + 2 + 3 + 3 + 3 + ... + n의 합 구하기

이 문제에서는 수열의 n번째 항을 나타내는 숫자 n이 주어집니다. 우리의 과제는 C++로 수열 1 + 2 + 2 + 3 + 3 + 3 + ... + n의 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

이 수열은 각 숫자 n이 자신과 같은 횟수만큼 반복되어 더해지는 형태입니다. 즉, 이는 제곱수들의 합으로 표현되는 수열입니다.

예시로 문제 이해하기

입력

n = 4

출력

30

설명

4번째 항까지의 수열의 합 = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 30

해결 방법 1: 중첩 반복문 사용 (단순한 방법)

가장 직관적인 해결책은 수열의 항들을 n까지 직접 더하는 것입니다. 이를 위해서는 두 개의 중첩 반복문이 필요합니다. 바깥쪽 반복문은 항을 처리하고, 안쪽 반복문은 각 항 내부의 값을 처리합니다.

알고리즘

초기화: sumVar = 0;

  • 1단계 — i를 1부터 n까지 반복합니다.
    • 1.1단계 — j를 1부터 i까지 반복합니다.
      • 1.1.1단계 — sumVar를 갱신합니다: sumVar += i;
  • 2단계 — sumVar를 출력합니다.

예제 코드

#include <iostream>
using namespace std;

int calcSeriesSum(int n){
    int sumVar = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            sumVar += i;
        }
    }
    return sumVar;
}

int main(){
    int n = 7;
    cout << "7번째 항까지 수열의 합은 " << calcSeriesSum(n);
    return 0;
}

출력

7번째 항까지 수열의 합은 140

이 방법은 구현이 간단하지만, 두 개의 중첩 반복문을 사용하기 때문에 시간 복잡도가 O(n²)이 되어 효율적이지 않습니다.

해결 방법 2: 단일 반복문 사용 (효율적인 방법)

더 효율적인 해결책은 다음 사실에 기반합니다. 어떤 숫자(n)를 자기 자신에게 n번 더하면, 그 결과는 곱셈으로 얻을 수 있습니다.

예를 들어, 5+5+5+5+5 = 5×5 입니다.

따라서 한 개의 반복문을 곱셈으로 대체하여 문제를 해결할 수 있습니다.

알고리즘

초기화: sumVal = 0;

  • 1단계 — i를 1부터 n까지 반복합니다.
  • 2단계 — sumVal을 갱신합니다: sumVal += (i * i)

예제 코드

#include <iostream>
using namespace std;

int calcSeriesSum(int n){
    int sumVar = 0;
    for(int i = 1; i <= n; i++){
        sumVar += (i*i);
    }
    return sumVar;
}

int main(){
    int n = 7;
    cout << "7번째 항까지 수열의 합은 " << calcSeriesSum(n);
    return 0;
}

출력

7번째 항까지 수열의 합은 140

이 방법은 반복문을 하나만 사용하므로 시간 복잡도가 O(n)으로 더 좋습니다. 하지만 이 역시 최선의 방법은 아닙니다. 동일한 결과를 O(1)의 시간 복잡도로 얻을 수 있기 때문입니다.

해결 방법 3: 일반 공식 사용 (가장 효율적인 방법)

가장 효율적인 해결책은 주어진 수열의 합에 대한 일반 공식을 활용하는 것입니다.

수열의 합은 다음과 같습니다.

1 + 2 + 2 + 3 + 3 + 3 + ... + N

이를 다음과 같이 변형할 수 있습니다.

1×1 + 2×2 + 3×3 + ... + N×N
= 1² + 2² + 3² + ... + N²

즉, 이 수열의 합은 처음 n개의 자연수 제곱의 합과 같습니다. 제곱의 합 공식은 다음과 같습니다.

합 = n × (n+1) × (2n+1) / 6

이 공식을 사용하면 반복문 없이 상수 시간에 답을 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;

int calcSeriesSum(int n){
    int sumVar = ((n*(n + 1)*(2*n + 1)) / 6);
    return sumVar;
}

int main(){
    int n = 7;
    cout << "7번째 항까지 수열의 합은 " << calcSeriesSum(n);
    return 0;
}

출력

7번째 항까지 수열의 합은 140

결론

세 가지 접근 방식을 비교하면 다음과 같습니다.

  • 중첩 반복문: 시간 복잡도 O(n²) — 직관적이지만 비효율적
  • 단일 반복문: 시간 복잡도 O(n) — 개선된 방법
  • 수학 공식: 시간 복잡도 O(1) — 가장 빠르고 효율적

실무에서는 수학적 성질을 활용한 O(1) 공식 기반 접근법이 가장 권장됩니다. 큰 입력값에서도 즉각적인 결과를 얻을 수 있기 때문입니다.