배열의 기초

(1)

::

배열의 기초

1차원 배열의 활용(교재 39장)

(2)

2 MJU CE C Language Programming

학습 내용

 The need for arrays

 Declaration and use

 C 배열의 특징

 Address 계산법

(3)

 C교수는 수업시간에 학생들에게 일련번호를 부여하고 실습실에 테이블 번호대로 앉게 한다. 왜 그럴까 이유 를 생각해보라.

(4)

번호의 좋은 점

 이름 대신 번호로 지칭

 반복 구조를 단순화 할 수 있음.

김선화, 이명진, 홍길동, 조성민, ...

1번부터 10번까지 완전군장 집합!!!

(5)

변수 작명의 한계: 예제 1

 세 개의 숫자를 입력하고 이들의 합과 평균을 구하라.

평균 보다 큰 점수를 출력하라.??

 int x,y,z;

 float mean;

 scanf("%d %d %d", &x, &y, &z);

 mean = (x+y+z)/3.0;

 if (x>mean) printf("%d\n",x);

 if (y>mean) printf("%d\n",y);

if (z>mean) printf("%d\n",z);

(6)

 100개의 숫자를 입력하고 이들의 합과 평균을 구하라.

평균 보다 큰 수를 출력하라.

 int x1,x2,x3,x4,x5,x6, ..., x98,x99,x100

 scanf("%d %d %d %d ....", &x1, &x2, &x3, ...

&x99, &x100);

 ???

(7)

 우리 학교 학생들의 키의 평균을 구하라...

 수천개의 변수를?

(8)

수학에서는...

N

x x

n i

i

2 ,

