chap x: G입력

Transcription

1 재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19)

2 이진검색의재귀알고리즘 int binsearch(int list[], int key, int left, int right) { /*search list[0] <= list[1] <=... <= list[n-1] for key. Return its position if found. Otherwise return -1 */ int middle; if (left <= right) { middle = (left + right) / 2; switch (compare(list[middle], key)) { case -1: return binsearch(list, key, middle+1, right); case 0: return middle; case 1: return binsearch(list, key, left, middle-1); return -1; 1 장. 기본개념 (Page 20)

3 예 1.4: 순열 (Permutations) 문제정의 n 1 개의원소를갖는집합에대해이집합의모든원소들에대한순열을출력하라. 예 : 집합 {a, b, c 에대해순열의집합 = {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a) n 개의원소에대한순열의수는 n! 재귀적인해결방법 : 집합 {a, b, c, d 를가정 a 가먼저나온후, {b, c, d 로구성된모든순열 b 가먼저나온후, {a, c, d 로구성된모든순열 c 가먼저나온후, {a, b, d 로구성된모든순열 d 가먼저나온후, {a, b, c 로구성된모든순열 1 장. 기본개념 (Page 21)

4 Program 1.8: 순열을출력하는재귀함수 void perm(char *list, int i, int n) // list[i] 에서 list[n] 까지의원소로구성된모든순열출력 // {a, b, c, d 의경우초기호출 = perm(list, 0, 3) { int j, temp; if (i == n) { // 단하나의순열만존재. 그냥출력하자 for (j = 0; j <= n; j++) printf("%c", list[j]); printf(" "); else { // 하나이상의순열존재. 재귀적으로출력 for ( j = i; j <= n; j++) { SWAP(list[i], list[j], temp); perm(list, i+1, n); SWAP(list[i], list[j], temp); 1 장. 기본개념 (Page 22)

5 perm() 함수의동작과정 i n perm(0, 3) i,j swap(0, 0) i j n n b a c d swap(0, 1) i n perm(1, 3) i,j swap(1, 1) i n i j n a c b d swap(1, 2) j,n a d c b swap(1, 3) i n perm(2, 3) i n a c b d perm(2, 3) i,j n swap(2, 2) i j,n a b d c swap(2, 3) i,j n a c b d swap(2, 2) i j,n a c d b swap(2, 3) i,n perm(3, 3) i,n a b d c perm(3, 3) i,n a c b d perm(3, 3) i,n a c d b perm(3, 3) 1 장. 기본개념 (Page 23)

6 3. 데이터추상화 (Data Abstraction) C 언어에서데이터타입 기본형 : char, int, float, double 확장형 : short, long, unsigned 그룹화 : array, struct, union 포인터 데이터타입의정의 데이터객체의모음및그데이터객체에적용가능한연산들의집합 예 : int 객체 : {0, 1, -1, 2, -2,..., INT_MAX, INT_MIN 연산 : {+,, *, /, %,... 1 장. 기본개념 (Page 24)

7 추상적데이터타입 (Abstract Data Type) 데이터객체의내부표현양식을아는것이도움이될까? Yes, but dangerous! Abstract Data Type (ADT) 의정의 데이터객체및연산의명세와데이터객체의내부표현양식 / 연산의구현내용을분리 예 : Ada package, C++ class ADT 에서연산의명세 구성요소 : 함수이름, 인자들의타입, 결과들의타입 함수의호출방법및결과물이무엇인지를설명 함수의내부동작과정및구현방법은은폐 Information Hiding 1 장. 기본개념 (Page 25)

8 연산명세에서내부함수들의종류 생성자 (Creator/Constructor) 데이터객체의새로운인스턴스생성 Transformer 기존인스턴스를이용하여새로운인스턴스를생성 관찰자 (Observer/Reporter) 인스턴스에대한정보를출력 1 장. 기본개념 (Page 26)

9 ADT 의예 : Natural Number ADT Natural_Number 객체 : 0 부터시작하여컴퓨터로표현할수있는최대정수 (INT_MAX) 까지의범위에속하는정수들의집합함수 : for all x, y Natural_Number; TRUE, FALSE Boolean and where +,, <, and == are the usual integer operations Nat_No Zero( ) ::= 0 Boolean Is_Zero(x) ::= if (x) return FALSE else return TRUE Nat_No Add(x, y) ::= if ((x + y) <= INT_MAX) return x + y else return INT_MAX Boolean Equal(x, y) ::= if ( x == y ) return TRUE else return FALSE Nat_No Successor(x) ::= if ( x == INT_MAX ) return x else return x + 1 Nat_No Subtract(x, y) ::= if (x < y) return 0, else return x y end Natural_Number 1 장. 기본개념 (Page 27)

10 4. 성능분석 (Performance Analysis) 프로그램의평가기준 주어진문제를해결 정확성 (Correctness) 문서화 (Documentation) 모듈화 (Modularization) 가독성 (Readability) 공간효율성 (Space efficiency) 시간효율성 (Time efficiency) 필수적인요소 좋은프로그래밍습관 성능과관련 성능분석 (Complexity theory, Simulation) vs. 성능측정 (Benchmarking) 복잡성 (Complexity) 의정의 공간복잡성 : 프로그램실행에소요되는메모리 시간복잡성 : 프로그램의실행시간 1 장. 기본개념 (Page 28)

11 4.1 공간복잡성 (Space Complexity) 고정적인공간요구사항 입력과출력크기에무관한공간들 예 : 명령어공간, 단순변수나상수를위한공간, 가변적인공간요구사항 : S p (I) I 의수나크기, 그리고 I/O 의횟수등에따라가변적인공간 프로그램 P 의전체공간요구 S(P) = c + S p (I) 예 : 단순산술함수 S abc (I) = 0 float abc( float a, float b, float c ) { return a+b+b*c + (a+b-c)/(a+b) + 4.0; 예 : 배열에저장된원소들의합 : Program 장. 기본개념 (Page 29)

12 Program 1.10 과 Program 1.11 float sum(float list[], int n) { float tempsum = 0; int i; for (i = 0; i < n; i++) tempsum += list[i]; return tempsum; Program 1.10: S sum (I) = 0 float rsum(float list[], int n) { if (n) return rsum(list, n-1) + list[n-1]; return 0; Program 1.11: S rsum (I) = (n+1)(float * + int) 1 장. 기본개념 (Page 30)