제 1 장 기본 개념 - PDF Free Download

시스템생명주기 (System Life Cycle) 요구사항 (requirement) - 프로젝트들의목적을정의한명세들의집합 - 입력과출력에관한정보를기술 분석 (analysis) - 문제들을다룰수있는작은단위들로나눔 - 상향식 (bottom-up)/ 하향식 (top-down) 접근방법 설계 (design) - 추상데이타타입 (abstract data type) 생성 - 알고리즘명세와설계기법고려 Copyright 2007 DBLAB, Seoul National University 2

시스템생명주기 (System Life Cycle) 정제와코딩 (refinement and coding) - 데이타객체에대한표현선택 - 수행되는연산에대한알고리즘작성 검증 (verification) - 정확성증명 (correctness proof) 수학적기법들을이용해서증명 - 테스트 (testing) 프로그램의정확한수행검증 프로그램의성능검사 - 오류제거 (error removal) 독립적단위로테스트후전체시스템으로통합 Copyright 2007 DBLAB, Seoul National University 3

알고리즘적분해와객체지향적분해 알고리즘적분해 ( 함수적분해 ) - 고전적프로그래밍기법 - 소프트웨어를기능적모듈로분해 - Pascal 의프로시저, FORTRAN 의서브프로그램, C 의함수 객체지향적분해 - 응용분야의개체를모델링하는객체의집합 - 소프트웨어의재사용성조장 - 변화에유연한소프트웨어시스템 - 직관적 Copyright 2007 DBLAB, Seoul National University 5

객체지향프로그래밍의기본정의와개념 객체 (object) - 계산을수행하고상태를갖는개체 - 데이타 + 절차적요소 객체지향프로그래밍 (object-oriented programming) - 객체는기본적인구성단위 (building block) - 각객체는어떤타입 ( 클래스 ) 의인스턴스 (instance) - 클래스는상속 (inheritance) 관계로연관됨 객체지향언어 (object-oriented language) - 객체지원 - 모든객체는클래스에속함 - 상속지원 객체기반언어 (object-based language) - 객체와클래스는지원하되상속은지원하지않는언어 Copyright 2007 DBLAB, Seoul National University 6

프로그래밍언어의발전과 C++ 의역사 고급프로그래밍언어 - 1 세대언어 - FORTRAN 수식계산가능 - 2 세대언어 - Pascal, C 알고리즘을효과적으로표현 - 3 세대언어 - Modula 추상데이타타입개념도입 - 4 세대언어 ( 객체지향언어 ) - Smalltalk, Objective-C, C++ 상속기능지원 C 의장점 - 효율성 (efficient) : 하드웨어를직접제어할수있는기능 - 유연성 (flexible) : 대부분의응용분야에사용가능 - 가용성 (available) : 모든컴퓨터에 C 컴파일러존재 Copyright 2007 DBLAB, Seoul National University 7

데이타추상화와캡슐화 데이타캡슐화 (data encapsulation) - 정보은닉 (information hiding) - 외부로부터데이타객체의자세한구현을은닉 데이타추상화 (data abstraction) - 객체의명세 (specification) 와구현 (implementation) 을분리 - 무엇 (what) 과어떻게 (how) 를명확하게구분 Copyright 2007 DBLAB, Seoul National University 8

데이타타입 데이타타입 (data type) - 객체 (object) 들과이객체들에대한연산 (operation) 의집합 C++ 의데이타타입 - 기본데이타타입 Char, int, float, double 등 타입수식어 : short, long, signed, unsigned - 파생데이타타입 포인터 (pointer) 타입, 참조 (reference) 타입 - 데이타를묶어주는구조 배열 (array), 구조 (struct), 클래스 (class) - 사용자정의데이타타입 추상데이타타입 (abstract data type; ADT) - 객체와연산에대한명세가객체의표현과연산의구현으로부터분리된방식으로구성된데이타타입 Copyright 2007 DBLAB, Seoul National University 9

데이타추상화와데이타캡슐화의장점 소프트웨어개발의간소화 - 복잡한작업을부분작업들로분해 테스트와디버깅 - 각부분작업을독자적으로테스팅, 디버깅 재사용성 - 자료구조에대한코드와연산을추출해서다른소프트웨어시스템에서도사용 데이타타입의표현에대한수정 - 데이타타입의내부구현에직접접근하는연산들만수정 Copyright 2007 DBLAB, Seoul National University 10

