전산 SMP 5 주차 2015. 10. 27 김범수 bskim45@gmail.com
들어가기전에 중간고사어땠나요? 점수는?
Welcome to Array & Pointer = Hell!
지난내용복습 ~ 중간고사
자료형과형변환
연산자, 우선순위, 결합순서 산술연산자 : +,-, *, /, % 대입연산자 : =, +=, -=, *=, /=, %=, <<=, >>=, &=, ^=, = 관계 ( 비교 ) 연산자 : >, <, >=, <=,,!= 논리연산자 : &&,,! 증가 / 감소연산자 : ++, -- 비트연산자 : &,, ^, ~ 시프트연산자 : <<, >> 주소연산자 : &
조건문 (Selection Statement) 조건 (Condition) 에따라서선택적으로프로그램을진행 프로그램의 Flow 를조종 2-Way Selection if~else Multi-Way Selection if~else if~else, switch 조건문안에얼마든지또조건문을넣을수있다. (nested)
Loop ( 고리 ) pre-test loop: 검사하고실행하기 while 문, for 문 post-test loop: 실행하고검사하기 do~while 문 Requirement Initialization Update Condition Check 언제무엇을쓰나요 주로 for 는반복횟수를알때, while, do~while 은모를때
함수
메모리공간은함수마다따로따로
Call-by-Value
Call-by-Reference
SWAP
Recursion 필수조건 Base Case (n=1) n=k n=k+1? 왜쓰나요? 장점 : 문제를단순하게풀수있다 단점 : 메모리소모가많다
Limitations of Recursion Recursive solutions may involve extensive overhead because of function calls Each recursive call uses up some of memory allocation Possibly duplicate computation, but not always
Duplicate computation on Fibonacci
Tower of Hanoi void tower(int n, char source, char auxiliary, char dest); source 는시작점, auxiliary 는중간, dest 는목적지 (1) Base case: if(n==1) source destination else: tower(n-1, source, dest, auxiliary); (1) source destination; (2) tower(n-1, auxiliary, source, dest); (3) (2) (3)
I/O
FILE I/O 콘솔 (console) 화면과의소통이아닌파일 (.txt.c etc) 과소통하기위한 Steam FILE *infile; infile = fopen( text.txt, w ); ~~ fclose(infile);
대표적 FILE I/O 관련함수들 int fprintf(file * out, const char * format, ) Filestream, out 으로부터 format 의형태로출력한다. 비교 ) int printf(const char * format, ) int fscanf(file * in, const char * format, ) File stream, in 으로부터 format 의형태로입력받는다. 비교 ) int scanf(const char * format, )
FLUSH 스트림버퍼를비우는역할을한다. scanf 등입력받는함수사용시주의!! 할점!! 근접한 scanf 두번사이에는 뭔가 언짢은일들이... ex) int a; char b; scanf( %d, &a); scanf( %c,&b); printf( %d %c\n, a, b); fflush(); #define FLUSH while(getchar!= \n )
자료구조 많은데이터를예쁘게잘저장해서 쉽고빠르게꺼내쓰려고 데이터가많아지면찾는데도오래걸린다. Example: finding a number from a set of numbers How many comparisons do we need to retrieve 7?
선언, 초기화, 접근
오늘할것 String Multi-dimensional Array Sorting Search(revisit)
문자열 (string) 도결국은배열이다 char 형의배열 & 끝에널문자 \0 배열 & 포인터를완전하게배우고 string 에대해서더자세히합니다.
문자열의선언 char str[9] = Good Day ; char month[] = January ; char *pstr = Good Day ; char str[9] = { G, o, o, d,, D, a, y, \0 };
Usage char pid[100], sid[100]; printf( Input your povis id: ); scanf( %s, pid); printf( %s, pid); scanf( %s, sid); printf( %s, sid);
Usage char pid[100], sid[100]; printf( Input your povis id: ); scanf( %s, pid); printf( %s, pid); getchar(); scanf( %s, sid); printf( %s, sid);
문자열예제 입력한문자의개수구하기 대 소문자변환 대 소문자변환 단어입력받고역순으로뒤집기 회문판정 (Palindrome) 31
입력한문자의개수구하기 #include <stdio.h> int main(void) { char str[30],ch; int i=0; //scanf("%s",str); // 공백입력안됨 gets(str); while(str[i]!='\0') i++; printf("%s의문자갯수는 %d입니다.\n", str, i); } 32
대 소문자변환 #include <stdio.h> int main(void) { char str[10]; int i; scanf("%s", str); for(i=0;i<10;i++){ if(str[i]>='a' && str[i]<='z') str[i]+=32; } printf("%s\n", str); } 33
대 소문자변환 #include <stdio.h> int main(void) { char str[10]; int i; scanf("%s", str); for(i=0;i<10;i++){ if(str[i]>='a' && str[i]<='z') str[i]+=32; else if(str[i]>='a' && str[i]<='z') str[i]-=32; } printf("%s\n", str); } 34
단어입력받고역순으로뒤집기 #include <stdio.h> int main(void) { char word[100],temp; int i=0, j, k=0; scanf("%s", word); while(word[i]!= '\0') i++; for(j=0; j<(i/2); j++) { // null의위치는고정 temp = word[i-j-1]; word[i-j-1] = word[j]; word[j] = temp; } printf("%s",word); } 35
회문판정 (Palindrome) 긔엽긔는거꾸로해도긔엽긔나자꾸만꿈만꾸자나자꾸만꿈만꾸자다들잠들다수박이박수다이심전심이다아들딸이다컸다이딸들아나가다오나나오다가나통술집술통소주만병만주소 36
회문판정 (Palindrome) #include <stdio.h> #include <string.h> main() { char str[100]; scanf("%s",str); int flag=0, i; int n=strlen(str); for(i=0;i<n/2;i++) { if(str[i]!=str[n-i-1]) { flag=1; break; } } if(flag==1) printf(" 회문아님 "); else printf(" 회문맞음 "); } 37
회문판정 (Palindrome) int IsPalindrome(char *str) { } if(str 의길이가 1 보다같거나작다 ) return TRUE; if(str 앞뒤문자가다르다 ) return FALSE; return IsPalindrome(str 의앞뒤를제거한문자열 ); int CheckPalindrome(char *str, int len) { if(len <= 1) return TRUE; else return (str[0] == str[len-1] && CheckPalindrome(str+1, len-2)); } 38
Two-dimensional Array (Matrix)
Declaration int table[5][4]; int table[3][2] = {0, 1, 2, 3, 4, 5}; int table[3][2] = { {0, 1}, {2, 3}, {4, 5} }; int table[][2] = {{0, 1}, {2, 3}, {4, 5} }; int table[3][2] = {0}; table[r][w] &table[r][w]
Memory Layout
2 차원배열 #include <stdio.h> int main(void) { char arr[3][10]={"apple","orange","banana"}; char arr1[3][10]; int i,j; arr a p p l e \0 \0 \0 \0 \0 for(i=0;i<3;i++) o r a n g e \0 \0 \0 \0 scanf( %s, arr1[i]); b a n a n a \0 \0 \0 \0 arr1 for(i=0;i<3;i++) a p p l e \0 쓰 레 기 값 printf("%s\n", arr[i]); o r a n g e \0 b a n a n a \0 for(i=0;i<3;i++){ for(j=0;j<10;j++){ printf("%c", arr[i][j]); }
Multi-dimension array
Declaration int arr[2][3][4] = { { {1, 2, 3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4} }, { {1, 2, 3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4} } }; int array[][][]={ { {0,1,2}, {3,4,5}, {6,7,8} }, { {9,10,11}, {12,13,14}, {15,16,17} }, { {18,19,20}, {21,22,23}, {24,25,26} } };
Sorting
왠갑자기 Sorting Array 는자료구조 우리가원하는데이터를 Array 에서빠르게찾으려면? 저장할때잘저장해서꺼내쓸때편해야한다 데이터를효율적으로관리하는방법 데이터를저장하는자료구조 + 데이터를찾는알고리즘
Array Sorting Selection Sort Bubble Sort Insertion Sort
Selection Sort Concept
Selection Sort
Algorithm
Code
Code #2
Bubble Sort Concept
Bubble Sort Example
Bubble Sort Design
Code
Code #2
Insertion Sort Concept
Insertion Sort Example
Insertion Sort Design
Code
Code #2
Search
Searching on Array
Sequential Search Design
Sequential Search 특징 Unsorted 배열에대해서는처음부터쭉봐야하기때문에비효율적이다. Worst Case: O(n)
Code
Binary Search Unsuccessful Binary Search Example
Binary Search Design
Binary Search 특징 검색대상배열은 sorted 인상태여야한다. 정렬된데이터에대해서는이진검색이빠르다 매 iteration 에서반틈 (1/2) 을서치후보에서제외시킨다.( 제외된거는볼필요없음 ) O(logn)
Code
Efficiency Best Average Worst Selection n 2 n 2 n 2 Bubble n n 2 n 2 Insertion n n 2 n 2
Search Efficiency Sequential O(n) vs Binary O(logn)
O(n) vs O(log 2 n)
Functions Graphed Using Normal Scale f(n) = 1 f(n) = n lg n f(n) = 2 n f(n) = lg n f(n) = n 2 f(n) = n f(n) = n 3
동영상하나보고갑시다 http://youtu.be/kpra0w1kecg
다음시간 Pointer, 그리고 Array 와의관계 Pointer Application