9-3-다.작업 결과 저장
배열은 중간 작업 결과를 저장하는데도 사용한다. 다음 예제는 1~100까지의 범위에 있는 모든 소수를 찾는 가장 간단한 알고리즘인 에라토스테네스의 체를 배열로 구현한 것이다.
|
예 제 : Eratosthenes |
#include <Turboc.h>
#define RANGE 100
void main()
{
BOOL Prime[RANGE+1];
int i,j;
// 일단 전부 소수로 가정한다.
for (i=0;i<=RANGE;i++) Prime[i]=TRUE;
// 2부터 배수를 찾아 지운다.
for (i=2;i<=RANGE;i++) {
if (Prime[i]) {
for (j=i*2;j<=RANGE;j+=i) {
Prime[j]=FALSE;
}
}
}
// 남은 소수 출력
puts("1~100까지의 소수 목록");
for (i=2;i<=RANGE;i++) {
if (Prime[i]) {
printf("%d ",i);
}
}
}
실행 결과는 다음과 같다.
1~100까지의 소수 목록
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73
79 83 89 97
소수(Prime Number)는 1과 그 자신만을 약수로 가지는 수이다. 따라서 2이상의 수로 나누어 떨어지면 그 수는 소수가 아니다. BOOL타입의 Prime 배열을 크기 RANGE+1로 선언하여 RANGE까지의 수에 대응시키는데 0과 1은 대상에서 제외된다. RANGE 매크로 상수는 100으로 정의했는데 이 값을 더 크게 바꾸면 더 넓은 범위에서 소수를 찾을 수도 있다. Prime 배열의 모든 요소를 일단 TRUE로 초기화하여 모든 수를 소수라고 가정한다.
그리고 i를 2부터 100까지 루프를 돌면서 Prime 배열에서 i의 배수를 찾아 지운다. 즉 소수가 아닌 수를 걸러내는 것이다. 배수를 찾아 지우는 j루프는 i의 두 배 되는 수부터 시작하는데 i자체는 자기 자신으로만 나누어진다고 볼 수 있으므로 일단은 소수로 봐야 한다. j는 i*2부터 시작해서 i씩 증가하면서 100까지 Prime[j]를 FALSE로 바꾼다. i가 2일 때 4, 6, 8, 10 등은 소수 후보에서 제외될 것이며 다음 루프에서 i가 3일 때 6, 9, 12, 15 등도 차례대로 제외된다.
단, 이미 i 자신이 소수가 아닌 것으로 판명이 났을 때는 더 이상 지울 후보가 없으므로 j 루프를 돌 필요가 없다. i가 자기보다 작은 수로 나누어 떨어졌다면 i의 배수도 모두 마찬가지이기 때문이다. 가령 i가 4일 때 이 숫자는 이미 앞에서 2의 배수로 판명나서 지워진 상태이므로 4의 배수인 8, 12, 16 등도 모두 지워졌을 것이다. 그래서 j 루프에 들어가기 전에 Prime[i]가 TRUE 인지를 먼저 점검한다.
이런 식으로 소수 후보를 하나씩 지워 나가면 결국 Prime 배열에는 소수인 수만 남게 될 것이다. 다시 2부터 루프를 돌면서 Prime[i]가 TRUE인 첨자만 출력하면 된다. 이처럼 중간 작업 결과를 저장할 때도 배열을 사용한다. 컴퓨터는 방금 한 연산도 별도로 저장하지 않으면 금방 잊어 버리기 때문에 배열에 기록을 계속 유지해야 한다.
AlphaNum
영문 소문자로 구성된 긴 문장을 입력받아 이 문자열 내의 각 알파벳 문자 개수를 구해 출력하라. 예를 들어 alpha가 입력되었다면 a:2, b:0, .... h:1, ... l:1, .... p:1이 출력되어야 한다. 각 문자의 출현 회수를 저장할 배열이 필요하다.