C++ 의기초 C++ 프로그램의구성 - 헤더화일.h 접미사 선언저장에사용 시스템 / 사용자정의화일 전처리기명령 #include 를사용하여화일에포함시킴 - 소스화일.C 접미사 소스코드저장에사용 프로그램의실행 - 컴파일 링크 적재 헤더화일중복방지 #ifdef FILENAME_H #define FILENAME_H // 헤더화일내용삽입... #endif Copyright 2007 DBLAB, Seoul National University 12

C++ 에서의영역 화일영역 - 함수정의에속하지않은선언, 클래스정의, 네임스페이스 네임스페이스영역 - 네임스페이스 (namespace) 논리적으로연관된변수나함수를한그룹으로만드는기법 - 영역정보를사용해서네임스페이스안의개체에접근 예 ) std::cout 지역영역 - 블록안에서선언된이름 클래스영역 - 클래스정의에관련된선언 Copyright 2007 DBLAB, Seoul National University 13

C++ 명령문과연산자 C++ 명령문 - C 와같은문법과의미 C++ 연산자 - new, delete 제외하고 C 의연산자와동일 C++ 의입출력 - 왼편 / 오른편시프트연산자 (<<, >>) 사용 C 와 C++ 의중요한차이점 - 연산자다중화 (operator overloading) 허용 Copyright 2007 DBLAB, Seoul National University 14

C++ 데이타선언 데이타선언 : 한데이타타입을어떤이름에연결 - 상수값 - 변수 : 데이타타입의인스턴스 - 상수변수 : 선언시에내용이고정 const int MAX=500; - 열거타입 : 일련의정수상수를선언 enum semester{summer, FALL, SPRING}; - 포인터 : 객체의메모리주소저장 int i=25; int *np; np = &i; - 참조타입 : 객체에대한또다른이름을제공 int i=5; int& j=i; i=7; printf( i=%d, j=%d, i, j); i=7, j=7 Copyright 2007 DBLAB, Seoul National University 15

C++ 에서의입출력 (1) 시스템정의헤더화일 iostream 이필요 cout - 표준출력장치로출력 - << 연산자는 cout 키워드와출력될개체를구분 #include <iostream> main() { int n=50; float f=20.3; cout<<"n:"<<n<<endl; cout<<"f:"<<f<<endl; } 출력 : n:50 f:20.3 Copyright 2007 DBLAB, Seoul National University 17

C++ 에서의입출력 (2) cin - 입력을위해사용 - >> 연산자는입력될변수들을구분 - 여백문자로입력값을구분 #include <iostream> main(){ int a,b; cin>>a>>b; } 입력 1: 5 10 <Enter> 입력 2: 5 <Enter> 10 <Enter> Copyright 2007 DBLAB, Seoul National University 18

C++ 에서의입출력 (3) C++ 에서의입출력의장점 - 자유형식 : 포맷기호불필요 - 입출력연산자도다중화가능 화일입출력 - 헤더화일 fstream 필요 #include <iostream> #include <fstream> main(){ ofstream outfile("my.out", ios::out); if (!outfile){ cerr << "cannot open my.out" << endl; // 표준오류장치 return; } int n = 50; float f = 20.3; outfile << "n: " << n << endl; outfile << "f: " << f << endl; } Copyright 2007 DBLAB, Seoul National University 19

C++ 의함수 정규함수 멤버함수 : 특정클래스와연관된함수 함수의구성 - 함수이름 - 인자리스트 ( 시그너처 ( 입력 )) - 반환타입 ( 출력 ) - 몸체 ( 함수를구현한코드 ) int Max(int a, int b){ if (a > b) return a; else return b; } Max : 함수이름 int a, int b : 인자리스트 int : 반환타입 { 와 } 사이 : 함수몸체 Copyright 2007 DBLAB, Seoul National University 20

C++ 의매개변수전달 값 (value) 에의한전달 - 전달된객체는그함수의지역저장소에복사 - 실인자에영향을주지않음 - 실인자로제공되는변수가함수에의해변경되지않음 참조 (reference) 에의한전달 - 인자리스트의타입명세자에 & 첨가 - 전달된객체의주소만함수의지역저장소에복사 - 실인자에접근 - 전달된객체가큰메모리를요구하는경우더빨리수행 상수참조 (constant reference) - 인자변경불가 const T& a 배열은참조로전달 Copyright 2007 DBLAB, Seoul National University 21

