배열(Array) 선린인터넷고등학교 정보통신과 유 순 옥.

Presentation on theme: "배열(Array) 선린인터넷고등학교 정보통신과 유 순 옥."— Presentation transcript:

1 배열(Array) 선린인터넷고등학교 정보통신과 유 순 옥

2 배열의 개요

3 데이터 선언과 기억장소 int data; 만약 10명의 점수를 저장한다면 변수명은 몇 개 필요할까요? data data1

4 배열은 왜 사용할까? 하나의 변수명에 자동으로 번호를 부여하도록 하면 편하다. int data[5]; data data[0]

5 배열의 개요 배열이란 a b 동일한 데이터형 변수의 모임
같은 형식의 여러 데이터를 하나의 변수에 긴 띠모양으로 저장하여 사용하는 자료의 집합체 a 정수 배열로 사용할 수 없다. b 정수 문자열 실수 데이터 형이 다르기때문

6 배열의 개요 배열이란 배열 변수 저장되는 데이터의 종류는 동일한 형이다. 각각의 데이터는 인덱스(첨자)로 구분한다.
여러 개의 데이터를 1개의 이름으로 기억 저장되는 데이터의 종류는 동일한 형이다. 각각의 데이터는 인덱스(첨자)로 구분한다. 첨자는 0부터 시작 첨자의 수에 따라 1차원 배열, 2차원 배열, …

7 배열의 개요 배열 이름 a 배열 요소가 기억되어 있는 메모리의 첫 번째 주소 인덱스(첨자) 1 2 3 4 배열명 데이터
1 2 3 4 a 배열명 데이터 배열 요소 a[0] a[1] a[2] a[3] a[4]

8 배열의 개요 배열의 선언 자료형 배열명[배열 크기] (예) int a[5] 인덱스(첨자) 1 2 3 4 int 배열명 a
자료형 배열명[배열 크기] (예) int a[5] 인덱스(첨자) 1 2 3 4 int 배열명 a a[0] a[1] a[2] a[3] a[4] 배열 요소

9 [예제 7-1] 원소에 직접 값 대입 #include <stdio.h> void main() { int a[5]; // 정수형배열a[5]를선언 a[0]=3; a[1]=7; a[2]=2; a[3]=1; a[4]=6; // 세번째와 다섯번째 원소를 출력하여라. } printf( "a[2]=%d, a[4]=%d \n", a[2],a[4]);

10 [예제 7-2] scanf()로 배열에 값 저장 a
#include <stdio.h> void main() { int i, a[5]; for(i=0; i<5; i++) { printf("a[%d]=",i); scanf( "%d", &a[i] ); } for(i=4; i>=0; i--) { printf("%3d", a[i] ); a a[0] a[1] a[2] a[3] a[4] 배열에 저장된 값을 역순으로 출력하여라.

11 배열은 for문으로 #include<stdio.h> int main(){ int i, a[10]; for(i=0; i<10; i++){ printf("%d", a[i]); } 초기화하지 않으면 배열요소에는 쓰레기값 저장

12 1차원 배열의 초기화

13 1차원 배열의 초기화 #include<stdio.h> int main(){ int i, a[]={3,2,7,6,9}; for(i=0; i<5; i++){ printf("%5d", a[i]); } 3 2 7 6 9

14 1차원 배열의 초기화 #include<stdio.h> int main(){ int i, a[]={3, 6, 2}; for(i=0; i<5; i++){ printf("%5d", a[i]); } 3 6 2

15 1차원 배열의 초기화 #include<stdio.h> int main(){ int i, a[5]={5, 8, 3}; for(i=0; i<5; i++){ printf("%5d", a[i]); } 5 8 3

16 1차원 배열의 초기화 #include<stdio.h> int main(){ int i, a[5]={4, }; for(i=0; i<5; i++){ printf("%5d", a[i]); } 4

17 1차원 배열의 초기화 #include<stdio.h> int main(){ int i; int a[5]; for(i=0; i<5; i++){ printf("%5d", a[i]); } 쓰 레 기 값 짱

18 1차원 배열의 초기화 #include<stdio.h> int main(){ int i; static int a[5]; for(i=0; i<5; i++){ printf("%5d", a[i]); }

