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이 출력되어야 한다. 각 문자의 출현 회수를 저장할 배열이 필요하다.