C++로 처음 n개의 자연수의 합 구하는 프로그램

이 튜토리얼에서는 처음 n개의 자연수의 합을 구하는 C++ 프로그램을 다뤄보겠습니다.

정수 n이 입력으로 주어지면, 1부터 n까지의 모든 자연수를 더한 합계를 계산하여 출력하는 것이 우리의 과제입니다.

반복문을 이용한 풀이

가장 기본적인 방법은 1부터 n까지 차례대로 반복하면서 값을 누적하는 것입니다. 아래 예제 코드를 살펴보세요.

예제 코드

#include<iostream>
using namespace std;

// 처음 n개의 자연수의 합을 반환하는 함수
int findSum(int n) {
    int sum = 0;
    for (int x = 1; x <= n; x++)
        sum = sum + x;
    return sum;
}

int main() {
    int n = 5;
    cout << findSum(n);
    return 0;
}

실행 결과

15

위 코드에서는 정수 n에 5를 대입했기 때문에, 1+2+3+4+5의 결과인 15가 출력됩니다. 이 방법의 시간 복잡도는 O(n)으로, n이 커질수록 연산 횟수도 비례해서 늘어납니다.

수학 공식을 이용한 효율적인 풀이

자연수의 합 공식인 n × (n + 1) / 2를 사용하면 반복문 없이도 한 번의 연산으로 결과를 얻을 수 있습니다. 이 경우 시간 복잡도는 O(1)로 매우 효율적입니다.

#include<iostream>
using namespace std;

// 가우스 공식을 이용한 합 계산
int findSum(int n) {
    return n * (n + 1) / 2;
}

int main() {
    int n = 5;
    cout << findSum(n);
    return 0;
}

실행 결과

15

마무리

두 방법 모두 동일한 결과를 출력하지만, n의 크기가 큰 경우에는 수학 공식을 활용하는 두 번째 방법이 훨씬 빠른 성능을 보여줍니다. 상황에 맞게 적절한 방법을 선택해 사용하시기 바랍니다.