19 실습 void prt_array(int a[]); void prt_array(int a[]){ int i;
#include <stdio.h> void main(){ int a[5]; int b[5]={0}; int c[5]={0,}; int d[5]={1, 2, 3}; int e[5]={4, 5, 6, 7, 8}; prt_array(a); // 배열의 값을 출력하는 함수 prt_array(b); prt_array(c); prt_array(d); prt_array(e); } void prt_array(int a[]); void prt_array(int a[]){ int i; for(i=0; i<=4; i++) printf("%5d", a[i]); printf("\n"); }

20 [문제] 10개의 데이터(정수)를 초기화하고 합을 구하여라.
#include <stdio.h> void main() { int i, a[10]={ 3, 7, 6, 4, 8, 9, 12, 2, 10, 1 }; int sum=0; for(i=0; i<10; i++) { sum+=a[i]; } printf("sum=%d\n", sum);

21 합 구하기

22 [문제] 10개의 데이터를 초기화하고 홀수 데이터의 합을 출력하여라.
#include <stdio.h> void main() { int i, a[10]={ 3, 7, 6, 4, 8, 9, 12, 2, 10, 1 }; int sum=0; for(i=0; i<10; i++) { if(a[i]%2 ) sum+=a[i]; } printf("sum=%d\n", sum);

23 [문제] 10개의 데이터를 초기화하고 홀수 데이터의 합을 출력하여라.
#include <stdio.h> int odd( int []); void main() { int a[10]={ 3, 7, 6, 4, 8, 9, 12, 2, 10, 1 }; int sum=0; sum=odd(a); printf("sum=%d\n", sum); } Int odd( int a[]){ int i, sum=0; for(i=0; i<10; i++) { if(a[i]%2 ) sum+=a[i]; } return sum;

24 피보나치 수열을 출력 1 1 2 3 5 8 13 21 34 피보나치 수열 초기화 F(0) = 0 F(1) = 1
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[10] 1 1 2 3 5 8 13 21 34 피보나치 수열 이전의 두 항의 합을 구하여 다음항의 값을 생성 초기화 F(0) = 0 F(1) = 1 F(2) = 1 F(3) = 2 ..... F(n) = F(n-1) + F(n-2) 배열로 처리

25 피보나치 수열

26 실습 #include<stdio.h> void main() { int i, a[10]={0,1}; for(i=2;i<10;i++) a[i] = a[i-2] + a[i-1]; } for(i=0;i<10;i++) printf("a[%d] = %d\n",i, a[i]);

27 소수 구하기

28 1에서 100까지의 수 중에서 소수 출력하기 배열 101개 선언 : num[101] 배열에 모두 0으로 초기화
i=2 ~ 100까지 반복 배열의 값이 0이면 첨자 출력 if( num[i] == 0) i 출력 첨자의 배수에 해당하는 첨자의 배열에 1 저장 for( j=i; j<=100; j+=i) num[j] = 1;

29 소수 구하기 1 첨자 2 3 4 5 6 7 8 9 10 11 2 출력 1 3 5 7 초기화 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7

30 1~100까지의 수 중에서 솟수 구하기 #include <stdio.h> void main() { int i, j, count=0; int num[101]={ 0, }; for( i=2; i<=100; i++ ) { if( num[i]==0 ) { printf("%4d", i ); count++; if( count%10==0 ) printf("\n"); for(j=i; j<=100; j+=i ) { num[j]=1; }

31 소수 구하기 2 배열 101개 선언 : num[101] 첨자와 같은 값을 배열에 저장 2 ~ 100까지 반복
배열의 값이 0이 아니면 배열 값 출력 if( num[i] ) num[i] 출력 첨차의 배수에 해당하는 첨자의 배열에 0 저장 for( j=i; j<=100; j+=i) num[j] = 0; 2 3 4 5 6 7 8 9 10 11

32 소수 구하기 2 첨자 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 11 출력 초기화 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7

33 프로그램 #include<stdio.h> void main() { int i,j, cnt=0, num[101]; for(i=2; i<=100; i++) // 저장 num[i]=i; //처리 for(i=2; i<=100; i++){ if(num[i]){ cnt++; for(j=i*2; j<=100; j+=i){ num[j]=0; } printf("\n\n 처리한후배열에저장된값"); for(i=2; i<=100; i++){ // 출력 if(num[i]) printf("%5d", num[i]); printf("\n\n 갯수= %d", cnt);

34 석차구하기 #include<stdio.h> void main(){ int kor[5], eng[5], sum[5]; float avg[5]; int rank[5]={1,1,1,1,1}; int i,j; //1. 국어영어점수입력 for(i=0; i<5; i++){ scanf("%d %d", &kor[i], &eng[i]); } //2. 총점평균구하기 sum[i]=kor[i]+eng[i]; avg[i]=sum[i]/2; //3. 석차구하기 for(i=0; i<5; i++){ // 기준값 for(j=0; j<5; j++){ // 비교값 if(sum[i] < sum[j]) rank[i]++; printf("국어 영어 총점 평균 석차\n"); //4. 출력하기 printf("%d %d %d %.1f %d \n",kor[i],eng[i],sum[i],avg[i],rank[i] );

35 정렬

36 정렬이란 임의의 순서대로 나열되어 있는 자료들을 일정한 기준에 의해 다시 재 나열하는 것 오름차순 정렬 내림차순 정렬
가나다순으로 정렬 작은 수에서 큰 수 순으로 정렬 내림차순 정렬 학교 성적표의 석차 큰 수에서 작은 수 순으로 정렬

37 정렬의 종류 삽입 정렬(insertion sort) 선택 정렬(selection sort) 버블 정렬(bubble sort)
퀵 정렬(quick sort) 쉘 정렬(shell sort) 힙 정렬(heap sort) 병합 정렬(merge sort) 기수 정렬(radix sort) 버킷 정렬(bucket sort)

38 정렬의 기본동작 정렬을 할 때 사용되는 기본 동작은 판단과 교환이다.
판단은 두 개의 값을 비교하여 크고 작음을 판단하는 과정이고, 교환은 판단 결과에 따라 두 개 값의 위치를 바꾸는 작업을 말한다.

39 배열에 저장된 두 개의 값 교환 3 5 5 3 if(a[0] < a[1]){ c = a[0]; a[0] = a[1];
}

40 비교후 교환 “만약 a의 값이 b 값보다 작으면 a와 b의 값을 바꿔라.”를 명령문으로 기술해보면 다음과 같다.
if(a < b){ c = a; //c 는 임시변수 a = b; // b = c; // } if(a[i] < a[j]){ c = a[i]; a[i] = a[j]; a[j] = c; }

41 선택 정렬(Selection Sort) ① 첫 번째 키를 기준키로 설정하며, 기준키로 설정된 값과 두 번째 위치, 세 번째 위치, … n 번째 위치의 값과 비교 하면서 가장 작은 값을 선택하여 교환한다. ② 두 번째 키를 기준기로 설정하여 기준키로 설정된 값과 세 번째 위치, … n 번째 위치의 값과 비교 하면서 가장 작은 값을 선택하여 교환한다. ③ n-1번째 키까지 위의 과정을 반복한다.

42 선택 정렬(오름차순) 기준값 비교값 기준값 > 비교값 이면 교환 기준값 비교값 기준값 비교값 기준값 비교값

43 선택 정렬(오름차순) 7 1 6 5 9 3 8 2 입력자료 step1 step2 step3 step4 step5 step6
결과

44 개선된 선택정렬 방법 (오름차순 정렬시) 1) 배열에서 가장 작은 수를 찾아 첫 번째 위치에 있는 수와 교환한다.
2) 첫 번째 수를 제외하고 가장 작은 수를 찾아 두 번째 위치에 있는 수와 교환 3) 두 번째까지 수를 제외하고 가장 작은 수를 찾아 세 번째 위치의 수와 교환 4) 전체가 정렬될 때까지 계속 반복