1

) ( 





N x x

ⁱ ^N



i



¹^,

아래 첨자(subscript)

(9)

C언어에서는 …

 첨자가 붙은 변수를 "배열"이라고 한다.

X

1

Y

n

X

2

X[1]

X[2]

Y[n]

수학 기호 C언어 기호

(10)

CFL array

(11)

진짜 장점은 반복 구조

(12)

배열의 선언과 사용

 int a[10]; // 선언. CFL에 없던 부분.

 float b[100]; // 선언

231 0 123 5

배열의 각 원소는 정수

각 element의 이름 a[0] a[1] a[2] a[9]

0 번째 요소 1 번째 요소

(13)

배열 원소의 사용

 a[0] = 123; b[2] = b[31];

 b[99] = 0.1827;

 i = 31; a[i+1] = a[i]; a[i] = i ;

 a[i+0.5] ??

일반 변수와 배열의 한 원소는 동격이다.

(14)

연습

 lab18_02 선언 연습

 lab18_03 배열 인덱스 사용 연습

(15)

배열의 응용: 반복

 score0 = 0;

 score1 = 0;

 score2 = 0;

 …

 score[0] = 0;

 score[1] = 0;

 score[2] = 0;

 …

 n = 0;

 score[n] = 0;

 n++;

 score[n] = 0;

 n++;

 score[n] = 0;

 n++;

반복문(while/for)으로 !!

(16)

연습

 lab18_04 반복문에서 배열 사용

(17)

실습 lab18_05(array_repeat.c)

 int score[5];

 score[0] = 0; score[1] = 2;

 score[2] = 4; score[3] = 6; score[4] = 8;

 printf("%d\n", score[4]);

 ...

 위의 프로그램을 2개의 for(혹은 while)을 이용하여 간략하게 만들어보라. (assignment용, print용)

(18)

입출력

 printf("%d %f", a[i], b[0]);

 scanf("%d %f", &a[i], &b[0]);

(19)

배열 입력 연습

 lab18_06

(20)

C array의 특징

 index (즉, 첨자)는 0부터 시작한다.

 선언에서의 첨자는 총 갯수

 따라서 int a[100]; 으로 선언하면

 a[0], a[1], a[2], ... a[99] 까지임

 첨자가 범위를 넘어도 문법적으로는 하자 없음 – only runtime error (프로그래머 책임)

(21)

배열 원소의 초기화

 int a[5] = { 1,2,3,4,5 };

 int b[5] = {1, 2, 3};

 int c[5] = {1,2,3,4,5,6,7};

 int d[] = {1,2,3,4};

 int f[10] = {};

 *주의:

int a[5]={0}; // 0 0 0 0 0 int b[5]={1}; // 전부 1 ??

(22)

실습: 배열 초기화 연습

 lab18_07

(23)

Good Programming Style

 배열 개수와 초기화 항목 수를 같게 한다.

 일부만 초기화가 필요하거나 전부 0으로 초기 화 할 경우 Comment를 달아준다.

int a[5]={1,0,0,0,0};

int c[100]= {}; // 전부 0으로 초기화

int b[5]={1}; // b[0]만 1이고 나머지는 0

(24)

배열과 메모리

 연속된 공간을 사용함

score[0]

int score[4];

score[1] score[2] score[3]

시작이

1000번지라면

1004 1008 1012

(25)

왜 연속된 공간을 사용하나?

vs.

(26)

실습 lab18_08(addr.c;result.txt)

 '&' 연산자는 주소를 뜻하는 연산자이다.

 int A[10]으로 선언하고 A[0] 부터 A[9]까지 주소를 '&'연산자를 이용하여 출력한다.

(A[i]의 주소는 &A[i] 로 쓴다.)

 while 문을 이용

 출력 포맷은 %d 가 아닌 %u를 이용한다.

(Warning은 무시해도 좋다.)

(27)

배열 원소의 주소 계산

 score[i]의 주소는?

❖ score[0]의 주소 + i*4

score[0]

int score[4];

score[1] score[2] score[3]

시작이

1000번지라면

1004 1008 1012

(28)

C언어 배열의 index오류

 모든 책임은 프로그래머에게

 장점: 프로그램 효율성이 좋다.

 단점: 오류의 탐지가 어렵다.

(29)

배열의 한계 ?

 배열의 index가 범위를 넘어가면 C언어에서는 어떻게 취급될까?

(30)

인원수의 착각

 1분대가 5명인데 6명으로 착각하고 분대장이 얼차려 를?

1분대 2분대

(31)

실습 lab18_09

 배포된 index.c 파일을 실행하여보고 여기서 알 수 있는 사실을 report.txt에 작성하여 제출 한다.

(32)

해설

(33)

데모

 a_limit.c 를 실행하여 언제까지 출력이 되는지 살펴보라.

Question:

C언어에서 배열의 한계를 초과하면 즉시 반응이 오나?

(34)

세그멘테이션 오류

 (Segmentation fault)

 int A[5], B[5], c[5];

 B[0] = 0; // 나의 메모리, 정상적인 참조

 B[6] = 0; // 비정상적인 참조이지만 나의 메모리

 A[100000] = 0; // 아마도 남의 메모리

A[0] A[1] A[2]…

나의 세그멘트 남의 세그멘트

(35)

assert 의 이용

 #include <assert.h>

 int main(){

 int idx;

 scanf("%d", &idx);

 assert(idx<10 && idx>=0);

 printf("OK\n");

#define NDEBUG // 더 이상 필요 없을 때, include 앞.

(36)

lab 18_10 assert.c

 배포된 assert.c 에서는 배열 인덱스가 범위를 초과할 수 있다. assert를 이용하여 범위 초과시 오류 메시지 를 출력하고 종료하도록하라.

(37)

숙제 lab18_11 (scores.c)

 최대 100명이 수강할 수 있는 과목의 성적 처리 프로 그램을 작성한다. 실제 학생 수는 프로그램할 당시에 는 알 수 없다.

 성적은 배열 score[100]에 scanf로 입력한다. EOF가 나오면 그 때 까지 정상 입력된 수의 개수가 바로 학생 의 수이다.

 총 학생 수를 출력하고 입력된 성적을 뒤에서 앞으로 ( 입력된 순서의 역순으로) 출력한다.

 (다음 hint)

(38)

Hint 1

 일단 데이터를 읽어 들이는 것부터 작성하여 테스트해 본다. (즉 while 하나로 읽자 마자 바로 출력하여 테스 트)

 성공하면 또 다른 while 문으로 역순 출력을 하면 된다 .

(39)

Hint

 int num = 0; 으로 선언

 while (scanf("%d", &scrore[ ?? ]) == 1){



 num 을 증가시킨다.

 }

 // 이 위치에서는 학생 수를 알 수 있다. 이 수는 보존한다. (왜

?)

 while 문을 이용하여 마지막 번호부터 앞으로 출력한다.

 즉 score[num-1], score[num-2], … score[1], score[0]

의 순서이다.

(40)

숙제: lab18_12 (score2.c)

 성적 처리 프로그램 score.c를 수정하여 평균점수를 출력하고, 평균 보다 점수가 높은 학생의 번호(index) 와 점수를 출력하도록 한다.

 예:

 평균: 70

 학생 0 : 100 점

 학생 3 : 80 점 ...

(41)

연습 문제 18_13, 14

(42)

1차원 배열을 함수로 전달하기

 void fun(int data[]){

 data[0] = 99; data[1] = 88;

 }

 main:

int score[5]={ 1,1,2,3,4};

fun(score);

 // 결과는?

형식인자의 배열 크기는 의미 없다 써도 되고

안 써도 된다.

(43)

1차원 배열을 함수로 전달하기

 int sum_array(int count, int data[]){

 // 전체의 합을 구해서 돌려준다.

 }

 main:

int score[5]={ 1,5,6,7,8};

int english[4] = { 50, 60, 70, 80 };

sum= sum_array (5, score);

// sum 출력

형식인자의 배열 크기는 의미없다 써도 되고

안 써도 된다.

(44)

실습 (1822)

 주어진 배열의 모든 원소의 합을 구하여 돌려주는 함수 sum_array를 작성하라.

 int sum_array(int count, int data[]){ .. }

 다음과 같이 테스트한다.

 int score[5]={ 1,5,6,7,8};

int english[4] = { 50, 60, 70, 80 };

sum= sum_array (5, score);

// sum 출력

 sum = sum_array(4, english);

 // sum 출력

(45)

Project 1. Bubble sort

 배열의 크기 count와 정수 배열 data를 전달했을 때 이를 내림차순으로 버블 정렬하는 함수

void bubble_sort(int count, int data[100]);

이를 활용하여 표준입력에서 읽어들인 100개 이하의 정수에 대해 정렬을 하여 순서대로 출력하게 하라.

 단, 입력 또한 함수를 이용한다.

 int read_array(int data[]);

 // read_array의 반환 값은 실제 읽어들인 정수의 개 수가 되게 한다.

(46)

Bubble sort 개요

9 8 1 2 6 6 4 3

8 1 2 6 6 4 3 9 1회 실시후

8 9

1 2 6 6 4 3 2회 실시후

A[0]:A[1] A[1]:A[2] A[6]:A[7]

8개 데이터를 다 정렬하려면 몇 회 필요?

(47)

범위를 넘기면…

9 8 1 2 6 6 4 3

8 1 2 6 6 4 3

A[0]:A[1] A[1]:A[2] A[6]:A[7]

0

A[7]:A[8]

9 0

쓰레기

(48)

효율성

9 8 1 2 6 6 4 3

8 1 2 6 6 4 3 9 8 9

1 2 6 6 4 3

A[0]:A[1] A[1]:A[2] A[6]:A[7]

A[0]:A[1] A[1]:A[2] A[5]:A[6]

A[0]:A[1]

첫번째 시행

두번째 시행

마지막 시행

(49)

실습 1878

 8개의 데이터를 버블 정렬한다고 했을 때에 비교하는 index 만을 출력하라.

출력 양식은 0:1

1:2 2:3 ...

 이런 방식이면 된다

(50)

Project: 성적 처리

 Sort를 이용한 성적 처리(최대 100명)

 학생 들의 학번, 국어, 영어 성적이 정수로 입력된다. 순서는 학 번1, 국어1, 영어1, 학번2, 국어2, 영어2, … 등의 순서이며 입 력이 더 없으면 처리를 시작한다.

 각 학생의 평균 점수를 기록한다. (float)

 평균 점수를 기준으로 내림차순 bubble 정렬한다.

이때, 학번과 국어 영어 성적이 함께 움직여야 함을 기억하자.

 letter grade by percentage (30% 이내 A, 50% 이내 B, 70% C, 나머지 D학점을 기록한다)

 전체 성적표를 출력한다. (다음 페이지)

(51)

출력물

순위 학번 국어 영어 평균 학점

1 60111119 95 97 96.0 A 2 60111112 91 92 91.5 A 3 60111111 85 86 85.5 B 등등

(52)

단계별

 1단계: Pseudo-code 로 각 단계를 분리, 설명하고 각 단계별로 어떻게 테스트할 것인지 설명한다.

 2단계: 각 데이터를 위한 변수를 선언한다.

 3~N단계: 각 단계별로 구현 및 테스트를 한다.

(53)

실습

 성적처리를 위한 프로그램의 설계를 한다.

 Pseudo-code (가상 코드)로 각 단계를 분리하여 설명 하고 각 단계별로 어떻게 테스트할 것인지 설명한다.

 design.txt에 작성하여 5분안에 제출한다.

(제출 후 sample review)

(54)

연습...

(55)

입력 반복하는 방법 1

 numData = 0;

 while ( scanf("%d", &s)==1 ){

 data[numData ] = s;

 numData ++;

 }

(56)

입력 반복 2

 최대 개수까지 고려

 while ( ??? && scanf( )==1 ){

 }

(57)

Project2. 삽입 정렬

 정수가 입력되면 100개 짜리 배열을 이용하여 크기 순 으로 저장하고 현재 개수를 기억하는 프로그램을 작성 하라. 입력되는 정수는 크기 순이 아니기 때문에 앞에 서부터 비교해가며 넣을 위치를 찾아야한다. 위치를 찾으면 먼저 그 뒤에 있는 데이터를 전부 뒤로 밀고 나 서 새 데이터를 넣어야 한다.

 단계1. 위치 찾기

 단계2. 뒤로 밀기



(58)

data[0] data[1] data[2] data[3] data[4] data[5] data[6] data[7]

♥

6

♥

7

♥

8

♥

9

♥

2

♥

4

♥

1

♥

3

(59)

단계1 (isort1.c 배포)

 int data[100]={ 1,2,3,4,7,8,9 };

 int size; // 현재 들어있는 개수

 int next; // 이번에 넣을 수

 size = 7; next = 6;

 next를 포함하여 순서대로 정렬한다면 몇 번째에 집어 넣어야 되는지를 찾는다.

 즉, next를 넣을 위치 insert_pos 를 찾아내어 출력해 본다. (정답은 4)

(60)

data[0] data[1] data[2] data[3] data[4] data[5] data[6] data[7]

♥

6

♥

2

♥

1

♥

3

♥

4

♥

8 7

♥

9

(61)

단계2/isort2.c

 int data[100]={1,2,3,4,7,8,9 };

 int size=7; // 현재 들어있는 개수

 int next = 6; // 이번에 넣을 수

 int insert_pos ; // next 가 들어갈 위치

 insert_pos 를 찾은 다음

 insert_pos 부터 size-1 까지의 데이터를 하나씩 뒤로 옮겨야 한다. 그러나 뒤에서부터 해야 지워지지 않는 다.

 size를 변경해야 한다. (1 증가)

(62)

1 2 3 4 7 ⁸ ⁹

6

…

data[ ]  data[ ] data[ ]  data[ ] data[ ]  data[ ]

(63)

단계 3(최종 isort.c)

 size = 0 으로 초기화 한 상태에서

 while (scanf("%d", &next) ==1 ){

 // 찾고

 // 뒤로 밀고

 // 삽입하고 필요한 변수 update

 }

 // 정렬된 데이터를 순서대로 출력

(64)

변형

 Insertion sort를 하되 데이터 입력이 모두 끝난 뒤에 정렬을 시작한다.

 정렬 시작전:

최초 1개는 정렬이 되어 있다고 생각하고 1번 항목(여 기서는 8) 부터 삽입을 한다.

9 8 6 7 1 ² ³ ⁴ ⁵

(65)

단원 요구사항

 배열의 선언하고 사용할 수 있어야 한다.

 배열의 index로서 정수 수식을 사용할 수 있어야 하며 반복문 을 사용하여 배열의 여러 요소에 반복적인 계산을 할 수 있어야 한다.

 배열의 한계와 프로그래머의 책임에 대하여 이해를 하고 있어야 하며 배열 주소의 계산 방법을 이해해야한다.

 배열요소의 입출력, 요소간의 이동, 복제를 활용할 수 있어야 한다.

 각종 sort 알고리즘의 설명이 주어졌을 때에 주어진 데이터를 sort하는 프로그램을 작성할 수 있어야 한다.