이 문제에서는 수열 2 + (2+4) + (2+4+6) + (2+4+6+8) + ... + (2+4+6+8+...+2n)이 주어지고, 숫자 n은 이 수열의 n번째 항을 정의합니다. 우리의 목표는 이 수열의 전체 합을 구하는 프로그램을 작성하는 것입니다.
문제 이해를 위한 예시
입력
n = 3
출력
20
설명 − 합 = (2) + (2+4) + (2+4+6) = 2 + 6 + 12 = 20
방법 1: 중첩 반복문을 사용한 단순 해법
가장 직관적인 방법은 중첩 반복문(nested loop)을 사용하는 것입니다. 내부 반복문이 수열의 i번째 항(짝수들의 합)을 계산하고, 각 항을 sum 변수에 누적하여 전체 합을 구합니다.
예제 코드
아래 프로그램은 이 해법의 동작 방식을 보여줍니다.
#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
int sum = 0;
for (int i = 1; i<=n; i++) {
int even = 2;
for (int j = 1; j<=i; j++) {
sum += even;
even += 2;
}
}
return sum;
}
int main() {
int n = 5;
cout<<"Sum of the series 2 + (2+4) + (2+4+6) + ... + (2+4+6+...+"<<(2*n)<<") is "<<calcSeriesSum(n);
return 0;
}출력 결과
Sum of the series 2 + (2+4) + (2+4+6) + ... + (2+4+6+...+10) is 70
이 방법은 구현이 간단하지만 효율적이지 않습니다. 외부 반복문과 내부 반복문이 모두 n에 비례하여 실행되므로 시간 복잡도는 O(n²)입니다. n이 커질수록 실행 시간이 급격히 늘어나기 때문에 더 나은 접근 방식이 필요합니다.
방법 2: 수학 공식을 활용한 효율적인 해법
수열의 일반항을 분석하면 O(1) 시간 복잡도로 답을 구할 수 있는 공식을 유도할 수 있습니다.
주어진 수열은 다음과 같습니다.
2 + (2+4) + (2+4+6) + (2+4+6+8) + ... + (2+4+6+8+...+2n)
일반항 유도
수열의 n번째 항은 n까지의 짝수들의 합입니다.
an = (2 + 4 + 6 + 8 + … + 2n) = n² + n
전체 합 공식 유도 과정
sum = 2 + (2+4) + (2+4+6) + (2+4+6+8) + ... + (2+4+6+8+...+2n) sum = ∑ (n² + n) sum = ∑ n² + ∑ n sum = [ (n*(n+1)*(2n + 1))/6 ] + [ (n*(n+1))/2 ] sum = ½ (n*(n+1)) [(2n + 1)/3 + 1] sum = ½ (n*(n+1)) [(2n + 1 + 3)/3] sum = ½ (n*(n+1)) [2(n+2)/3] sum = ⅓ * n * (n+1) * (n+2)
최종적으로 수열의 합은 n(n+1)(n+2)/3이라는 간단한 공식으로 표현됩니다.
예제 코드
공식을 적용한 프로그램은 다음과 같습니다.
#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
return ((n)*(n+1)*(n+2)/3);
}
int main() {
int n = 5;
cout<<"Sum of the series 2 + (2+4) + (2+4+6) + ... + (2+4+6+...+"<<(2*n)<<") is "<<calcSeriesSum(n);
return 0;
}출력 결과
Sum of the series 2 + (2+4) + (2+4+6) + ... + (2+4+6+...+10) is 70
결론
중첩 반복문을 사용한 방법은 O(n²)의 시간 복잡도를 가지는 반면, 수학 공식을 활용하면 단 한 번의 곱셈 연산만으로 결과를 얻을 수 있어 시간 복잡도가 O(1)로 크게 개선됩니다. 따라서 실제 개발 환경에서는 공식 기반 접근법을 사용하는 것이 가장 효율적입니다.