동적배열 배열을위한메모리할당방법 지역변수로자동할당 int score[100]; score[10] = 123; 지역변수로배열을생성하는경우, 크기에제한이있음 동적배열 동적메모리할당 int *score; score = (int *) malloc(100*sizeof(int)); score[10] = 123; 동적메모리할당으로배열을생성하는경우, 더큰배열을사용할수있음 6-35
동적 (dynamic) 메모리할당, 동적배열생성 동적메모리할당 실행도중에동적으로메모리를할당받는것 사용이끝나면시스템에메모리를반납 int score[100]; // 정적배열대신, score = (int *) malloc(100*sizeof(int)); 로동적으로메모리를할당하여, 배열로사용할수있음 필요한만큼만할당을받고메모리를매우효율적으로사용 malloc() 계열의라이브러리함수를사용 운영체제 할당요구 #include #include <stdio.h> <stdio.h> #include #include <stdlib.h> <stdlib.h> int int main(void) main(void) int int *p; *p; p = (int (int *)malloc( *)malloc( sizeof(int) sizeof(int) ); );...... 프로그램 6-36
동적메모리할당예제 #include <stdio.h> #include <stdlib.h> int main(void) int *score; int i; score = (int *)malloc( 100*sizeof(int) ); if( p == NULL ) // 반환값이 NULL인지검사 printf(" 동적메모리할당오류 \n"); exit(1); for(i=0 ; i<100 ; i++) score[i] = 0; free(p); return 0; 동적메모리할당 동적메모리해제 6-37
void *malloc(size_t size) 동적메모리할당 size는바이트의수 malloc() 함수는메모리블럭의첫번째바이트에대한주소를반환 만약요청한메모리공간을할당할수없는경우에는 NULL값을반환 int *score; score = (int *)malloc(100*sizeof(int)); if( score == NULL )... // 오류처리 score????? 6-38
void free(void *ptr) 동적메모리반납 free() 는동적으로할당되었던메모리블록을시스템에반납 ptr은 malloc() 을이용하여동적할당된메모리를가리키는포인터 int *score; score = (int *)malloc(100*sizeof(int)); free(score); score????? 6-39
정렬 (sorting) 이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 6-40
정렬이란? 정렬은자료탐색에있어서필수적이다. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 6-41
선택정렬 (selection sort) 선택정렬 (selection sort): 정렬이안된숫자들중에서최소값을선택하여배열의첫번째요소와교환 6-42
선택정렬 (selection sort) 선택정렬 (selection sort): 정렬이안된숫자들중에서최소값을선택하여배열의첫번째요소와교환 몇개의단계만살펴보자. 5 3 8 1 2 7 6-43
선택정렬 #include <stdio.h> #define SIZE 10 int main(void) int list[size] = 3, 2, 9, 7, 1, 4, 8, 0, 6, 5 ; int i, j, temp, least; for(i = 0; i < SIZE-1; i++) least = i; for(j = i + 1; j < SIZE; j++) if(list[j] < list[least]) least = j; temp = list[i]; list[i] = list[least]; list[least] = temp; 내부 for 루프로서 (i+1) 번째원소부터배열의마지막원소중에서최소값을찾는다. 현재의최소값과비교하여더작은정수가발견되면그정수가들어있는인덱스를 least 에저장한다. 0 1 2 3 4 5 6 7 8 9 for(i = 0;i < SIZE; i++) printf("%d ", list[i]); printf("\n"); return 0; list[i] 와 list[least] 를서로교환 6-44
다음과같이하면안됨 변수의값을서로교환할때 grade[i] = grade[least]; // grade[i] 의기존값은파괴된다! grade[least] = grade[i]; 올바른방법 temp = list[i]; list[i] = list[least]; list[least] = temp; 6-45
Divide and Conquer Quick Sorting Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. Steps in Quick Sort Pick an element, called a pivot, from the list. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. 6-46
In-place version of QuickSorting // left is the index of the leftmost element of the array // right is the index of the rightmost element of the array // (inclusive) number of elements in subarray: right-left+1 int partition(array[], left, right, pivotindex) pivotvalue = array[pivotindex]; swap array[pivotindex] and array[right] // Move pivot to end storeindex = left; for (i = left; i<= right 1; i++) // left i< right if (array[i] pivotvalue) swap array[i] and array[storeindex]; storeindex = storeindex + 1; swap array[storeindex] and array[right]; // Move pivot to its final place return storeindex; Yeungnam University (yuantl) 6-47
function quicksort(array, left, right) if (left >= right) return; else if (left < right) // subarray of 0 or 1 elements already sorted select a pi (pivotindex) in the range left pi right // e.g.) (left + right)/2 newpi = partition(array, left, right, pi); // element at newpivotindex (newpi) is now at its final position if (left < (newpi-1)) quicksort(array, left, newpi - 1); // recursively sort elements on the left of pivotnewindex if ((newpi+1) < right) quicksort(array, newpi + 1, right); // recursively sort elements on the right of pivotnewindex 6-48
Quick Sort Algorithm (1) Level 0 left (=0) pi(pivotindex) =6 right (=12) 13 7 5 8 12 10 6 9 2 4 11 1 3 13 7 5 8 12 10 6 9 2 4 11 1 3 In partition function pi (pivot index ) = 6 pivotvalue(pv) = 6 Swap a[pi=6], a[right=12] si (storeindex) = 0 13 7 5 8 12 10 3 9 2 4 11 1 6 6-49
Level 0 (pv = 6) Quick Sort Algorithm (2) left (=0) right (=12) 13 7 5 8 12 10 3 9 2 4 11 1 6 si (=0) i(=0) 13 7 5 8 12 10 3 9 2 4 11 1 6 si (=0) i(=1) i(=2) If (a[i] <= pv) swap a[i] and a[si]; si += 1; 6-50
Quick Sort Algorithm (3) Level 0 5 7 13 8 12 10 3 9 2 4 11 1 6 si (=1) i(=2)i(=3)i(=4)i(=5) i(=6) 5 3 13 8 12 10 7 9 2 4 11 1 6 si (=2) i(=7) i(=8) 5 3 2 8 12 10 7 9 13 4 11 1 6 si (=3) i(=9) 6-51
Level 0 si = 4, i = 9 Quick Sort Algorithm (4) 5 3 2 4 12 10 7 9 13 8 11 1 6 si = 5, i = 11, swap(a[5], a[right]) 5 3 2 4 1 10 7 9 13 8 11 12 6 return storeindex (si = 5) 5 3 2 4 1 6 7 9 13 8 11 12 10 6-52
Overall Process (1) QS(A[], 0, 12) pi = (0+12)/2 = 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 5 8 12 10 6 9 2 4 11 1 3 0 1 2 3 4 5 6 7 8 9 10 11 12 partition(a[], 0, 12, 6) newpi = 5 5 3 2 4 1 6 7 9 13 8 11 12 10 0 1 2 3 4 5 6 7 8 9 10 11 12 QS(A[], 0, 4) pi = (0+4)/2 = 2 partition(a[], 0, 4, 2) newpi = 1 5 3 2 4 1 6 7 9 13 8 11 12 10 0 1 2 3 4 5 6 7 8 9 10 11 12 1 2 5 4 3 6 7 9 13 8 11 12 10 0 1 2 3 4 5 6 7 8 9 10 11 12 QS(A[], 2, 4) pi = (2+4)/2 = 3 partition(a[], 2, 4, 3) newpi = 3 1 2 5 4 3 6 7 9 13 8 11 12 10 0 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 9 13 8 11 12 10 6-53
Overall Process (2) 0 1 2 3 4 5 6 7 8 9 10 11 12 QS(A[], 6, 12) pi = (6+12)/2 = 9 1 2 3 4 5 6 7 9 13 8 11 12 10 partition(a[], 6, 12, 9) newpi = 7 0 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 13 10 11 12 9 QS(A[], 8, 12) pi = (8+12)/2=10 0 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 13 10 11 12 9 0 1 2 3 4 5 6 7 8 9 10 11 12 partition(a[], 8, 12, 10) newpi = 10 1 2 3 4 5 6 7 8 10 9 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 QS(A[], 8, 9) pi = (8+9)/2 = 8 1 2 3 4 5 6 7 8 10 9 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 partition(a[], 8, 9, 8) newpi = 9 1 2 3 4 5 6 7 8 9 10 11 12 13 6-54
Overall Process (3) 0 1 2 3 4 5 6 7 8 9 10 11 12 QS(A[], 11, 12) pi = (11+12)/2 = 11 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 partition(a[], 8, 9, 11) newpi = 11 1 2 3 4 5 6 7 8 9 10 11 12 13 6-55
Comparisons of Sorting Algorithms Selection sorting comparisons to find the maximum or minimum element at each inner loop only 1 swap in each inner loop no more memory requirements Quick sorting divide and conquer comparisons and swapping at each stage the number of elements for each stage is divided, recursively over head in function call: more memory requirements 6-56
순차탐색 (Sequential Search) 순차탐색은배열의원소를순서대로하나씩꺼내서탐색키와비교하여원하는값을찾아가는방법 비교 50 성공 10 20 30 40 50 10 grade[0] grade[1] grade[2] grade[3] grade[4] grade[5] 6-57
순차탐색 #include <stdio.h> #define SIZE 10 int main(void) int key, i; int list[size] = 1, 2, 3, 4, 5, 6, 7, 8, 9 ; printf(" 탐색할값을입력하시오 :"); scanf("%d", &key); for 루프를이용하여 list[i] 와 key 를비교하는연산을배열의크기만큼반복한다. 만약 list[i] 와 key 가같으면탐색은성공되고키값이발견된배열의인덱스를출력한다. for(i = 0; i < SIZE; i++) if(list[i] == key) 탐색할값을입력하시탐색성공인덱스 = 탐색종료 printf(" 탐색성공인덱스 = %d\n", i); printf(" 탐색종료 \n"); return 0; 6-58
이진탐색 (binary search) 이진탐색 (binary search): 정렬된배열의중앙에위치한원소와비교되풀이 6-59
이진탐색 #include <stdio.h> #define SIZE 16 int binary_search(int list[], int n, int key); int main(void) int key; int grade[size] = 2,6,11,13,18,20,22,27,29,30,34,38,41,42,45,47 ; printf(" 탐색할값을입력하시오 :"); scanf("%d", &key); printf(" 탐색결과 = %d n", binary_search(grade, SIZE, key)); return 0; 6-60
이진탐색 int binary_search(int list[], int n, int key) int low, high, middle; low = 0; high = n-1; while( low <= high ) // 아직숫자들이남아있으면 printf("[%d %d]\n", low, high); // 하한과상한을출력한다. middle = (low + high)/2; // 중간위치를계산한다. if( key == list[middle] ) // 일치하면탐색성공 return middle; else if( key > list[middle] )// 중간원소보다크다면 low = middle + 1; // 새로운값으로 low 설정 else high = middle - 1; // 새로운값으로 high 설정 return -1; 6-61
실행결과 탐색할값을입력하시오 :34 [0 15] [8 15] [8 10] [10 10] 탐색결과 = 10 6-62
순차탐색과이진탐색의비교 N 개의원소를가진배열에서지정된값을탐색하기위한비교 (comparison) 회수 순차탐색 최소 : 1 ( 첫번째원소가탐색대상일경우 ) 최대 : N ( 마지막원소가탐색대상일경우 ) 평균 : N/2 이진탐색 최소 : 1 ( 첫번째 pivot 위치의원소가탐색대상일경우 ) 최대 : log 2 N ( 마지막레벨의 pivot 원소가탐색대상일경우 ) 예 : 1000 개의원소를가진배열에서지정된값탐색 순차탐색 : 평균 500 회비교 이진탐색 : 최대 10 회비교 6-63
int s[10]; // 1차원배열 int s[3][10]; // 2차원배열 int s[5][3][10]; // 3차원배열 2 차원배열 6-64
2 차원배열의구현 2 차원배열은 1 차원적으로구현된다. 6-65
#include <stdio.h> 2 차원배열의활용 int main(void) int s[3][5]; int i, j; int value = 0; // 2차원배열선언 // 2개의인덱스변수 // 배열원소에저장되는값 for(i=0;i<3;i++) for(j=0;j<5;j++) s[i][j] = value++; for(i=0;i<3;i++) for(j=0;j<5;j++) printf("%d\n", s[i][j]); return 0; 0 1 2 3... 11 12 13 14 6-66
2 차원배열의초기화 int s[3][5] = 0, 1, 2, 3, 4, // 첫번째행의원소들의초기값 10, 11, 12, 13, 14, // 두번째행의원소들의초기값 20, 21, 22, 23, 24 // 세번째행의원소들의초기값 ; 6-67
2 차원배열의초기화 int s[ ][5] = 0, 1, 2, 3, 4, // 첫번째행의원소들의초기값 10, 11, 12, 13, 14, // 두번째행의원소들의초기값 20, 21, 22, 23, 24, // 세번째행의원소들의초기값 ; 6-68
2 차원배열의초기화 int s[ ][5] = 0, 1, 2, // 첫번째행의원소들의초기값 10, 11, 12, // 두번째행의원소들의초기값 20, 21, 22 // 세번째행의원소들의초기값 ; 6-69
2 차원배열의초기화 int s[ ][5] = 0, 1, 2, 3, 4, // 첫번째행의원소들의초기값 5, 6, 7, 8, 9, // 두번째행의원소들의초기값 ; 6-70
3 차원배열 #include <stdio.h> int main(void) int s[3][3][3]; int x, y, z; int i= 1; // 3차원배열선언 // 3개의인덱스변수 // 배열원소에저장되는값 for(z=0;z<3;z++) for(y=0;y<3;y++) for(x=0;x<3;x++) s[z][y][x] = i++; return 0; 6-71
다차원배열인수 #include <stdio.h> #define YEARS 3 #define PRODUCTS 5 총매출은 45 입니다. int sum(int grade[][products]); int main(void) int sales[years][products] = 1, 2, 3, 4, 5, 6, 7, 8, 9 ; int total_sale; total_sale = sum(sales); printf(" 총매출은 %d입니다.\n", total_sale); return 0; int sum(int grade[][products]) int y, p; int total = 0; for(y = 0; y < YEARS; y++) for(p = 0; p < PRODUCTS; p++) total += grade[y][p]; return total; 6-72 첫번째인덱스의크기는적지않아도된다.
#include <stdio.h> #define CLASSES 3 #define STUDENTS 5 다차원배열예제 학급 0 의평균성적 = 2 학급 1 의평균성적 = 12 학급 2 의평균성적 = 22 전체학생들의평균성적 = 12 int main(void) int s[classes][students] = 0, 1, 2, 3, 4, // 첫번째행의원소들의초기값 10, 11, 12, 13, 14, // 두번째행의원소들의초기값 20, 21, 22, 23, 24, // 세번째행의원소들의초기값 ; int clas, student, total, subtotal; total = 0; for(clas = 0; clas < CLASSES; clas++) subtotal = 0; for(student = 0; student < STUDENTS; student++) subtotal += s[clas][student]; printf(" 학급 %d 의평균성적 = %d\n", clas, subtotal / STUDENTS); total += subtotal; printf(" 전체학생들의평균성적 = %d\n", total/(classes * STUDENTS)); return 0; 6-73
행렬 (Matrix) 행렬 (matrix) 는자연과학에서많은문제를해결하는데사용 6-74
2 차원배열을이용한행렬의표현 #include <stdio.h> #define ROWS 3 #define COLS 3 int main(void) int A[ROWS][COLS] = 2,3,0, 8,9,1, 7,0,5 ; int B[ROWS][COLS] = 1,0,0, 1,0,0, 1,0,0 ; int C[ROWS][COLS]; int r,c; // 두개의행렬을더한다. for(r = 0;r < ROWS; r++) for(c = 0;c < COLS; c++) C[r][c] = A[r][c] + B[r][c]; // 행렬을출력한다. for(r = 0;r < ROWS; r++) for(c = 0;c < COLS; c++) printf("%d ", C[r][c]); printf("\n"); return 0; Yeungnam University (yuantl) 6-75 중첩 for 루프를이용하여행렬 A 의각원소들과행렬의 B 의각원소들을서로더하여행렬 C 에대입한다. 3 3 0 9 9 1 8 0 5
4x4 행렬의초기화 (1) /** * matrix4_4.cpp * programmed by Young-Tak Kim (August 10, 2011) * */ #include <iostream> #include <iomanip> using namespace std; #define SIZE_4 4 void printmtrx(int ma[][size_4], int size_n); void addmtrx(int ma[][size_4], int mb[][size_4], int mx[][size_4],int size_n); void subtractmtrx(int ma[][size_4], int mb[][size_4], int mx[][size_4], int size_n); void multiplymtrx(int ma[][size_4], int mb[][size_4], int mx[][size_4], int size_n); int main() int ma[4][4] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16; int mb[4][4] = 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 4; int mc[4][4]; int md[4][4]; int me[4][4]; 6-76
4x4 행렬의초기화 (2) /** matrix4_4.cpp (cont.) */ printf(" n Matrix ma: n"); printmtrx(ma, 4); printf(" n Matrix mb: n"); printmtrx(mb, 4); addmtrx(ma, mb, mc, 4); printf(" n Matrix mc = ma + mb: n"); printmtrx(mc, 4); subtractmtrx(ma, mb, md, 4); printf(" n Matrix md = ma - mb: n"); printmtrx(md, 4); multiplymtrx(ma, mb, me, 4); printf(" n Matrix me = ma x mb: n"); printmtrx(me, 4); printf(" n"); return 0; 6-77
확장완성형코드를사용한 4x4 행렬의출력 void printmtrx(int ma[][size_4], int size_n) unsigned char a6 = 0xA6, a1 = 0xA1, a2 = 0xA2; unsigned char a3 = 0xA3, a4 = 0xA4, a5 = 0xA5; for (int i=0; i< size_n; i++) for (int j=0; j< size_n; j++) if ((i==0) && (j==0)) printf("%c%c%3d", a6, a3, ma[i][j]); else if ((i==0) && j==(size_n -1)) printf("%3d%c%c", ma[i][j], a6, a4); else if ((i>0) && (i<size_n-1) && (j==0)) printf("%c%c%3d", a6, a2, ma[i][j]); else if ((i>0) && (i<size_n-1) && (j== (size_n -1))) printf("%3d%c%c", ma[i][j], a6, a2); else if ((i==(size_n-1)) && (j==0)) printf("%c%c%3d", a6, a6, ma[i][j]); else if ((i==(size_n-1)) && (j==(size_n -1))) printf("%3d%c%c", ma[i][j], a6, a5); else printf("%3d", ma[i][j]); printf(" n"); 6-78
4x4 행렬의덧셈, 뺄셈, 곱셈 void addmtrx(int ma[][size_4], int mb[][size_4], int mx[][size_4], int size_n) for (int i=0; i<size_n; i++) for (int j=0; j<size_n; j++) mx[i][j] = ma[i][j] + mb[i][j]; void subtractmtrx(int ma[][size_4], int mb[][size_4], int mx[][size_4], int size_n) for (int i=0; i<size_n; i++) for (int j=0; j<size_n; j++) mx[i][j] = ma[i][j] - mb[i][j]; void multiplymtrx(int ma[][size_4], int mb[][size_4], int mx[][size_4], int size_n) for (int i=0; i<size_n; i++) for (int j=0; j<size_n; j++) mx[i][j] = 0; for (int k=0; k<size_n; k++) mx[i][j] += ma[i][k] * mb[k][j]; 6-79
실행결과 6-80
Homework 6 6.1 5 x 5 Matrix 계산프로그램 (1) 입력데이터가포함된입력파일 (exam1_input.txt) 과출력결과를저장할출력데이터파일 (exam1_output.txt) 을 fopen() 을사용하여 open 또는생성하라. 입력데이터파일에는 2개의 5 x 5 행렬을위한총 50개의정수형데이터가포함되어있도록구성할것. (2) 2개의 5x 5 행렬을저장할수있는 2차원배열 (ma[size][ SIZE] 및 mb[size][ SIZE]) 을준비하고, 입력데이터파일 (exam1_input.txt) 로부터 fscanf() 함수를사용하여, 각 25개씩의정수데이터를읽어 2차원배열을초기화하는프로그램 initmtrx(int M[][SIZE], int size) 을작성할것. (3) 입력된 2개의행렬의값을화면에출력하기위한 printmtrx(int M[][SIZE], int size) 함수와출력데이터파일 (exam1_output.txt) 에출력하기위한 fprintmtrx(file* fout, int M[][SIZE], int size) 함수를각각작성할것. 행렬의각값은최소5자리를확보하고, 오른쪽정렬로출력되도록할것. 이때, 행렬을표시하기위하여, 확장완성형코드를사용할것. 출력결과 확장완성형코드 사용방법 0xa6, 0xa1 printf( %c%c, 0xa6, 0xa1) 0xa6, 0xa2 printf( %c%c, 0xa6, 0xa2) 0xa6, 0xa3 printf( %c%c, 0xa6, 0xa3) 0xa6, 0xa4 printf( %c%c, 0xa6, 0xa4) 0xa6, 0xa5 printf( %c%c, 0xa6, 0xa5) Advanced Networking 0xa6, Tech. 0xa6 Lab. printf( %c%c, 0xa6, 0xa6) 6-81