프로그래밍실습 제 17 강

강의 내용 정렬(sorting) 선택정렬(selection sort) 작은 수부터 큰 수 순으로 정렬하여 출력하는 프로그램 계산시간(CPU time)의 측정 (1) malloc의 사용 (2차원 배열) 이차원 배열은 여러 개의 일차원 배열들로 이루어진다. 포인터의 오프셋(Offset) n개의 실수를 입력받아 음수, 양수 및 이들의 개수를 출력하는 프로그램 포인터의 오프셋 (2차원 배열) realloc을 사용한 기억장소의 재할당

정렬(sorting) 아래 입출력과 같이 7개의 양의 정수를 입출력 예: 양의 정수 7개를 입력하십시오. 90 62 38 12 74 97 29 정렬된 결과: 12 29 38 62 74 90 97

선택정렬(selection sort)  12 62 38 90 74 97 29 (i=1, ind=6)  12 29 38 62 74 90 97 즉, n개의 원소를 갖는 배열의 경우 i번째 단계마다 a[i]와 그 오른쪽에 있는 원소들을 비교하여 가장 작은 원소와 a[i]를 교환한다. (i=0,1,2,...,n-2)

#include<stdio.h> #define N 7 main() { int a[N],min,ind,i,j,temp; printf("양의 정수 %d개를 입력하십시오.\n",N); for(i=0;i<N;i++) // 입력 scanf("%d",&a[i]);