C++ 의함수이름다중화 함수다중화 (function overloading) - 함수의시그너처 ( 인자리스트 ) 가다르기만하면같은이름을가진함수가둘이상존재할수있음 - e.g. int Max(int, int); int Max(int, int, int); int Max(int*, int); int Max(float, int); int Max(int, float); Copyright 2007 DBLAB, Seoul National University 22

C++ 에서의동적메모리할당 new / delete 연산자 - 실행시간에자유저장소를할당받거나반환 new 연산자 - 원하는타입의객체를생성하고그에대한포인터를반환 - 생성할수없으면예외발생 delete 연산자 - new 로생성된객체에게할당된기억장소를반환 e.g. int *ip = new int;.. delete ip; int *jp = new int[10]; //jp 는정수배열.. delete [] jp; Copyright 2007 DBLAB, Seoul National University 24

예외발생 오류와다른특별한조건이발생했음을알리는데사용 다양한예외각각에대해예외클래스를정의 e.g int DivZero(int a, int b, int c) { if (a <= 0 b <= 0 c <= 0) throw "All parameters should be >0 ; return a + b * c + b / c; } Copyright 2007 DBLAB, Seoul National University 25

알고리즘명세 알고리즘 (algorithm) - 특정작업을수행하는명령어들의유한집합 알고리즘의요건 - 입력 : 외부에서제공되는데이타가 0 개이상 - 출력 : 적어도한개이상의결과생성 - 명확성 : 각명령은명확하고모호하지않아야함 - 유한성 : 알고리즘대로수행하면어떤경우에도반드시종료 - 유효성 : 반드시실행가능해야함 알고리즘기술방법 - 자연어 - 흐름도 (flowchart) - C++ 언어 Copyright 2007 DBLAB, Seoul National University 27

선택정렬 n 1 개의서로다른정수의집합을정렬 - 정렬되지않은정수들중에서가장작은값을찾아서정렬된리스트다음자리에놓는다 for (int i = 0; i < n; i++) [ a[i] 에서부터 a[n-1] 까지의정수값을검사한결과 a[j] 가가장작은값 a[i] 와 a[j] 를서로교환 ; } 1 void SelectionSort(int *a, const int n) 2 {// n 개의정수 a[0] 부터 a[n-1] 까지비감소순으로정렬한다. 3 for (int i = 0; i < n; i++) 4 { 5 int j = i; 6 // a[i] 와 a[n-1] 사이에가장작은정수를찾는다. 7 for (int k = i + 1; k < n; k++) 8 if (a[k] < a[j]) j = k; 9 swap(a[i], a[j]) 10 } 11 } Copyright 2007 DBLAB, Seoul National University 28

선택정렬의정확성증명 정리 1.1 - 함수 SelectionSort(a, n) 는 n 1 개의정수를정확하게정렬한다. 그결과는 a[0],..., a[n-1] 로되고여기서 a[0] a[1]... a[n-1] 이다. 증명 - i=q 에대해, 외부 for 가수행되면 a[q] a[r], q < r n-1 이된다. - i>q 이면 a[0] 에서 a[q] 가변하지않는다. - 따라서 for 를마지막으로수행하면 ( 즉, i=n-1), a[0] a[1]... a[n-1] 가된다. Copyright 2007 DBLAB, Seoul National University 29

이원탐색 이미정렬된배열 a[0]...a[n-1] 에서 x = a[j] 인 j 를반환 - left, right: 탐색하고자하는리스트의왼쪽, 오른쪽끝 - 초기값으로 left = 0, right = n-1 - 리스트의중간위치 middle = (left + right) / 2 로설정 - a[middle] 과 x 비교 ⑴ x < a[middle] right = middle-1 ⑵ x = a[middle] middle 반환 ⑶ x > a[middle] left = middle+1 Copyright 2007 DBLAB, Seoul National University 30

순환알고리즘 수행이완료되기전에자기자신을다시호출 - 직접순환 (direct recursion) : 함수가그수행이완료되기전에자기자신을다시호출 - 간접순환 (indirect recursion) : 호출함수를다시호출하게되어있는다른함수를호출 순환알고리즘기술방법 1. 주어진입력에대해함수가마땅히수행해야할작업에대한명령문구성 2. 자신에대한순환적호출이제대로이루어질때목적을달성할수있는지검증 3. 함수를유한한횟수로순환호출하면완료조건을만족시키는지확인 4. 완료조건을만족시켰을때함수가올바른계산을하는지확인 Copyright 2007 DBLAB, Seoul National University 31

순환이원탐색 BinarySearch(a, x, 0, n-1) int BinarySearch(int *a, const int x, const int left, const int right) {// 정렬된배열 a[left],..., a[right] 에서 x 탐색 if(left <= right){ int middle = (left + right) /2; if(x < a[middle]) return BinarySearch(a, x, left, middle-1); else if(x > a[middle]) return BinarySearch(a, x, middle+1, right); return middle; }//if 의끝 return -1;// 발견되지않음 } Copyright 2007 DBLAB, Seoul National University 32

순열생성기 주어진집합의모든가능한순열출력 Permutations(a,0,n-1) void Permutations(char *a, const int k, const int m) {// a[k],..., a[m] 에대한모든순열생성 if(k == m){// 순열을출력 for (int i = 0 ; i <= m; i++) cout << a[i] << ; cout << endl; } else {//a[k:m] 에는하나이상의순열이있다. 이순열을순환적으로생성 for(i=k;i<=m;i++){ swap(a[k], a[i]); Permutations(a, k+1, m); swap(a[k], a[i]); } } } Copyright 2007 DBLAB, Seoul National University 33

표준템플릿라이브러리 표준템플릿라이브러리 (STL:standard templates library) - 컨테이너 (container) - 어댑터 (adapter) - 반복자 (iterator) - 함수객체 (function) - 알고리즘 - #include<algorithm> 첨가 Copyright 2007 DBLAB, Seoul National University 34

accumulate STL 알고리즘 순차에있는원소들을합산 accumulate(start, end, initialvalue) - accumulate(a, a+n, initialvalue) initialvalue n 1 i 0 a[ i] accumulate(start, end, initialvalue, operator) - operator : 합산과정에서사용될연산을정의하는함수 - e.g 정수로된배열의곱셈 int Product(int *a, int n) {//a[0:n-1] 의수의곱셈을반환 int initval = 1; return accumulate(a, a+n, initval, multiplies<int>()); } Copyright 2007 DBLAB, Seoul National University 35

STL 알고리즘 copy 와 next_permutation copy - 원소순차를한장소에서또다른장소로복사 - copy(start, end, to) start, start+1,..., end-1 에서 to, to+1,..., to+end-start 로복사 next_permutation - [start,end) 범위에있는원소들의다음으로큰사전식순열생성 - 그러한다음순열이존재하면 true 반환 - next_permutation(start,end) void Permutations(char *a, const int m) {//a[0:m] 의모든순열생성 // 모든순열을하나씩출력 do{ copy(a, a+m+1, ostream_iterator<char>(cout, )); cout << endl; }while(next_permutation(a, a+m+1)); } Copyright 2007 DBLAB, Seoul National University 36

성능분석과측정 (1) 프로그램의평가기준 - 우리가원하는작업을하는가? - 원래작업의명세에부합해서정확히작동하는가? - 문서화가되어있는가? - 논리적작업단위를수행하는기준으로함수가생성되었는가? - 코드가읽기쉬운가? 성능평가 (performance evaluation) - 성능분석 (performance analysis) 사전예측 - 성능측정 (performance measurement) 이후검사 Copyright 2007 DBLAB, Seoul National University 37

공간복잡도 (1) 공간복잡도 (space complexity) - 프로그램을실행시켜완료하는데필요한메모리양 - 고정부분 보통명령어공간, 단순변수, 집합체, 상수를위한공간 - 가변부분 변수, 참조된변수가필요로하는공간, 순환스택공간 - 프로그램 P 의공간요구 S(P) = c + S P - c : 상수 - S P : 인스턴스특성 문제에의존 인스턴스로인해필요로하는공간 Copyright 2007 DBLAB, Seoul National University 38

공간복잡도 (2) float Abc(float a, float b, float c) { return a+b+b*c+(a+b-c)/(a+b)+4.0; } - a,b,c 값각각을저장하고 Abc 에서값을반환하는데한워드가필요하다고가정 - S P = 0 line float Sum(float *a, const int n) { float s = 0; for(int i = 0 ; i < n ; i++) s+= a[i]; return s; } - S Sum (n) = 0 Copyright 2007 DBLAB, Seoul National University 39

공간복잡도 (3) line float Rsum(float *a, const int n) 1 { 2 if(n<=0) return 0; 3 else return(rsum(a, n-1) + a[n-1]); 4 } - R Sum 을호출할때마다적어도네개의워드 (n 과 a 값, 반환값, 반환주소에필요한공간포함 ) - 순환깊이가 n+1 이므로순환스택공간에 4(n+1) Copyright 2007 DBLAB, Seoul National University 40

시간복잡도 (1) 시간복잡도 - 프로그램을완전히실행시키는데필요한시간 - T(P) = 컴파일시간 + 실행시간 (t P ( 인스턴스특성 )) - t P (n) = c a ADD(n)+c s SUB(n)+c m MUL(n)+c d DIV(n) + n : 인스턴스특성 C a, C s, C m, C d : +, -, x, / 연산을위한상수시간 ADD, SUB, MUL, DIV : 특성 n 인인스턴스에서각연산의실행횟수 Copyright 2007 DBLAB, Seoul National University 41

시간복잡도 (2) 프로그램단계수 (number of steps) - 주석 : 0 - 선언문 : 0 변수, 상수정의 (int, long, short, char,...) 사용자데이타타입정의 (class, struct, union, template) 접근결정 (private, public, protected, friend) 함수타입결정 (void, virtual) - 산술식및지정문 : 1 예외 : 함수호출을포함하는산술식 - 반복문 : 제어부분에대해서만단계수고려 - 스위치명령문 switch(<expr>) 의비용 = <expr> 의비용 각조건의비용 = 자기의비용 + 앞서나온모든조건의비용 - if-else 문 <expr>, <statement1>, <statement2> 에따라각각단계수가할당 Copyright 2007 DBLAB, Seoul National University 42

시간복잡도 (3) 프로그램단계수 (number of steps) - 함수호출 값에의한전달인자포함하지않을경우 : 1 값에인한전달인자포함할경우 : 값인자크기의합 순환적인경우 : 호출되는함수의지역변수도고려 - 메모리관리명령문 : 1 - 함수명령문 : 0 비용이이미호출문에할당 - 분기명령문 : 1 Copyright 2007 DBLAB, Seoul National University 43

단계수테이블 명령문의실행당단계수 (s/e : step per execution) 결정 - s/e : 그명령문의실행결과로 count 가변화하는양 명령문이실행되는총횟수계산 line float Sum(float * a, const int n) 1 { 2 float s = 0; 3 for(int i = 0 ; i < n ; i++) 4 s+= a[i]; 5 return s; 6 } Copyright 2007 DBLAB, Seoul National University 44

피보나치수 피보나치수열 - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... - F 0 = 0, F 1 = 1 - F n = F n-1 + F n-2, n 2 void Fibonacci(int n) {// 피보나치수 F n 계산 if(n<=1) cout << n << endl; //F 0 =0 와 F 1 =1 else { // F n 을계산한다 int fn; int fnm2 = 0; int fnm1 = 1; for(int i = 2 ; i <=n ;i++) { fn = fnm1 + fnm2; fnm2 = fnm1; fnm1 = fn; }//for 문의끝 cout << fn << endl; }//else 의끝 } (1)n=0, 1 인경우 : 2 (2)n>1 인경우 : 4n+1 Copyright 2007 DBLAB, Seoul National University 45

점근표기법 (1) 빅오 (big oh ) - 모든 n, n n 0 에대해 f(n) cg(n) 인조건을만족시키는두양의상수 c 와 n 0 가존재하면 f(n)=o(g(n)) - 예 3n + 2 = O(n) (c=4, n 0 =2) 3n + 3 = O(n) (c=4, n 0 =3) 100n + 6 = O(n) (c=101, n 0 =10) 10n 2 + 4n + 2 = O(n 2 ) (c=11, n 0 =5) 1000n 2 + 100n 6 = O(n 2 ) (c=1001, n 0 =100) 6*2 n + n 2 = O(2 n ) (c=7, n 0 =4) 3n + 3 = O(n 2 ) (c=3, n 0 =2) 10n 2 + 4n + 2 = O(n 4 ) (c = 10, n 0 =2) 3n + 2 O(1) 10n 2 + 4n +2 O(n) Copyright 2007 DBLAB, Seoul National University 46

점근표기법 (2) 연산시간 - 상수시간 : O(1) - 로그시간 : O(logn) - 선형시간 : O(n) -n 로그시간 : O(nlogn) - 평방시간 : O(n 2 ) - 입방시간 : O(n 3 ) - 지수시간 : O(2 n ) - 계승시간 : O(n!) 연산시간의크기순서 O(1) O(logn) O(n) O(nlogn) O(n 2 ) O(n 3 ) O(2 n ) O(n!) Copyright 2007 DBLAB, Seoul National University 47

점근표기법 (3) 오메가 (omega) - 모든 n, n n 0 에대해 f(n) cg(n) 을만족시키는두양의상수 c 와 n 0 가존재하면 f(n) = (g(n)) - 예 3n + 2 = Ω(n) (n 0 =1, c=3) 3n + 3 = Ω(n) (n 0 =1, c=3) 100n + 6 = Ω(n) (n 0 =1, c = 100) 10n 2 + 4n +2 = Ω(n 2 ) (n 0 =1, c = 1) 6*2 n + n 2 = Ω(2 n ) (n 0 =1, c = 1) 3n + 3 = Ω(1) 10n 2 + 4n + 2 = Ω(n) 6*2 n + n 2 = Ω(1) Copyright 2007 DBLAB, Seoul National University 48

점근표기법 (4) 세타 (theta) - 모든 n, n n 0 에대해 c 1 g(n) f(n) c 2 g(n) 을만족시키는세양의상수 c 1, c 2 와 n 0 가존재하면, f(n) = (g(n)) - 예 3n + 2 = (n) (c 1 =3, c 2 =4, n 0 =2) 3n + 3 = (n) 10n 2 + 4n + 2 = (n 2 ) 6*2 n + n 2 = (2 n ) 10*log n + 4 = (log n) 3n + 2 (1) 3n + 3 (n 2 ) 10n 2 + 4n + 2 (n) 10n 2 + 4n + 2 (1) 6*2 n + n 2 (n 100 ) 6*2 n + n 2 (1) Copyright 2007 DBLAB, Seoul National University 49

매직스퀘어 (magic square) 1~n 2 까지의정수로된 n n 행렬 각행의합, 열의합, 주대각선의합이모두동일 첫번째행의중앙에 1 을넣는것부터시작한다. 빈정방형에 1 씩큰수를할당하면서왼쪽대각선방향으로올라간다. 만약정방형밖으로벗어나면정방형의반대편자리에서계속한다. 즉상단을벗어나면같은열의최하단으로, 왼쪽에서벗어나면같은행의제일오른쪽으로이동한다. 만약정방형이채워져있으면밑으로움직여서계속한다. Copyright 2007 DBLAB, Seoul National University 50

성능측정 (1) 프로그램의공간및시간요구량을구하는것 순차탐색함수에대한최악의경우성능측정 - 시간을측정할 n 의값들결정 - n 의값들에대해서최악의성질을가진데이타결정 int SequentialSearch (int *a, const int n, const int x) {// a[0:n-1] 에대해탐색 int i; for(i=0; i<n && a[i]!= x; i++); if(i==n) return -1; else return i; } - 점근적해석 : Θ(n) 작은 n 값, 무시된저차항들의영향에의해정확하지않을수있음 Copyright 2007 DBLAB, Seoul National University 52

테스트데이타의생성 최악의성능을초래하는데이타세트생성 - 관심있는인스턴스특성값들에대해적당한대규모의무작위테스트데이타생성 - 생성한테스트데이타각각에대해실행시간측정 - 이들시간의최대값을최악의경우의시간으로사용 평균인경우의시간측정 - 주어진특성의모든가능한인스턴스에대한평균 - 위에언급된기법을사용해서평균시간의어림값계산 실험을위해생성되어야할데이타들을결정하기위해사용되는알고리즘을분석하는것이바람직 Copyright 2007 DBLAB, Seoul National University 54