45 선택 정렬(오름차순) 7 1 6 5 9 3 8 2 입력자료 step1 step2 step3 step4 step5 step6
결과

46 선택정렬

47 선택정렬 min = a[i]; index = i; for(j=i+1; j<n; j++){ a[index] = a[i];
void Selection_Sort(int a[], int n){ int i, j; int min, index; for(i=0; i<n-1; i++){ min = a[i]; index = i; for(j=i+1; j<n; j++){ if(min>a[j]){ min=a[j]; index = j; } a[index] = a[i]; a[i] = min;

48 버블 정렬 인접한 요소를 비교하여 교환하는 모양이 마치 거품이 보글보글하는 모양과 같다고 해서 붙여진 이름으로, 매 단계에서 인접한 원소들을 비교하고 교환하면서 정렬하는 방법이다.

49 버블 정렬 [ 버블 정렬 방법 ] ① 첫 번째 레코드와 두 번째 레코드의 키를 비교하여 키 값이 작은 레코드를 앞에 놓은 후, 두 번째 레코드와 세 번째 레코드의 키를 비교하여 키 값이 작은 레코드를 다시 앞에 놓는 과정을 반복해서 맨 마지막으로 n-1번째와 n번째 레코드를 비교하여 위치를 교환하여 n번째 위치하는 레코드가 가장 큰 키 값을 가진 레코드가 되도록 하면 1단계가 종료된다. ② 다시 n 번째 위치한 레코드를 제외하고 첫 번째에서 n-1번째의 레코드를 위와 같은 방법으로 반복하면 n-1번째에 두 번째로 큰 레코드가 놓이게 된다. ③ 이와 같은 작업을 n-1회 반복하면 정렬이 완료된다.

50 버블 정렬

51 버블 정렬

52 버블 정렬 bubble_Sort(int a[], int count){ int i, j, k, temp; for(i=1; i<count; i++){ for(j=0; j<count-i; j++){ if(a[j] > a[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }

53 개선된 버블 정렬 데이터를 정렬해보면, step1 : 한번 이상 교환이 이루어졌으므로, flag=1 step2 : 한번 이상 교환이 이루어졌으므로, flag=1 step3 : 한번도 교환이 이루어지지 않았으므로, flag=0 종료된다.

54 개선된 버블 정렬 Bubble_Sort(int a[], int count){ int i, j,k, temp, flag; for(i=1; i<count; i++){ flag = 0; for(j=0; j<count-i; j++){ if(a[j] > a[j+1]){ temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; flag = 1; } if(flag == 0) return 1; return 0;

55 삽입 정렬 삽입 정렬은 이미 정렬된 데이터에 새로운 데이터가 입력될 때마다 적절한 위치를 찾아 삽입하는 동작을 반복적으로 수행하여 정렬하는 방식이다.

56 삽입 정렬 [ 삽입 정렬 방법 ] ① 맨 뒤의 데이터와 삽입하고자 하는 데이터를 비교한다.
② 삽입하고자 하는 데이터가 더 작으면 이미 정렬된 데이터를 한 칸 뒤로 이동하여 빈 ③ 삽입하고자 하는 데이터가 클 때까지 ②번을 반복 수행한다. ④ 삽입하고자 하는 데이터가 크면 추가하는 과정을 n번 수행하면 정렬이 완료된다.

57 삽입 정렬

58 삽입 정렬 insertion_Sort(int a[], int count){ int i, j,k, temp; for(i=0; i<count; i++){ temp = a[i]; for(j = i-1; j>=0; j--){ if(temp>= a[j]) break; a[j+1] = a[j]; } a[j+1] = temp;

59 검색

60 검색 검색이란 주어진 자료에서 조건에 만족하는 어떤 특정한 값을 찾는 것을 말한다.

61 선형 탐색(Linear Search) 선형 탐색은 가장 단순한 알고리즘으로 주어진 파일에서 레코드의 처음부터 마지막까지 읽어가면서 순차적으로 비교하면서 원하는 자료를 찾는 것이다.

62 선형 탐색(Linear Search) [ 선형 검색 알고리즘 수행 과정 ] ① 처음 키 필드와 비교한다.
② 만약 같으면 검색을 종료하고 같지 않으면 다음 키 필드를 비교한다. ③ 마지막 키 필드까지 비교하여 같은 값이 없으면 원하는 데이터가 없다고 판단한다.

63 선형 탐색(Linear Search)

64 선형 탐색(Linear Search) int linear_search(int a[], int n, int key){ int i; for(i=0; i<n; i++) if( a[i] == key) return i; return -1; }

65 이진 검색(Binary Search) 이진 탐색은 정렬된 자료에 대하여 검색하는 방법이다.

66 값 22를 찾는 과정 left : 첫 번째 위치 right : 마지막 번째 위치 5 7 12 15 20 22 25 27 30 45 1 2 3 4 6 8 9 △ left ▲ right ∧ middle middle : 중간 값 middle = (left + right)/2 = (0 + 9)/2 = 9/2 = 4

67 값 22를 찾는 과정 5 7 12 15 20 22 25 27 30 45 middle = (5+9)/2 = 14/2 = 7
left : middle right : 변화없음 5 7 12 15 20 22 25 27 30 45 1 2 3 4 6 8 9 △ left ∧ middle ▲ right △ left ∧ middle middle : 중간 값 middle = (5+9)/2 = 14/2 = 7

68 값 22를 찾는 과정 22 25 27 30 45 middle = (5+6)/2 = 11/2 = 5
left : 변화 없음 right : middle-1 22 25 27 30 45 5 6 7 8 9 △ left ∧ middle ▲ right 찾고자 하는 값 발견 ▲ right ∧ middle middle : 중간 값 middle = (5+6)/2 = 11/2 = 5

69 이진 검색(Binary Search) [ 이진 검색 알고리즘 수행 과정 ] 먼저 자료가 정렬되어 있어야 한다.
① 중간 데이터((left+right)/2)를 찾는다. ② 만약 중간 데이터와 같으면 검색을 종료한다.( a[middle] == key ) ③ 만약 같지 않을 경우 ㉠ 만약 중간 데이터가 찾고자 하는 값보다 크면 중간+1부터 마지막까지 데이터 중에서 다시 중간데이터를 찾는다.( (midddle+1 + right)/2 ) ㉡ 만약 중간 데이터가 찾고자 하는 값보다 작으면 처음부터 중간-1까지 데이터 중에서 다시 중간데이터를 찾는다.( (left + middle-1)/2) ④ 찾고자 하는 값을 찾을 때까지 ③의 과정을 반복한다.

70 이진 검색(Binary Search)

71 이진 검색(Binary Search) int binary_search(int a[], int n, int key){ int left, right, middle; left = 0; right = n-1; while(left <= right){ middle = (left + right)/2; if( key > a[middle] ) left = middle +1; else if( key < a[middle] ) right = middle - 1; else return middle; } return -1;

72 2차원 배열

73 2차원 배열 정의 : 2개의 첨자를 갖는 배열 자료형 배열명[행의 수][열의 수]; 예 : int a[4][5]; 형식 0 행
자료형 배열명[행의 수][열의 수]; 예 : int a[4][5]; 0 행 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] 1 행 a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] 2 행 a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] 3 행 a[3][0] a[3][1] a[3][2] a[3][3] a[3][4] 0 열 1 열 2 열 3 열 4 열 a[0] a[1] a[2] a[3]

74 실습 1 2 3 4 5 6 7 8 9 1) 2) 1 1 3)

75 2차원 배열 int a[2][3]; a[0][0]=70; a[0][1]=33; a[0][2]=26; 2차원 배열 선언
2차원 배열에 저장

76 2차원 배열과 초기화 int a[2][3]={{70, 33, 26}, {15, 33, 88}};

77 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j, a[2][3]={3,2,7,6,9,8}; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

78 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j, a[2][3]={{3,2,7}, {6,9,8}}; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

79 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j, a[2][3]={3,2,7,6}; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

80 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j, a[2][3]={3,}; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

81 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j, a[2][3]={{3,}, {6,5,3}}; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

82 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j, a[][3]={{3,2,7}, {6,9,8}}; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

83 2차원 배열과 초기화 #include<stdio.h> int main(){ int i, j; static int a[2][3]; for(i=0; i<2; i++){ for(j=0; j<3; j++){ printf("%5d", a[i][j]); printf(“\n”); }

84 2차원 배열과 초기화 및 출력 #include <stdio.h> void main(void) { int a[2][3] = {{70, 33, 26},{15, 33, 88}}; int i, j; for(i=0; i<2; i++) { for(j=0; j<3; j++) printf("%3d", a[i][j]); printf("\n"); }

85 2차원 배열 값들의 합 #include <stdio.h> void main(void){ static int a[2][3] = {{1, 2, 3},{4, 5, 6}}; int i, j, sum=0; for(i=0; i<2; i++) for(j=0; j<3; j++) sum += a[i][j]; printf("sum=%d", sum); // 결과 출력 }

86 문제 국어 영어 수학 프밍 합계 5 6 7 8 9 1 4 2 3 합계

87 행렬 a와 b의 합과 곱 a b 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 a+b a*b

88 #include <stdio.h> void main(void) { int a[3][3] = {{1, 5, 6}, {2, 4, 7}, {2, 5, 8}}; int b[3][3] = {{7, 1, 6}, {3, 4, 7}, {4, 6, 3}}; int c[3][3] = {0,}, d[3][3], i, j, k; // 합 계산 for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) ( ) // 곱 계산 for (k = 0; k < 3; k++) // 결과 출력 printf("합\n"); for (i = 0; i < 3; i++) { printf("%3d", d[i][j]); printf("\n"); } printf("곱\n"); printf("%3d", c[i][j]);

89 문자 배열

90 대소문자 변환 배열에 문자열을 입력하고, 입력한 영문자의 대문자는 소문자로 소문자는 대문자로 변환하여라.

91 프로그램 #include <stdio.h> #include <conio.h> void main(){ char c[255]; int i = -1; clrscr(); // 화면 지우기 printf("\nInput String = "); gets(c); // 문자열 입력 while (c[++i] != '\0') { if (c[i] >= 'A' && c[i] <= 'Z') // 대문자를 소문자로 바꿈 c[i] += 32; else if (c[i] >= ‘a' && c[i] <= ‘z') c[i] -= 32; } puts(c); // 문자열 출력

92 문자열 길이 구하기 배열에 문자를 입력하고 역순으로 출력하여라.

93 프로그램 #include <stdio.h> void main(){ char c[255]; int i=0; printf("\nInput String : "); gets(c); while (c[i++] != '\0'); // 문자열의 길이를 구함 i--; while(--i >= 0) // 문자열을 역순으로 출력 printf("%c", c[i]); }