[C프로그래밍 새내기를 위한 첫 C 언어 책] Chapter7(배열) 정리 및 연습문제

 

내용 정리

 

배열에 대한 간단한 내용은 빠르게 스킵하고

 

1차원, 2차원, 3차원 배열의 구조를 정리한후, 버블정렬에 대해 정리하려 한다.

 

 

배열은 배열명만으로 모든 배열 원소를 한번에 입출력하거나 저장할 수 없으며,

배열 원소 단위로 입출력하거나 저장해야 한다.

 

→ 표준 입력 함수에서는 입력된 자료를 저장할 기억장소의 주소를 명시해야 하므로 배열 원소 앞에 '&'붙인다.

ex) scanf("%d",&quiz[0]);

 

 

※ 1차원 배열

 

예제로 간단한 1차원 배열 문제를 확인하고 넘어가려 한다.

//프로그램 7-3 설문조사 결과 구하기
 
#include <stdio.h>
#define PERSONS 30
#define STARS 6
 
int main()
{ 
    int i;
 
    //배열 초기화
    int survey[PERSONS] = { 1, 3, 2, 5, 3, 2, 1, 2, 3, 4, 5, 2, 
        3, 3, 2, 1, 4, 5, 2, 3, 5, 1, 3, 4, 2, 3, 1, 4, 2, 3 };
 
    int vote[STARS] = { 0 }; //각 연예인의 투표수 0으로 초기화
 
    for (i = 0; i < PERSONS; i++)
    {
        vote[survey[i]]++;  //선택 된 연예인 득표수 증가
    }
 
    printf("연예인 득표수\n");
    printf("================\n");
    for (i = 1; i < STARS; i++)
    {
        printf(" %d번   %d표\n", i, vote[i]);
    }
 
    return 0;
}

 

위의 예제 실행결과

 

 

※ 2차원 배열

 

2차원 배열 (출처: 네이버 지식백과)

 

 

2차원 배열은 1차원 배열이 여러 개 모인 배열로

표 형태의 구조로 표현한다.

학창시절 배웠던 행렬이라고 생각하면 편리한거같다.

 

바로 예제를 통해 프로그래밍 하는 방법을 확인 해보자

 

//프로그램 7-7 2*3행렬 A와 B의 덧셈 결과인 행렬 C구하기
 
#include <stdio.h>
#define N 2 //행 수
#define M 3 //열 수
 
int main()
{
    int A[N][M], B[N][M], C[N][M];
    int i, j;
 
    printf("행렬A 입력\n");
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            printf("%d행 %d열:",i+1,j+1);
            scanf("%d", &A[i][j]);
        }
    }
 
    printf("\n행렬B 입력\n");
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            printf("%d행 %d열:", i + 1, j + 1);
            scanf("%d", &B[i][j]);
        }
    }
 
    printf("\n행렬A \n");
    for (i = 0; i < N; i++)
    {
        printf("[");
        for (j = 0; j < M; j++)
        {
            printf("%3d",A[i][j]);
        }
        printf("]\n");
    }
 
    printf("\n행렬B \n");
    for (i = 0; i < N; i++)
    {
        printf("[");
        for (j = 0; j < M; j++)
        {
            printf("%3d", B[i][j]);
        }
        printf("]\n");
    }
 
    printf("\n행렬C(A+B)\n");
    for (i = 0; i < N; i++)
    {
        printf("[");
        for (j = 0; j < M; j++)
        {
            C[i][j] = A[i][j] + B[i][j];
            printf("%3d", C[i][j]);
        }
        printf("]\n");
    }
    return 0;
}

 

 

1차원 배열과 별반 다를게 없다. 배열 선언, 출력, 입력시에 차원 수만 다르다.

 

 

 

 

※ 3차원 배열

 

2차원에서 한 차원이 더 늘어났으므로, 3차원 입체 공간이다.

표가 여러 면이 겹쳐저 있다고 생각하면 된다.

 

