(누적 합) 기호?
sum = 0;
for( i = 1 ; i <= 10 ; i++){
sum += i;
}
위의 소스를 sigma(시그마)로 나타내면
(문제) 다음 소스는 시그마로 어떻게 표현할 까요?
sum =0;
for( i = 1 ; i <= 2 ; i++){
for( j = 1 ; j <= 3 ; j++){
sum += i + j;
}
}
시그마 표현 몇가지 예를 들어 보겠습니다.
시그마 표현이 이해가 되시나요?
시그마의 성질 몇가지를 알아보겠습니다.
1.
proof)
두 소스는 같습니다. 아래 소스가 시간 면에서 유리 하겠죠.
sum = 0 ;
for( i = 1 ; i <= n ; i++){
sum += k * a[i];
}
는
sum = 0 ;
for( i = 1 ; i <= n ; i++){
sum += a[i];
}
sum *= k ;
2.
proof)
3.
이 것은 다음 코드로 이해할 수 있습니다.
sum = 0;
for( i = 1 ; i <= 30 ; i++){
sum += 10;
}
10 을 30 번 누적하라는 의미 입니다. 즉
시그마의 성질 이용하기
(예제) 다음식
을 구하여 봅니다.
(sol)
등차수열의 합으로 구할 수 있지만 여기에서는 시그마의 성질을 이용하겠습니다.
누적합 문제를 시그마로 해결하기 위해서는
1.일반항을 구합니다.
2. 시그마의 하한값, 상한값을 적절하게 넣어 준 후
3. 시그마의 성질 세가지를 이용해서 분해한 후
4.
의
누적합 공식을 대입 후 식을 정리하면 됩니다.
이 문제에서는 일반항은 2n - 1 이므로
이는
이고
.....
작업 중....
을 구하여 봅니다.누적합 문제를 시그마로 해결하기 위해서는