for(i=0;i<N-1;i++){ // 선택정렬 min=a[i]; ind=i; for(j=i+1;j<N;j++) if(a[j]<min){// a[j]가 min보다 작으면 min=a[j]; // min을 갱신한 후 ind=j; // 첨자 j를 ind에 저장함 } temp=a[i]; // a[i]와 a[ind]와의 교환 a[i]=a[ind]; a[ind]=temp;

printf("정렬된 결과: "); // 출력 for(i=0;i<N;i++) printf("%d ",a[i]); printf("\n"); }

예: 동적 메모리 할당과 선택정렬을 이용하여 주어진 자료의 개수와 자료값을 입력하면 작은 수부터 큰 수 순으로 정렬하여 출력하는 프로그램을 작성하라. 힌트: 부함수의 내용은 아래와 같다.(선택정렬) void selection_sort(int *a, int n) { int min,ind,i,j,temp; for(i=0;i<n-1;i++){ // 선택정렬 min=a[i]; ind=i; for(j=i+1;j<n;j++) if(a[j]<min){ // a[j]가 min보다 작으면 min=a[j]; // min을 갱신한 후 ind=j; // 첨자 j를 ind에 저장함 } temp=a[i]; // a[i]와 a[ind]와의 교환 a[i]=a[ind]; a[ind]=temp;

// 주함수 #include<stdio.h> #include<stdlib.h> main() { int *a,n,i; void selection_sort(int*,int); printf("자료의 개수는? "); scanf("%d",&n); a=malloc(n*sizeof(int)); printf("%d개의 정수를 입력하십시오.\n",n); for(i=0;i<n;i++) // 입력 scanf("%d",&a[i]); selection_sort(a,n); //부함수 호출 printf("정렬된 결과: "); // 출력 for(i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); free(a); } //부함수 void selection_sort(int *a, int n) int min,ind,i,j,temp; for(i=0;i<n-1;i++){ min=a[i]; ind=i; for(j=i+1;j<n;j++) if(a[j]<min){ min=a[j]; ind=j; temp=a[i]; a[i]=a[ind]; a[ind]=temp;

입출력 예: 자료의 개수는? 7 7개의 정수를 입력하십시오. 12 38 47 89 47 74 99 정렬된 결과: 12 38 47 47 74 89 99

* 삽입정렬(insertion sort) * 선택정렬(selection sort) * 빠른정렬(quick sort) 정렬(sorting)에 대한 참고 자료 http://dasan.sejong.ac.kr/~yjcha/C/lectures/ch_08a_sort.hwp * 거품정렬(bubble sort) * 삽입정렬(insertion sort) * 선택정렬(selection sort) * 빠른정렬(quick sort)

계산시간(CPU time)의 측정 (1) #include<stdio.h> #include <time.h> //CPU time 측정을 위해서는 time.h가 필요 main() { clock_t t1,t2; //시간을 측정하는 변수로는 clock_t형을 사용 double t; //출력할 계산시간(CPU time)은 double형 double s=0; int i; t1=clock(); //시작 시점에서의 시간 측정 for(i=1;i<=10000000;i++) s+=(1./i)*(1./i); t2=clock(); //끝 시점에서의 시간 측정 t=(double)(t2-t1)/CLOCKS_PER_SEC; //t1부터 t2까지 걸린 시간 printf(“합: %f CPU time: %.3f초\n",s,t); } 출력 예: 합: 1.644934 CPU time: 0.124초

계산시간(CPU time)의 측정 (2) #include<stdio.h> #include<time.h> #include<windows.h> // Sleep 함수를 사용하기 위해 // windows.h가 필요함 main() { clock_t t1,t2; double t; t1=clock(); // 시작 시점에서의 시간 측정 Sleep(2000); // 2000ms(=2초)동안 아무 작업을 하지 않음 t2=clock(); // 끝 시점에서의 시간 측정 t=(double)(t2-t1)/CLOCKS_PER_SEC; printf("CPU time: %.3f초\n",t); } 출력: CPU time: 2.012초

malloc의 사용 (2차원 배열) 다음 프로그램의 출력을 예상해 보자. #include<stdio.h> #include<stdlib.h> main() { void sub(); int **a,i,j; a=malloc(2*sizeof(int*)); for(i=0;i<2;i++) a[i]=malloc(3*sizeof(int)); a[0][0]=1,a[0][1]=2,a[0][2]=3,a[1][0]=4,a[1][1]=5,a[1][2]=6; sub(a,2,3); for(i=0;i<2;i++){ for(j=0;j<3;j++) printf("%4d ",a[i][j]); printf("\n"); } for(i=0;i<2;i++) //기억장소 해제: 할당의 역순 free(a[i]); // free(&a[i][0]); 과 같음 free(a); // free(&a[0]); 과 같음

void sub(int **a, int m, int n) //부함수 { int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]*=a[i][j]; } 출력: 1 4 9 16 25 36 참고: 위의 C코드에서 캐스트 연산자를 사용하여 다음과 같이 수정할 수도 있다. int **a,i,j; a= (int**) malloc(2*sizeof(int*)); for(i=0;i<2;i++) a[i]= (int*) malloc(3*sizeof(int));

2차원 배열의 동적 할당에 대한 이해 앞의 예에서 2차원 배열 a[][]는 2개의 1차원 배열 a[0][]과 a[1][] 로 이루어지고, 각각의 1차원 배열은 3개의 원소로 이루어져 있다. 2차원 배열을 동적 할당 하는 경우 각 각의 1차원 배열에 속한 원소 들은 연속된 기억 장소를 사용하여 할당 되지만, 각 1차원 배열끼리 는 일반적으로 떨어져서 할당되게 된다. (일반 배열을 선언하는 경우는 상황이 전혀 다르다. 즉 int a[2][3]; 의 경우에 6개의 원소가 모두 연속된 기억 장소를 차지한다.) 동적 할당의 경우 a[0]은 a[0][0]의 주소를 저장하는 포인터 변수 이고 a[1]은 a[1][0]의 주소를 저장하는 포인터 변수이다. 즉 a[0]과 a[1]은 모두 int*형 변수이다. a는 int**형 변수이며 이 변수에는 int*형 변수 a[0]의 주소가 저장된다. 즉, a에는 &a[0]가 저장된다. 결국 a는 포인터의 포인터이다.

malloc을 사용한 이차원 배열의 동적 할당을 설명하는 그림

calloc을 사용한 이차원 배열의 동적 할당을 설명하는 그림

포인터의 오프셋(Offset) 예를 들어 배열의 이름이 a인 일차원 배열을 동적 할당한 후에 다음과 같이 하면 배열의 첨자를 1부터 사용할 수 있는데, 이를 포인터의 오프셋 이라 부른다. a--; 예: Int *a; a=calloc(3,sizeof(int)); a--; 인 경우 -------

n개의 실수를 입력 받아, 첫 째 줄에는 입력된 수 중에서 양수들을 출력하고 둘 째 줄에는 입력된 수 중에서 음수들을 출력하며 셋째 줄에는 양수 및 음수의 개수를 각각 출력하는 프로그램을 작성해 보자. (단, malloc과 포인터의 오프셋을 이용하며 자료형은 double형을 사용할 것. 또한 출력을 위한 변환 문자는 %g를 사용할 것.) 입출력 예: 자료의 개수는 몇 개입니까? 5 자료를 입력 하십시오. 2.1 -3.76 -123.569 0 33.8 양수: 2.1 33.8 음수: -3.76 -123.569 ==> 양수는 2개, 음수는 2개 입니다.

#include<stdio.h> #include<stdlib.h> main() { double *a; int i,n,pn=0,nn=0; printf("자료의 개수는 몇 개입니까? "); scanf("%d",&n); a=malloc(n*sizeof(double)); a--; //포인터의 오프셋 printf("자료를 입력 하십시오.\n"); for(i=1;i<=n;i++) scanf("%lf",&a[i]); printf("\n양수: ");

for(i=1;i<=n;i++) if(a[i]>0.){ printf("%g ",a[i]); pn++; } printf("\n음수: "); if(a[i]<0.){ nn++; printf("\n==> 양수는 %d개, 음수는 %d개 입니다.\n",pn,nn); free(&a[1]); //free의 인자로는 배열의 첫 원소의 //주소를 사용, free(a+1);과 같음

포인터의 오프셋 (2차원 배열) #include<stdio.h> #include<stdlib.h> main() { void sub(); int **a,i,j; a=malloc(2*sizeof(int *)); a--; for(i=1;i<=2;i++){ a[i]=malloc(3*sizeof(int)); a[i]--; } a[1][1]=1,a[1][2]=2,a[1][3]=3; a[2][1]=4,a[2][2]=5,a[2][3]=6; sub(a,2,3); for(j=1;j<=3;j++) printf("%4d ",a[i][j]); printf("\n");

free(&a[i][1]); //free(a[i]+1); 과 같음 free(&a[1]); //free(a+1); 과 같음 } for(i=1;i<=2;i++) free(&a[i][1]); //free(a[i]+1); 과 같음 free(&a[1]); //free(a+1); 과 같음 } void sub(int **a, int m, int n) //부함수 { int i,j; for(i=1;i<=m;i++) for(j=1;j<=n;j++) a[i][j]*=a[i][j]; 출력: 1 4 9 16 25 36

이차원 배열에 대한 동적 할당 및 포인터의 오프셋

배열의 동적 할당과 포인터의 오프셋에 대하여는 다음 자료를 참고할 것: http://dasan.sejong.ac.kr/~yjcha/c1/c_lectures/ch_09_dynamic_allocation.hwp

realloc을 사용한 기억장소의 재할당 realloc은 malloc이나 calloc으로 할당된 배열의 크기를 재조정 할 때 사용하며 stdlib.h 또는 malloc.h가 필요하다. 원래보다 더 크게 재할당 하더라도 기존에 저장된 배열 원소의 값은 모두 보존된다. 원래보다 더 작게 재할당 하는 경우에도 살아남는 배열원소의 값은 보존된다.

#include<stdio.h> #include<stdlib.h> main() { int *a,i; 예: #include<stdio.h> #include<stdlib.h> main() { int *a,i; a=malloc(10*sizeof(int)); for(i=0;i<10;i++){ a[i]=i; printf("%d ",a[i]); } printf("\n"); realloc(a,5*sizeof(int)); for(i=0;i<5;i++) realloc(a,7*sizeof(int)); a[5]=10,a[6]=20; for(i=0;i<7;i++) free(a);

출력: 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 1 2 3 4 10 20

예: 다음은 calloc 및 포인터의 오프셋을 사용한 경우에 대한 재할당 예이다. #include<stdio.h> #include<stdlib.h> main() { int *a,i; a=calloc(10,sizeof(int)); a--; for(i=1;i<=10;i++) printf("%d ",a[i]); printf("\n"); realloc(a+1,5*sizeof(int)); // a+1은 &a[1]와 같다. for(i=1;i<=5;i++) free(a+1); } 출력: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0