3차원 배열의 논리적 구조(출처: https://kr.mathworks.com/help/matlab/math/multidimensional-arrays.html)

 

A[면][행][열] 이런 식이다.

 

 

 

※ char형 배열을 이용한 문자열 처리

 

문자열이 "Seoul"이면 배열의 원소 자리는 6자리 필요

끝에 널(\0)문자 포함!

 

배열명은 포인터! 이 부분은 포인터 챕터에서 포스팅.

따라서 입력받을 때는 &가 필요없다.

 

 

 

※ 버블정렬

 

배열에서 이웃하는 두 원소씩 차례대로 정렬하는 작업을

반복하여 배열 전체를 정렬하는 방법.

 

버블 정렬 (출처:  http://blog.naver.com/PostView.nhn?blogId=justant&logNo=20204028286&parentCategoryNo=&categoryNo=33&viewDate=&isShowPopularPosts=false&from=postView)

 

그림을 보면 버블정렬의 정의가 쉽게 이해 된다.

 

 

{5,4,3,2,1}의 배열을 정렬해 보자

 

//버블정렬
//1. 단순 버블 정렬
 
#include <stdio.h>
 
int main()
{
    int a[5] = { 5, 4, 3, 2, 1 };
    int i, j, k, temp;
 
    for (i = 0; i < 5 - 1; i++)
    {
        printf("step%d\n", i+1);
 
        for (j = 0; j < 5 - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
            printf("%d번째 비교:", j + 1);
            for (k = 0; k < 5; k++)
            {
                printf("%d", a[k]);
            }
            printf("\n");
        }
 
        printf("\n");
    }
    return 0;
}

버블 정렬 과정

 

step1

1번째 4와 5를 비교하여 5를 뒤로이동.

2번째 5와 3을 비교하여 5를 뒤로 이동.

step1이 끝나면 맨 앞의 5가 맨 뒤로 이동하는 것을 볼 수 있다.

 

나머지 step도 마찬가지.

 

 

그러나 이 방법은 비효율적이며 배열의 원소 수가 많을 경우 연산 낭비이다.

 

step2의 4번째

step3의 3번째 4번째

step4의 2번째 3번째 4번째

원소의 순서가 변하지 않는 낭비 연산임을 알 수 있다.

 

 

원소의 순서가 변경될 때만 출력해보면

확실하게 절반 정도의 연산이 낭비임을 알 수 있다.

 

원소의 순서가 변경 될 때만 출력

 

맨 위의 그림처럼 정렬이 완료된 마지막 원소를 제외하고

정렬을 하면 효율적인 알고리즘이 될 것이다.

 

//버블정렬
//2. 정렬된 원소를 제외한 나머지 원소 정렬
 
#include <stdio.h>
 
int main()
{
    int a[5] = { 5, 4, 3, 2, 1 };
    int i, j, k, temp;
 
    for (i = 0; i < 5 - 1; i++)
    {
        printf("step%d\n", i + 1);
 
        for (j = 0; j < 5 - (i+1); j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
            printf("%d번째 비교:", j + 1);
            for (k = 0; k < 5; k++)
            {
                printf("%d", a[k]);
            }
            printf("\n");
        }
 
        printf("\n");
    }
    return 0;
}

 

단순 버블정렬과 다른 부분은

for (j = 0; j < 5 - (i+1); j++)

고작 이부분.

 

반복 횟수인 i번을 추가로 빼주는 것이다.

 

의미는

 

step1에서는 원소가 5개 이므로 4번 모두 비교를 하고

step2에서는 step1에서 정렬이 된 마지막 원소를 제외하고 3번 비교를 한다.

...

step4에서는 맨 앞 두 원소만 비교하여 정렬한다.

 

효율성을 개선한 버블정렬

 

하지만 이 알고리즘도 완벽하게 효율적인 알고리즘이 아니다.

 

완전하게 내림차순인 경우의 배열만 이 알고리즘이 효율적이다.

 

만약 배열에 {1,2,3,5,4}가 저장되어 있다면

 

 

사진 설명을 입력하세요.

step1에서 {1,2,3,4,5} 로 정렬이 되고

나머지 step는 연산 낭비이다.

 

이는 한 step진행 후

원소 순서에 변화가 생기는지 여부를 확인 할 수 있는

flag변수를 사용해서 비효율을 줄일 수 있다.

 

이부분은 생략한다.

---

 

연습 문제

 

11, 12번을 풀어보겠다.

 

 

문제 11: 2*3 행렬 A와 3*4 행렬 B를 곱한 결과인 2*4 행렬 C를 구하여 다음과 같이 출력하시오.

 

//연습문제 11
 
#include <stdio.h>
 
int main()
{
    int A[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };
    int B[3][4] = { { 3, 4, 5, 6 }, { 1, 2, 4, 3 }, { 4, 2, 6, 1 } };
    int C[2][4] = { 0, };
    int i, j, k;
    int sum = 0;
 
    printf("행렬A\n");
    for (i = 0; i < 2; i++){
        printf("[ ");
        for (j = 0; j < 3; j++)
        {
            printf("%d ", A[i][j]);
        }
        printf("]\n");
    }
    printf("\n");
 
    printf("행렬B\n");
    for (i = 0; i < 3; i++){
        printf("[ ");
        for (j = 0; j < 4; j++)
        {
            printf("%d ", B[i][j]);
        }
        printf("]\n");
    }
    printf("\n");
 
    for (i = 0; i < 2; i++)
    {
        for (j = 0; j < 4; j++)
        {
            for (k = 0; k < 3; k++)
            {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
            sum = 0;
        }
    }
 
    printf("행렬C=A+B\n");
    for (i = 0; i < 2; i++){
        printf("[ ");
        for (j = 0; j < 4; j++)
        {
            printf("%d ", C[i][j]);
        }
        printf("]\n");
    }
 
    return 0;
}

 

3중 for문을 사용하여 곱셈하는데

약간 복잡하지만 충분히 생각해보면 이해가 된다.

 

 

 

 

문제 12: 10개 문항이 있는 학생 10명의 시험 답안지로부터 채점을 한 후 결과를 다음과 같이 출력하시오. 학생 10명의 시험 답안지는 다음과 같이 2차원 배열을 선언하면서 초기화한다.

 

#include <stdio.h>
#define STUDENT 10
#define N 10
 
int main()
{
    int paper[STUDENT][N] = 
    { { 1, 3, 2, 3, 4, 2, 3, 1, 4, 3 }, { 1, 2, 2, 2, 4, 2, 3, 1, 4, 2 },
    { 4, 3, 2, 3, 4, 2, 3, 1, 4, 2 }, { 1, 3, 2, 2, 4, 3, 3, 4, 4, 2 },
    { 1, 3, 2, 3, 4, 2, 3, 3, 4, 1 }, { 1, 1, 2, 4, 4, 3, 3, 2, 4, 3 },
    { 1, 3, 2, 3, 4, 2, 3, 1, 4, 2 }, { 1, 3, 2, 3, 3, 2, 3, 1, 4, 2 },
    { 2, 3, 3, 3, 3, 2, 4, 1, 4, 2 }, { 3, 4, 4, 2, 4, 1, 2, 1, 4, 2 } };
    
    int answer[N] = { 1, 3, 2, 3, 4, 2, 3, 1, 4, 2 };
    int score[STUDENT] = { 0, }; //각 학생의 점수배열
    int order[STUDENT] = { 0, }; //각 학생의 등수
    int high = 0; //자신보다 높은 점수 있으면 1개씩 증가시키기
    int i,j;
 
    printf("\t문항별 채점 결과\n");
    printf("=========================================\n");
    
    printf(" 문항");
    for (i = 0; i < N; i++)
    {
        printf("%3d",i);
    }
    printf("  점수\n");
    printf("=========================================\n");
    
    for (i = 0; i < STUDENT; i++) //점수 및 맞고 틀린 문제 확인
    {
        printf("%3d번", i+1);
        for (j = 0; j < N; j++)
        {
            if (paper[i][j] == answer[j])
            {
                printf("%3c",'o');
                score[i]++;
            }
            else
                printf("%3c",'x');
        }
        printf("  %d점\n",score[i]);
    }
 
    for (i = 0; i < STUDENT; i++)
    {
        for (j = 0; j < STUDENT; j++)
        {
            if (score[i] < score[j])
                high++; 
        }
        order[i] = high + 1;
        high = 0; //자신 점수보다 높은 학생 수 0으로 초기화
    }    
 
    printf("\n\n\t  정렬 및 석차\n");
    printf("\t=================\n");
    printf("\t번호 점수 석차\n");
    printf("\t=================\n");
    for (i = 0; i < STUDENT; i++)
    {
        for (j = 0; j < STUDENT; j++)
        {
            if (order[j] == i+1)
                printf("\t%2d번%3d점%3d등\n", j + 1, score[j], order[j]);
        }
    }
    printf("\t=================\n");
 
    return 0;
}