[알고리즘/C언어] 수열의 합 알고리즘 (정보처리기사, 실기)

정보처리기사 실기 시험에서 다뤄질만한 기초적인 알고리즘을 이 카테고리에서 쭉 정리해보려고 한다.

 

1. 동일한 숫자 N번 더하기

Sum = 7 + 7 + 7 + ... + NUM (NUM-10항까지의 합)

#include <stdio.h>
#define NUM 10	// 기호형 상수 : 상수 -> 반드시 대문자로 표현한다.
int main() {
	int sum = 0, cnt;
	for (cnt = 1; cnt <= NUM; cnt++) {   // cnt = 1,NUM,1 (알고리즘)
		sum = sum + 7;
		printf("cnt=%d, sum=%d\n", cnt, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%d,  sum=%d\n", cnt, sum);	// 11, 70

	system("pause");
	return 0;
}

가장 이해하기 쉬운 베이직한 방법이다.

먼저 10항까지의 합이므로 기호형 상수 NUM을 10이라고 정의하였다.

NUM은 변수와는 다르게 바뀌지 않는 값으로 

함수에서 계속해서 반복적으로 사용되는 변하지 않는 값들을 정의할 때 쓴다.

 

cnt변수의 초기값은 1이고 10을 포함하여 반복하므로 10번 반복하게 된다.

반복문 종료 후 cnt= 11, sum= 70이 된다.

 

#include <stdio.h>
#define NUM 10
int main() {
	int sum = 0, cnt;
	for (cnt = NUM; cnt >= 1; cnt--) {	 // cnt = NUM, 1, -1
		sum = sum + 7;
		printf("cnt=%d, sum=%d\n", cnt, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%d,  sum=%d\n", cnt, sum);

	system("pause");
	return 0;
}

cnt의 초기값을 10으로 주고 1보다 크거나 같을 때가지 증감시키며 반복하는 방법도 있다.

이 경우 실행결과는 아래와 같다.

 

실행결과

#include <stdio.h>
#define NUM 10
int main() {
	int sum = 0, cnt;
	for (cnt = 1; cnt < NUM+1; cnt++) {	 // cnt = 1, NUM+1, 1
		sum = sum + 7;
		printf("cnt=%d, sum=%d\n", cnt, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%d,  sum=%d\n", cnt, sum);

	system("pause");
	return 0;
}

첫번째 코드와 거의 같으나 <= 대신 <을 사용했으므로, NUM에 +1을 해준다.

 

#include <stdio.h>
#define NUM 10
int main() {
	int sum = 0, cnt;
	for (cnt = 1; cnt != NUM + 1; cnt++) {
		sum = sum + 7;
		printf("cnt=%d, sum=%d\n", cnt, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%d,  sum=%d\n", cnt, sum);

	system("pause");
	return 0;
}

거의 사용하지 않는 방법이지만 위와 같이 표현할 수도 있다.

결과값은 동일하다.

 

 

2. 1씩 증가하는 수열의 합

Sum = 1 + 2 + 3 + 4 + ... + NUM (NUM-10항까지의 합)

sum = 1 + 2 + 3 + 4 + ... + NUM의 규칙은

   i        1     1    1

숫자가 1씩 증가하고 있다는 점이다.

#include <stdio.h>
#define NUM 10
int main() {
	int  cnt, sum = 0, i=0;
	for (cnt = 1; cnt <= NUM; cnt++) {
		i = i + 1;
		sum = sum + i;
		printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);	// i = 10

	system("pause");
	return 0;
}

위 코드의 특징은 i에 1을 더하여 sum에 i를 더해나가는데,

i = i + 1; 연산을 sum = sum + i; 연산 전에 실행한다는 점이다.

 

그러므로 반복문을 다 빠져나가고 난 후에도 i는 11이 아니고 10이 된다.

 

실행결과

 

#include <stdio.h>
#define NUM 10
int main() {
	int  cnt, sum = 0, i = 1;
	for (cnt = 1; cnt <= NUM; cnt++) {
		sum = sum + i;
		printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);
		i = i + 1;
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);	// i = 11

	system("pause");
	return 0;
}

위와 동일한 코드에서 i의 초기값을 1로 바꾸고

i의 증감을 sum 연산 뒤에 이루어지게 한다면

반복문 종료 후 아래 사진과 같이 i는 11이 된다.

 

위 코드는 i대신 cnt를 sum에 더하는 것과 결과가 동일하다.

실행결과

 

 

3. 1부터 N까지 홀수의 합

Sum=1+3+5+7+...+NUM (NUM-10항까지의 합)

sum = 1 + 3 + 5 + 7 + ... + NUM의 규칙은

   i        2     2    2

숫자가 2씩 증가하고 있다는 점이다.

#include <stdio.h>
#define NUM 10
int main() {
	int  cnt, sum = 0, i = -1;
	for (cnt = 1; cnt <= NUM; cnt++) {
		i = i + 2;
		sum = sum + i;
		printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);	// i = 19

	system("pause");
	return 0;
}

i는 2만큼 증가해야 하므로 i = i + 2;를 해준다.

여기서 sum에 처음으로 더해야하는 수가 1이므로 i의 초기값이 -1이 되어야 1을 더할 수 있다.

 

실행결과

 

#include <stdio.h>
#define NUM 10
int main() {
	int  cnt, sum = 0, i = 1;
	for (cnt = 1; cnt <= NUM; cnt++) {
		sum = sum + i;
		printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);
		i = i + 2;
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);	// i = 21

	system("pause");
	return 0;
}

만약에 i 연산을 sum연산 뒤에 실행한다면 i의 초기값은 1이 될 것이다.

 

 

[문제] 만약에 아래와 같은 상황에서 빈 칸에 들어갈 코드는 어떻게 될까?

#include <stdio.h>
#define NUM 10
int main() {
	int  cnt, sum = 1, i = [   ];
	for (cnt = 1; cnt [   ] NUM; cnt++) {
		i = [        ];
		sum = sum + i;
		printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);	// i = 10

	system("pause");
	return 0;
}

1) 일단 i는 2씩 증가하므로 i = i + 2;를 채워넣는다.

 

2) 그 다음, sum의 초기값이 0이 아니고 1이므로 sum에 3부터 더해야한다는 결론을 내릴 수 있다.

그러므로 i의 초기값은 1이 되어야한다. (i = 1 + 2 = 3을 만들어야하기 때문이다.)

 

3) cnt의 초기값은 1이고 원래대로라면 10번을 더해야하는데,

sum이 이미 1을 가지고 있었으므로 3부터 9번을 실행해야 한다. 

1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19

그러므로 cnt < 10이 되어야 한다.

 

[정답]

#include <stdio.h>
#define NUM 10
int main() {
	int  cnt, sum = 1, i = 1;
	for (cnt = 1; cnt < NUM; cnt++) {
		i = i + 2;
		sum = sum + i;
		printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);
	}
	printf("----------반복문 종료-------------\n");
	printf("cnt=%2d, i=%2d, sum=%5d\n", cnt, i, sum);	// i = 10

	system("pause");
	return 0;
}