[Algorithm] 1부터 n까지 더하는 알고리즘의 설계

우리가 흔히 '1부터 n까지 더한 값을 출력하는 프로그램을 작성하라' 는 문제를 보면,

대부분이 이렇게 작성할 것이다.

#include <stdio.h>

int main()
{
	int a, sum=0;
	scanf("%d", &a);
	
	for(int i = 1; i <= a; i++)
	{
		sum = sum + i; //물론 sum += i로 쓸 수도 있다.
	}
	
	printf("%d", sum);
}

그리고, 출력값은 위와 같이 표시될 것이다.

만약, 이 출력값을 반복문 없이 구현하라고 하면 어떻게 구현할 것인가? 

재귀부터 시작해서 등차수열의 합 공식 등... 다양한 방법이 있을 것이다.

그 중 우리는 재귀함수를 사용해서 점화식으로 구현해 보도록 하겠다.

<풀이방법 1> 

먼저, 함수 f(n)은 1부터 n까지의 합으로 정의할 수 있다.

f(1) = 1

f(2) = 1 + 2

....

f(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9

f(10) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10

뭔가 공통점이 보이지 않는가? [f(n), n=10] 을 구하고자 할 때 f(9)는 1 ~ n-1의 합을 구하는 것이고, 

f(10)은 1부터 n까지의 합을 구하는 것이다. 따라서 f(10)은 아래와 같이 작성할 수 있다.

f(10) = f(9) + 10

이를 일반화하면

으로 쓸 수 있다.

이를 코드로 작성하면

으로 작성할 수 있는 것이다. n에 1이 들어가면 1~1의 합이니 return 1, 

1이 아니라면 함수 내 재귀를 수행하는 것이다.

<풀이방법 2>

f(10) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10일 때,

f(5) = 1 + 2 + 3 + 4 + 5 이다.

이를 f(10) = f(5) + 6 + 7 + 8 + 9 + 10 로 표현할 수 있으며,

f(10) = f(5) + (5 + 1) + (5 + 2) + (5 + 3) + (5 + 4) + (5 + 5) 로 표현 가능하다.

정리하면, 

f(10) = f(5) + 1 + 2 + 3 + 4 + 5 + 5 + 5 + 5 + 5 + 5

이 식에서 굵게 표시한 부분은 또 f(5)로 치환할 수 있다. 

빨간색으로 표현한 부분은 5*5로 5의 제곱으로 표현 가능하다.

따라서 f(10) = 2f(5) + 5^2 로 표현할 수 있으며, 입력한 n은 10이므로

로 나타낼 수 있다.

그러나, 이 식은 홀수에서는 표현할 수 없는 식이다. 홀수를 나누면 소수점이 남기 때문.

따라서, 일반항에 가우스를 씌우고 (0.5 잃음), 가우스에서 잃었던 0.5 + n/2할때 생기는 0.5를 더해준다.

그럼 아래와 같이 정리할 수 있다. 

이를 홀, 짝 구분없이 쓸 수 있도록 정리하면, 아래와 같이 표현 가능하다.

프로그래밍 언어에서는 정수를 나누면 소수점 이하를 버리므로 아래와 같이 프로그램을 작성할 수 있다.

직접 여러 숫자를 대입해 보면서 풀어보면 잘 이해가 될 것이다.