C++에서 2⁰ + 2¹ + 2² + … + 2ⁿ 수열의 합 구하기

이 문제에서는 하나의 숫자 n이 주어지며, 이 값은 수열 2⁰, 2¹, 2², …, 2ⁿ의 마지막 항을 결정합니다. 우리의 목표는 2⁰ + 2¹ + 2² + … + 2ⁿ 수열의 전체 합을 구하는 프로그램을 작성하는 것입니다.

예제로 문제 이해하기

입력

n = 6

출력

127

설명

sum = 2⁰ + 2¹ + 2² + 2³ + 2⁴ + 2⁵ + 2⁶
sum = 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127

방법 1: 반복문을 이용한 풀이

가장 직관적인 방법은 반복문(loop)을 사용하는 것입니다. 0부터 n까지 각 값 i에 대해 2ⁱ를 계산한 뒤, sum 변수에 차례대로 더해주면 됩니다.

알고리즘

sum = 0으로 초기화
Step 1: i = 0부터 n까지 반복하며 다음을 수행한다.
Step 1.1: sum += 2ⁱ 로 sum 값을 갱신한다.
Step 2: sum을 출력한다.

구현 예제

아래 프로그램은 위 알고리즘이 실제로 동작하는 모습을 보여줍니다.

#include <iostream>
#include <math.h>
using namespace std;
int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++)
        sum += pow(2, i);
    return sum;
}
int main() {
    int n = 11;
    cout<<"Sum of the series 2^0 + 2^1 + 2^2 +...+ 2^"<<n<<" is "<<calcSeriesSum(n);
    return 0;
}

실행 결과

Sum of the series 2^0 + 2^1 + 2^2 +...+ 2^11 is 4095

이 방법은 코드가 단순하고 이해하기 쉽다는 장점이 있지만, 반복문을 사용하기 때문에 시간 복잡도가 O(n)으로 효율적이지 않습니다. n이 커질수록 실행 시간도 그에 비례해서 늘어나게 됩니다.

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

더 효율적인 접근 방식은 등비수열의 합 공식을 활용하는 것입니다. 2의 거듭제곱 수열의 합은 다음 공식으로 한 번에 계산할 수 있습니다.

합 = 2^(n+1) − 1

이 공식을 사용하면 반복문 없이 단 한 번의 연산만으로 결과를 얻을 수 있으므로, 성능 면에서 큰 이점을 가집니다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;
int calcSeriesSum(int n) {
    return ((pow(2, (n+1)) - 1));
}
int main() {
    int n = 11;
    cout<<"Sum of the series 2^0 + 2^1 + 2^2 +...+ 2^"<<n<<" is "<<calcSeriesSum(n);
    return 0;
}

실행 결과

Sum of the series 2^0 + 2^1 + 2^2 +...+ 2^11 is 4095

추가 최적화: 비트 시프트 활용하기

2의 거듭제곱은 비트 시프트(bit shift) 연산으로 대체할 수 있습니다. pow(2, n+1) 대신 (1 << (n+1))을 사용하면 부동소수점 연산 없이 더 빠르고 정확하게 결과를 얻을 수 있습니다.

int calcSeriesSum(int n) {
    return (1 << (n + 1)) - 1;
}

마무리

반복문을 이용한 방법은 직관적이지만 O(n)의 시간이 소요되는 반면, 수학 공식 2^(n+1) − 1 또는 비트 시프트를 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 입력 크기가 커질 가능성이 있는 경우에는 공식 기반의 접근 방식을 사용하는 것이 바람직합니다.