9-3. 배열의 활용
1.불규칙한 정보의 저장
2.재사용할 정보 저장
3.작업 결과 저장
4.룩업 테이블
5. 미리 계산된 값
9-3-가.불규칙한 정보
배열의 기본적인 용도는 동일한 타입의 집합적인 정보를 다루는 것인데 아주 간단한 구조이지만 활용 용도는 헤아릴 수 없을 정도로 많다. 이 절에서는 배열로 할 수 있는 전형적인 몇 가지 기법에 대해 요약적으로 알아보기로 한다. 다음 예제는 2차원 배열을 사용하여 문자 'C'로 큼직하게 C문자를 써 본다.
예 제 : ArrayC |
#include <Turboc.h>
void main()
{
int i;
int arPos[40][2]={
{48,6},{47,5},{46,4},{45,4},{44,3},{43,3},{42,3},
{41,3},{40,3},{40,3},{39,4},{38,4},{37,5},{36,6},
{36,7},{35,8},{35,9},{35,10},{34,11},{34,12},
{34,13},{34,14},{35,15},{35,16},{35,17},{36,18},
{37,19},{38,20},{39,20},{40,21},{41,21},{42,21},
{42,21},{43,21},{44,20},{45,20},{46,20},{47,19},
{48,18},{49,17}
};
clrscr();
for (i=0;i<sizeof(arPos)/sizeof(arPos[0]);i++) {
gotoxy(arPos[i][0],arPos[i][1]);
putch('C');
}
}
arPos 배열에 C문자를 구성하는 40개의 점좌표가 저장되어 있다. 각 좌표는 (x,y)로 구성되어 있고 40개의 좌표에 규칙성이 전혀 없기 때문에 이런 식으로 초기값을 일일이 지정해야 한다. arPos 배열에 좌표값이 저장되어 있으므로 0~39까지 루프를 돌면서 (arPos[i][0], arPos[i][1]) 좌표에 'C'를 출력했다. 실행 결과는 다음과 같다.
CCCCC
CC CC
C C
C C
C
C
C
C
C
C
C
C
C
C
C C
C C
C C
CC CCC
CCCC
그렇다면 arPos의 초기값은 어떻게 구했는지 궁금할 것이다. 이 좌표들은 모눈종이에 C자를 크게 그려 놓고 각 좌표를 일일이 조사한 것이며 특별한 테크닉이 있는 것은 아니다. 쉽게 말해서 체력과 시간만 있다면 이런 예제는 얼마든지 만들 수 있다.
9-3-나.재사용할 정보
다음 예제는 2차원 배열의 활용예인데 난수로 생성한 좌표를 배열에 저장해 놓고 역순으로 이 좌표를 재생한다. 실행해 보면 깨끗한 화면에 *가 100개 출력되고 출력된 순서대로 다시 사라질 것이다.
예 제 : RandArray |
#include <Turboc.h>
void main()
{
short arPt[100][2];
int i;
clrscr();
for (i=0;i<100;i++) {
arPt[i][0]=random(80);
arPt[i][1]=random(25);
gotoxy(arPt[i][0],arPt[i][1]);
putch('*');
delay(20);
}
delay(2000);
for (i=0;i<100;i++) {
gotoxy(arPt[i][0],arPt[i][1]);
putch(' ');
delay(20);
}
}
난수로 선택한 임의 위치에 *를 100번 출력하는 것은 아주 쉽다. 루프를 100번 돌면서 gotoxy(random(80), random(25)); putch('*')만 100번 실행하면 된다. 이렇게 출력한 *를 순서대로 다시 지우려면 각 점들이 출력된 좌표를 일일이 기억하고 있어야 한다. 그렇지 않으면 원래 어디에 출력되어 있었는지 알 수가 없을 것이다. 컴퓨터는 별도로 기억시키지 않으면 다 잊어 버리므로 다시 사용할 정보는 항상 저장해 놓아야 한다.
이 예제에서 사용된 arPt 배열은 처음에 100개의 *를 출력할 때 난수로 선택한 좌표를 잠시 저장해 두기 위한 용도로 사용된다. 총 점의 개수가 100개이므로 1차 첨자의 크기가 100이고 각 점은 x,y 좌표쌍으로 구성되므로 2차 첨자의 크기는 2이다. arPt[n][0]는 n번째 점의 x좌표를, arPt[n][1]은 n번째 점의 y좌표를 저장한다.
난수로 *를 100번 출력하되 그 좌표를 배열에 저장해 두었다가 지울 때는 다시 이 배열의 선두부터 루프를 돌면서 원래 출력했던 자리에 공백을 출력하면 된다. 저장해야 할 좌표가 100개나 되고 각 좌표는 (x,y)의 쌍으로 구성되어 있지만 arPt 배열 단 하나만 있으면 이 정보들을 통째로 저장할 수 있다. 개별 변수 100개에 이 정보를 따로 저장하는 것은 불가능하다.
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이 출력되어야 한다. 각 문자의 출현 회수를 저장할 배열이 필요하다.
9-3-라.룩업 테이블
임의의 날짜가 주어졌을 때 이 날짜 다음의 날짜, 즉 내일을 구하는 예제를 만들어 보자. 내일이란 굉장히 쉽게 구할 수 있을 것 같지만 날짜라는 정보의 구조가 간단하지 않기 때문에 생각보다 훨씬 더 어렵다. 오늘 날짜가 m월 d일이라고 했을 때 대부분의 경우는 d만 1증가시키면 된다. 그러나 오늘이 월말일 경우는 d는 1이 되고 m은 1증가해야 하는데 예를 들어 3월 31일의 내일은 3월 32일이 아니라 4월 1일이다.
월이 바뀔 때도 m이 무조건 1증가되기만 하는 것은 아니다. 13월이라는 것은 없으므로 12월 다음은 1월이 되어야 한다. 오늘이 월말이라는 것을 알아 내려면 매 달마다 몇일까지 있는지를 조사해야 한다. 3월은 31일까지 있지만 4월은 30일까지밖에 없다. 이런 정보를 조사할 때도 배열을 사용할 수 있다. 다음 예제는 배열로 이 문제를 풀어본 것이다.
예 제 : PrintTomorrow |
#include <Turboc.h>
void PrintTomorrow(int m, int d)
{
static int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
if (d > days[m] || m < 1 || m > 12) {
printf("입력한 날짜가 틀렸습니다.\n");
} else {
d++;
if (d > days[m]) {
d=1;
m++;
if (m == 13) {
m=1;
}
}
printf("내일은 %d월 %d일입니다.\n",m,d);
}
}
void main()
{
int mon,day;
printf("오늘 날짜(월 일)을 공백으로 구분하여 입력해 주세요 : ");
scanf("%d%d",&mon,&day);
PrintTomorrow(mon,day);
}
PrintTomorrow 함수는 날짜를 전달하면 이 날짜의 내일을 조사하여 출력한다. 매월의 마지막 날에 대한 정보를 days라는 배열로 작성해 놓고 days의 첨자로 m을 사용하면 m월의 날 수를 쉽게 조사할 수 있다. 이런 식으로 값의 참조를 위해 사용하는 배열을 룩업 테이블(Lookup Table)이라고 한다. 만약 배열을 사용하지 않는다면 switch case문이나 여러 개의 조건문을 가지는 if문을 구성해야 할 것이다.
if (m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12) {
// 31일까지 있음
} else if (m==4 || m==6 || m==9 || m==11 {
// 30일까지 있음
} else {
// 28일까지 있음
}
조사 대상이 12개 정도이고 비슷한 값들을 가진다면 이 정도 조건문으로도 문제를 일단 해결할 수 있겠지만 만약 100개 정도의 불규칙한 값을 조사해야 한다면 이런 방법은 한계가 있다. 아무리 값이 많아도 또 값이 불규칙해도 룩업 테이블을 작성하면 아주 빠른 속도로 원하는 값을 찾을 수 있을 뿐만 아니라 이후 값을 수정하기도 편리하다. 값을 선택하는 기준이 정수라면 이 정수값을 첨자로 하는 룩업 테이블을 작성하고 정수를 첨자로 넣기만 하면 배열을 통해 원하는 값을 바로 찾을 수 있다.
룩업 테이블은 보통 한 함수만 사용하는데다 읽기 전용인 경우가 많으므로 static으로 선언하는 것이 좋다. 만약 static으로 선언하지 않고 단순 지역 배열로 선언한다면 함수가 호출될 때마다 이 배열을 매번 초기화해야 하는데 이는 엄청난 실행 속도의 저하를 가져온다. 배열의 크기가 크면 클수록 초기화 속도는 느려지는데 이럴 때 static 기억 부류를 사용하면 딱 한 번만 초기화하므로 속도에 유리하다.
다음 예제는 룩업 테이블의 또 다른 사용예인데 전혀 규칙성이 없는 난수중 하나를 선택한다. 발생 가능한 난수 목록을 배열에 미리 작성해 놓고 난수로 배열 첨자를 고르는 방식이다. 실행할 때마다 룩업 테이블에 있는 정수중 하나가 선택되어 출력될 것이다.
예 제 : RandTable |
#include <Turboc.h>
void main()
{
int arRand[]={2,9,14,19,27};
int Num;
randomize();
Num=arRand[random(sizeof(arRand)/sizeof(arRand[0]))];
printf("생성한 난수 = %d\n",Num);
}
이런 방법을 쓰는 대신 원하는 난수를 포괄하는 범위에서 수를 하나 생성하고 조건문으로 원하는 난수 중 하나가 맞는지 점검하는 방법을 쓸 수도 있다. while문으로 조건에 맞는 난수가 나올 때까지 루프를 돌리면 언젠가는 원하는 값이 나오기는 하겠지만 루프를 여러 번 돌아야 하므로 비효율적이고 난수를 고르는 시간이 일정하지 않다. 룩업 테이블은 첨자만 난수로 선택하므로 단 한 번에 원하는 값을 고를 수 있고 난수의 목록을 편집하기도 편리하다.
다음 예제의 Congratulation 함수는 게임의 시도 회수에 따라 축하 메시지를 출력하는데 시도 회수가 적을수록 높은 점수를 부여한다. 회수별로 메시지를 다르게 출력하기 위해 switch case문을 사용했다.
예 제 : GameMessage1 |
#include <Turboc.h>
void Congratulation(int count)
{
switch (count) {
case 1:
puts("축하합니다. 최고 성적입니다.");
break;
case 2:
puts("대단한 성적입니다.");
break;
case 3:
puts("참 잘 하셨습니다");
break;
case 4:
puts("보통이 아니군요.");
break;
case 5:
puts("보통입니다.");
break;
case 6:
puts("조금 더 노력하셔야겠습니다.");
break;
case 7:
puts("정말 못하시는군요.");
break;
case 8:
puts("수준 이하입니다.");
break;
default:
puts("다음부터 절대로 이 게임을 하지 마세요.");
break;
}
}
void main()
{
Congratulation(3);
}
이 예제는 기능상의 문제는 전혀 없지만 길다란 switch case문이 왠지 비효율적으로 보인다. 시도 회수인 count로부터 메시지만을 구하는 룩업 테이블을 작성하면 출력문을 훨씬 간단하게 구성할 수 있으며 또한 메시지를 편집하거나 추가하기도 편리하다. 다음 예제는 똑같은 동작을 하되 룩업 테이블로 바꿔 본 것이다.
예 제 : GameMessage2 |
#include <Turboc.h>
void Congratulation(int count)
{
static char *Message[]={"",
"축하합니다. 최고 성적입니다.",
"대단한 성적입니다.",
"참 잘 하셨습니다",
"보통이 아니군요.",
"보통입니다.",
"조금 더 노력하셔야겠습니다.",
"정말 못하시는군요.",
"수준 이하입니다.",
"다음부터 절대로 이 게임을 하지 마세요.",
};
if (count >= 9) count=9;
puts(Message[count]);
}
void main()
{
Congratulation(3);
}
count를 첨자로 하는 문자열의 배열을 작성했는데 이 룩업 테이블도 물론 static으로 선언해야 한다. count가 0인 경우는 없으므로 빈 문자열로 초기화해 미사용으로 남겨 두었다. 메시지 문자열들이 한 곳에 모여 있으므로 소스가 훨씬 더 짧아지고 보기에도 좋다. 만약 count와 메시지가 일대일로 대응되지 않고 일정 범위별로 대응된다면 같은 메시지를 배열에 계속 나열할 필요없이 2차 룩업 테이블을 만든다. 예를 들어 1~3회는 상, 4~8까지는 중, 9~12까지는 하로 범위를 나누어 메시지를 다르게 출력하고 싶다면 다음과 같이 수정한다.
예 제 : GameMessage3 |
#include <Turboc.h>
void Congratulation(int count)
{
static char *Message[]={
"잘 하셨습니다.",
"보통입니다.",
"못 하는군요.",
};
static int arMes[]={0,0,0,0,1,1,1,1,1,2,2,2,2};
if (count >= 12) count=12;
puts(Message[arMes[count]]);
}
void main()
{
Congratulation(8);
}
count를 arMes 룩업 테이블에 넣어 몇 번째 메시지인가를 먼저 선택하고 이 값을 Message 배열의 첨자로 넣어 실제 메시지를 고르는 것이다. count로부터 최종 메시지가 선택되는 과정은 다음과 같다.
이렇게 하면 메시지를 출력하는데 필요한 최소한의 정보만 유지할 수 있으며 편집하기도 쉽다. count에 따른 메시지를 변경하려면 arMes배열을 편집하고 최종 메시지 문자열을 변경하려면 Message 배열을 편집하기만 하면 된다.
PrintTomorrow2
PrintTomorrow 예제는 년도에 대한 고려는 하지 않는데 년도까지 계산에 포함하면 윤년을 고려해야 한다. 윤년이란 4로 나누어 떨어지되 100으로는 나누어 떨어지지 않는 년도인데 1904년은 윤년이지만 1900년은 윤년이 아니다. 또한 100으로 나누어 떨어지는 년도라도 400으로 나누어 떨어지면 윤년이 되는데 2000년은 윤년이다. 윤년에는 2월달이 29일까지 있으므로 룩업 테이블에서 읽은 값 중 2월의 값을 수정한 후 사용해야 한다. 년, 월, 일 정보를 모두 입력받아 윤년까지 고려해서 내일 날짜를 출력하는 예제를 작성하라.
9-3-마.미리 계산된 값
다음 예제는 지구가 태양을 공전하는 동작을 시뮬레이션하는데 그래픽 환경이 아니기 때문에 다소 썰렁해 보이기는 하지만 좌표 계산은 제대로 하고 있다. 실행해 보면 태양을 상징하는 S 주위를 지구 E가 끊임없이 원 운동을 하는데 그래픽 환경이라면 실감나는 동영상을 감상해 볼 수 있을 것이다.
예 제 : Revolution1 |
#include <Turboc.h>
#include <math.h>
void main()
{
double angle;
int x=-1,y=-1;
clrscr();
gotoxy(40,12);
putch('S');
for (angle=0;;angle+=10) {
if (angle==360) angle=10;
if (kbhit()) break;
gotoxy(40+x,12+y);putch(' ');
x=int(cos(angle*3.1416/180)*20);
y=int(sin(angle*3.1416/180)*10);
gotoxy(40+x,12+y);putch('E');
delay(100);
}
}
이 프로그램을 작성하려면 매 각도마다 원주상의 좌표를 계산해야 하는데 이때는 삼각 함수가 필요하다. 반지름 r인 원에서 임의의 각도 θ인 원주상의 x, y를 계산하는 공식은 다음과 같다.
이 공식대로 지구의 x, y 좌표를 구하되 sin, cos 함수가 각도가 아닌 라디안을 요구하므로 각도를 라디안으로 변환했으며 콘솔 환경의 좌표가 세로쪽이 길기 때문에 가로 반지름을 세로보다 두 배로 주어 정원이 되도록 했다. 아뭏든 이 공식대로 angle에 대한 좌표를 구하고 angle을 0~350까지 반복적으로 루프를 돌리면 지구를 공전시킬 수 있다.
문제는 이 좌표를 계산하는데 시간이 너무 오래 걸린다는 점이다. 삼각 함수는 실수 차원에서 계산을 하므로 무척 느린데다 라디안을 각도로 변환하는 수식과 실수를 다시 정수로 바꾸는 캐스트 연산까지 꽤 많은 것들을 계산해야 좌표값 하나를 얻을 수 있다. 그나마 지구가 정원 운동을 하기 때문에 공식 하나로 좌표를 구할 수 있지만 만약 아주 복잡한 곡선 운동을 한다면 수식이 더욱 복잡해질 것이다.
이런 복잡한 값을 실행중에 일일이 구해서 사용하면 프로그램의 속도는 그만큼 느려지게 된다. 이럴 때는 필요한 모든 값을 미리 구해 배열에 넣어 두고 배열의 값을 참조하는 방법을 사용할 수 있다. 다음이 배열로 수정해 본 예제인데 결과는 완전히 동일하다.
예 제 : Revolution2 |
#include <Turboc.h>
#include <math.h>
void main()
{
double angle;
int x=-1,y=-1;
static int arx[]={20,19,18,17,15,12,9,6,3,0,-3,-6,
-10,-12,-15,-17,-18,-19,-19,-19,-18,-17,-15,-12,
-9,-6,-3,0,3,6,10,12,15,17,18,19};
static int ary[]={0,1,3,5,6,7,8,9,9,9,9,9,
8,7,6,4,3,1,0,-1,-3,-5,-6,-7,
-8,-9,-9,-9,-9,-9,-8,-7,-6,-4,-3,-1};
clrscr();
gotoxy(40,12);
putch('S');
for (angle=0;;angle+=10) {
if (angle==360) angle=10;
if (kbhit()) break;
gotoxy(40+x,12+y);putch(' ');
x=arx[(int)angle/10];
y=ary[(int)angle/10];
gotoxy(40+x,12+y);putch('E');
delay(100);
}
}
arx, ary배열에 각도에 해당하는 좌표값을 미리 구해 적어 놓았다. 이 배열의 실제값은 앞 예제가 구하는 x, y를 printf로 출력하면 쉽게 구할 수 있다. 배열에 값을 미리 다 계산해 놓았으므로 실제 이 값이 필요할 때는 몇 번째 값이 필요하다는 요청만 하면 된다. 배열에 있는 값을 읽는 것은 직접 수식을 계산하는 것보다 훨씬 더 빠르므로 프로그램의 전체적인 속도는 비약적으로 향상된다.
배열을 통한 이런 최적화 기법은 아주 기초적인 성능향상 방법중 하나인데 프로그램의 크기가 커지는 대신 속도를 얻는 작전이다. 즉 배열에 미리 계산된 값은 속도에 유리하고 크기에 불리한 방법인데 요즘의 컴퓨터 환경은 메모리가 넉넉하기 때문에 얼마든지 이런 방법을 사용해도 별 무리가 없다. 이런 최적화 기법을 사용하는 실제 예는 스타크래프트라는 게임에서도 볼 수 있다.
캐리어에서 발사되는 요격기인 인터셉터는 굉장히 복잡한 곡선 운동을 하는데 인터셉터의 이동 경로를 실시간으로 계산하는데는 다소 복잡한 수식이 동원될 것이다. 게다가 이런 인터셉터가 한꺼번에 수십개씩 나올 수 있기 때문에 각 인터셉터의 좌표를 일일이 계산해서 사용한다는 것은 무리다. 이럴 때 인터셉터와 캐리어의 상대적인 좌표를 미리 배열에 작성해 놓고 하나씩 꺼내 쓰는 방법을 사용하면 속도상의 많은 이득을 볼 수 있다.
출저:www.winapi.co.kr
배열의 활용 5가지
1.불규칙한 정보의 저장
2.재사용할 정보 저장
3.작업 결과 저장
4.룩업 테이블
5. 미리 계산된 값
알고는 있었지만 이렇게 정리하니 머리에 쏙쏙
역시 혼연 최고!!!!
