[자료구조 3장] - 배열과 구조체(2)

배열과 구조체(2)

 

배열 응용 프로그램

배열의 차원 : 배열의 각 항목에 접근하기 위해 필요한 인덱스의 수

자료의 형태가 그려지지 않으면 프로그래밍에서 다루기 쉽지 않기 때문에 1, 2차원 배열이 주로 활용된다.

 

실습 프로그램

- 1차원 배열에 n개 데이터 읽어들여 평균을 구하고 평균보다 더 큰 값의 데이터 수를 구하는 프로그램

 

- 영어학원에 4개의 시간에 3분의 강사가 수업을 개설했을 때, 각 시간의 각 선생님께 수강 신청한 학생의 수를 2차원 배열에 입력받아 저장하고 각 선생님 클래스의 학생수를 출력해주는 프로그램

 

- 전화번호부 정보를 가지는 문자열의 2차원 배열, 즉 문자형의 3차원 배열에 이름과 전화번호 데이터를 준비하고 있다고 하자. 이때 전화번호부에 저장 되어 있는 이름을 순서대로 번호를 붙여 출력해 주고 그 번호를 통해 전화번호를 검색해 주는 프로그램

 

---

마방진(magic square) 프로그램

2차원 배열을 이용한 예제

n * n 정사각행렬은 1에서 n제곱 까지의 정수로 채워진 행렬로서 각 행과 열 그리고 두 개의 주 대각선의 합이 모두 같다.

 

n이 홀수일 때 마방진을 만들기 위한 정방행렬을 만드는 규칙

1. 첫 번째 행의 중앙에 1을 넣는다.

2. 왼쪽 대각선 방향으로 올라가면서 빈자리에 1씩 큰 수를 놓는다. 이때 행렬의 밖으로 벗어나면 그 방향의 반대편에서 계속하라. 즉 상단을 벗어나면 같은 열의 최하단으로, 왼쪽으로 벗어나면 같은 행의 제일 오른쪽으로 이동한다.

3. 만약 이동하려는 자리에 숫자가 이미 채워져 있으면 바로 밑으로 내려가서 계속한다.

 

이 규칙을 이용하여 만든 n = 5인 경우 마방진(5 * 5 마방진)

15	8	1	24	17
16	14	7	5	23
22	20	13	6	4
3	21	19	12	10
9	2	25	18	11

 

각 행과 열 그리고 대각선을 더한 값은 65로 동일하다.

 

마방진 프로그램을 만들어보자.

#define MAX_SIZE 15

void main()
{
    int n, r, c, sum = 0, digit, row, col;
    int table[MAX_SIZE][MAX_SIZE];
    
    printf("Enter a number: ");
    scanf("%d", &n);
    
    if( (n < 1) || n > MAX_SIZE) {
    	printf("Error! size is out of range.\n");
        exit(0);
    }
    if(!(n%2)) {
    	printf("Error! size is even.\n");
        exit(0);
    }
    
    for(r = 0; r < n; r++)
    	for(c= 0; c < n; c++)
        	table[r][c] = 0;
            
    r = 0; c = (n-1)/2;
    table[r][c] = 1;
    
    for(digit = 2; digit < n*n; digit++) {
    	row = r - 1;
        col = c - 1;
        if (row < 0) row = n - 1; //up
        if (col < 0) col = n - 1; //left
        if(table[row][col]) r++;
        else {
        	r = row;
            c = col;
        }
        table[r][c] = digit;
    }
    for (r= 0; r < n; r++) {
    	for(c = 0; c < n; c++)
        	printf("%5d", table[r][c]);
        printf("\n");
    }
    for(c = 0; c < n; c++)
    	sum += table[0][c];
        
    printf("Row/Column/Diagonal Sum = %d\n", sum);
    
} /* main */
}

 

n으로 7을 넣으면 결과는 다음과 같다.

28	19	10	1	48	39	30
29	27	18	9	7	47	38
37	35	26	17	8	6	46
45	36	34	25	16	14	5
4	44	42	33	24	15	13
12	3	43	41	32	23	21
20	11	2	39	40	31	22

Row/Column/Diagonal Sum = 175